Симплекс-метод линейного программирования

Аннотация:

линейные

программы

имеют

удивительную

структуру.

Симплексные методы используют эту удивительную структуру, чтобы быстро

найти

оптимальный

способ.

Благодаря

этому

проблемы

с

миллионами

переменных

теперь

могут

быть

решены,

следовательно,

решаются

чрезвычайно сложные промышленные проблемы. Вот почему симплексные

методы стали решающими в нашем мире на сегодня.

Ключевые слова:

симплексный метод, линейное программирование,

целевая функция, сложность.

Любая

задача

линейного

программирования

с

двумя

переменными

может быть легко решена с помощью графического метода, так как легче

иметь дело с двумерным графиком. Все возможные решения в графическом

методе лежат в пределах допустимой области на графике, и мы использовали

для проверки угловых точек допустимой области для оптимального решения,

т.

е.

одна

из

угловых

точек

допустимой

области

была

оптимальным

решением. Мы использовали для проверки всех угловых точек, помещая эти

значения в целевую функцию.

Но если число переменных увеличивается, становится очень трудно

решить проблему, рисуя ее график, поскольку проблема становится слишком

сложной. Симплексный метод был разработан американским математиком

Г. Б. Данцигом.

Этот метод является математической обработкой графического метода.

Здесь также различные угловые точки возможной области проверяются на

оптимальность. Но проверить все угловые точки невозможно, так как число

угловых

точек

увеличивается

по

мере

увеличения

числа

уравнений

и

переменных. Максимальное число этих точек, подлежащих испытанию

m + nm = m+1! m! n!

где m-число, а n-число переменных.

Таким образом, в симплексном методе число угловых точек,

подлежащих тестированию, значительно сокращается за счет использования

очень

эффективного

алгоритма,

который

приводит

нас

к

оптимальной

угловой точке решения всего за несколько итераций. Давайте возьмем один

пример и будем действовать шаг за шагом.

Целевая

функция-максимизировать Z=

1 2x1

+

1 5x2

+

1 4x3

Шаг 1:

(a) правая сторона всех ограничений должна быть либо нулевой, либо

+ve. Если они-ve, то они должны быть сделаны +ve путем умножения обеих

сторон на (-1), и знак неравенства будет обращен. В этом примере R. H. S.

Уже +ve или ноль.

b) все неравенства преобразуются в равенства путем добавления или

вычитания слабых или избыточных переменных. Эти слабые или избыточные

переменные вводятся потому, что легче иметь дело с равенствами, чем с

неравенствами в математической обработке.

Если ограничение ≤ type, переменные slack добавляются, если

ограничение

≥

type,

то

избыточная

переменная

вычитается.

Здесь

вялые

переменные s,, s2 и s3 добавляются в три неравенства (i), (ii) и (iii), получаем.

и объективная функция становится

Максимальное значение z = 12х1 + 15х2 + 14x3 + ОС 1 Под + для OS2 + os3

Шаг 2:

Найти исходное основное возможное решение:

Мы

начинаем

с

возможного

решения,

а

затем

переходим

к

оптимальному

решению

на

следующих

итерациях.

Начальное

возможное

решение

предпочтительно

выбирать

в

качестве

источника,

т.

е.

там,

где

регулярные переменные, например, в этом случае xv x2, x3, принимают

нулевые значения. т. е. x1 x2, x3 = 0

и мы получаем s1 = 0, s2 = 0 и s3 = 100 из неравенств (i), (ii) и (iii)

Основными переменными являются переменные, которые в настоящее

время находятся в решении, например, Sv S2 и S3 являются основными

переменными в исходном решении.

Неосновные

переменные-это

переменные,

которые

установлены

равными нулю и не находятся в текущем решении, например, x1 и x2 и x3

являются неосновными переменными в исходном решении.

Вышеуказанная информация может быть представлена в Таблице 1.

В таблице первая строка представляет коэффициенты целевой функции,

вторая строка - различные переменные (сначала регулярные переменные,

затем

переменные

слабины/избытка).

Третья

четвертая

и

пятая

строки

представляют коэффициенты переменных во всех ограничениях.

Первый столбец представляет коэффициенты основных переменных

(текущие переменные решения) в задаче (ei) второй столбец представляет

основные переменные (текущие переменные решения), а последний столбец

представляет правую часть ограничений в стандартной форме. Т. е. после

объединения всех неравенств в равенства в любой таблице текущие значения

переменных текущего решения (основных переменных) задаются R. H. S.

В Таблице 1, текущее решение:

S1 =0, S2 = 0, S3 = 100

Конечно, неосновные переменные Xv X2 и X3 также будут равны нулю

Вырождение

всякий

раз,

когда

какая-либо

базовая

переменная

принимает

нулевые

значения,

текущее

решение

считается

вырожденным,

поскольку в настоящей задаче S1 = 0 и S2 = 0 задача может быть решена

путем замены S1 = t и S2 = t, где t очень мало +ve число.

Шаг 3:

Тест На Оптимальность.

Тест оптимальности может быть выполнен, чтобы найти, является ли

текущее

решение

оптимальным

или

нет.

Для

этого

сначала

напишите

последнюю строку в виде (Ej), где

Ej = Σei. Мос.

Где aij представляет коэффициенты в матрице идентичности тела для I-

й

строки

и

j-го

столбца,

т.

е.

представляет

первый

столбец

таблицы.

В

последней строке запишите значение (Cj-Ej), где c; представляет значения

первой

строки,

а

Ej

представляет

значения

последней

строки.

(Cj

–

Ej)

представляет

собой

преимущество

приведения

любой

неосновной

переменной к текущему решению, т. е. делая ее базовой.

В таблице 2 значения Cj-Ej равны 12, 15 и 14 для Xv X2 и X3. Если

любое

из

значений

Cj-Ej

равно

+ve,

то

это

означает,

что

большинство

положительных

значений

представляет

переменную,

которая

вводится

в

текущее решение, в максимальной степени увеличит целевую функцию. В

данном случае X2-это потенциальная переменная, входящая в решение для

следующей итерации. Если все значения в строке (Cj – Ej) отрицательны, это

означает, что оптимальное решение достигнуто.

Шаг 4:

Итерации в направлении оптимального решения:

Максимальное

значение

Cj-Ej

дает

ключ

coloumn,

как

отмечено

в

таблице

Поэтому X2-входящая переменная, т. е. она станет базовой и войдет в

решение.

Из

существующей

неосновной

переменной,

и

человек

должен

выйти и стать неосновным. Чтобы найти, какая переменная должна быть

вытеснена, я разделяю коэффициенты в столбце RHS на соответствующие

коэффициенты в ключевом столбце, чтобы получить столбец отношения.

Теперь найдите наименьшее положительное значение в столбце Ratio, и это

даст ключевую строку. В настоящей задаче мы имеем три значения, т. е. t, µ и

100, и из них t является наименьшим +ve. Поэтому строка, соответствующая

T в столбце отношения, будет ключевой строкой. И С., будет оставлять

переменной. Элемент на пересечении ключевой строки и ключевого coloumn

является ключевым элементом.

Теперь все элементы в ключевом coloumn, кроме ключевого элемента,

должны быть сделаны нулевыми, а ключевой элемент-единым. Это делается с

помощью операций строк, как это делается с матрицами. Здесь ключевым

элементом уже является unity, а другой элемент в key coloumn равен нулю,

добавляя

-1

раз

первую

строку

в

третью

строку

и

получая

следующую

таблицу.

Поэтому вторым возможным решением становится

X1 = 0, X2 = t и X3 = 0 там z = 15t

В новой таблице S1 был заменен на X2 в основных переменных и

соответственно EI coloumn также был изменен.

Шаг 5:

При взгляде на значения Cj-Ej в таблице 3 мы обнаруживаем, что x1

имеет большинство +ve значений 27, что указывает на то, что решение может

быть

дополнительно

улучшено,

приведя

x1

в

решение,

т.

е.

сделав

его

основным. Поэтому X1 coloumn является ключевым столбцом, также найдите

ключевую

строку,

как

объяснялось

ранее,

и

заполните

таблицу

5.

Ключевой

элемент

в

таблице

5

выходит

равным

2,

и

он

сделан

единицей, а все остальные элементы в ключевом coloumn сделаны нулевыми

с помощью операций строки, и, наконец, мы получаем таблицу 6. Первый

ключевой элемент делается unity путем деления этой строки на 2. Затем,

добавив подходящие кратные этой строки в другие строки, мы получим

таблицу 6.

Из таблицы 6 видно, что решение still не является оптимальным, так

как

Cj-Ej

имеет

еще

+

ve

значения

1/2

это

дает

ключ

coloumn

и

соответствующая ключевая строка найдена, ключевой элемент выполнен, как

у к а з а н о

в

т а б л и ц е

7

Теперь с помощью подходящих операций строк мы делаем другие

элементы в ключевом столбце равными нулю, как показано в таблице 8.

Видно, что так как все значения в строке Cj-Ej либо-ve, либо нулевое

оптимальное решение достигнуто.

Окончательное решение X1 = 40 тонн

x2 = 40 тонн

x3 = 20 тонн

поскольку t очень мал, им пренебрегают.

Симплексные методы-это удивительные методы, которые используют

структуру линейных программ. Для решения еще более масштабных проблем

необходимо улучшить управление базами. Вот где используются и очень

эффективны такие методы, как генерация столбцов и разложение Бендера.

Однако они могут быть медленными в случаях вырождения, которые на

самом деле очень распространены во многих классических моделях. Другие

методы разрабатываются для борьбы с вырождением, включая двойственную

переменную стабилизацию или улучшенный первичный симплекс.

В

целом,

основное

применение

линейных

программ

касается

целочисленного линейного программирования, которое может моделировать

очень

большой

спектр

задач.

Однако

необходимо

добавить

много

дополнительных

методов,

включая

ветвь

и

границу,

метод

режущей

плоскости или, в последнее время, целочисленный симплекс. Для улучшения

целочисленного линейного программирования еще предстоит провести много

исследований.

Литература:

1.Двухфазные

методы

решения

задач

линейного

программирования:

первый и второй фазы

2.Линейное

программирование:

необходимый

тур

для

исследования

деятельности