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

Область допустимых решений ОЗЛП есть выпуклый многогранник, или симплекс. По этой причине наиболее распространенный метод решения задачи линейного программирования был назван симплекс-методом. Суть этого метода, как было показано выше, заключается в последовательном улучшении найденного заранее допустимого решения путем направленного перемещения из одной вершины ОДР в другую.

Последовательность основных этапов симплекс-метода следующая:

  • 1) отыскивается одна из вершин многогранника, удовлетворяющая условиям типа (14.6). Заметим, что при этом не все условия (14.7) могут быть выполнены;
  • 2) последовательными переходами в так называемые соседние вершины находят вершину, принадлежащую ОДР, т.е. обеспечивается выполнение и всех условий (14.7). Это означает, что получено опорное (допустимое) решение;
  • 3) если допустимое решение не является оптимальным, то, продолжая последовательный переход в соседние вершины и все время находясь в ОДР, находят вершину, удовлетворяющую условию (14.1), которой соответствует искомое решение задачи.

Эффективным механизмом реализации всех перечисленных этапов является формализованная схема, на каждом шаге которой производится замена одной свободной переменной на одну базисную. Эта схема получила название схема модифицированных жордановых исключений.

Рассмотрим механизм реализации каждого из перечисленных этапов. Начнем с отыскания одной из вершин многогранника, удовлетворяющей условиям (14.6). Система ограничений (14.6) представляет собой систему т линейных алгебраических уравнений с п неизвестными, которых больше, чем число уравнений. Следовательно, решая систему, можно определить ровно т (любых!) неизвестных, которые будут выражены через остальные (п - т) неизвестных. Тем самым производится разделение переменных на свободные и базисные. Эта операция реализуется за т шагов жордановых исключений. Затем переходят к нахождению опорного плана.

Алгоритм нахождения опорного плана. Пусть проведено к шагов модифицированных жордановых исключений и результат записан в виде табл. 14.1.

Таблица 14.1

Результат жордановых исключений

-*1

~x2

~xr

~xk

P

хк+1

«fcri.1

afc+l,2

aJfc+l,r

ak+,k

P,

хк+:2

ak+2,l

ak+2,2

ak+2,r

ak+2,k

P2

xs

asl

as2

asr

ask

Pp

хп

«„1

«„2

a nr

ank

P„,

L

Yi

Y2

Yr

Yк

Yo

Напомним: опорное решение лежит всегда в одной из вершин области допустимых решений и содержит не менее к нулевых компонентов. Таким образом, положив все переменные, расположенные в верхней точке таблицы (свободные переменные), нулю, всегда можно оказаться в угловой точке, т.е. X = (0, 0,О, (Зх, (32, ..., Рт). Поэтому если в табл. 14.1 все (3, неотрицательны, то имеем допустимое решение X* =(0,...,0,x^+1,jc^+2,...,x„) и можно переходить ко второму этапу решения задачи — улучшению опорного плана.

Если же существует хотя бы один отрицательный свободный член, например Рр < 0, то решение, соответствующее табл. 14.1, недопустимо. При этом возможны две ситуации.

  • 1. В 5-й строке табл. 14.1 все коэффициенты asj > 0. Свободные переменные, удовлетворяющие условию (14.7), можно только увеличивать, так как выбранное нами их исходное состояние нулевое. Поскольку в модифицированных жордановых исключениях они стоят со знаком «минус» и все as; > 0, то их произведение неположительно и никакое увеличение значений свободных переменных не может компенсировать отрицательности (L. Это означает, что соответствующая базовая переменная xs никогда не может быть сделана неотрицательной. Следовательно, допустимый план не может быть получен. Делаем заключение, что система ограничений в ОЗЛП несовместна и задача не имеет решения (конец решения задачи).
  • 2. В s-й строке табл. 14.1 существует хотя бы один отрицательный коэффициент asr < 0. Тогда член xs может быть сделан положительным за счет увеличения свободной переменной х,., чтобы компенсировать неотрицательность (Зр. Однако увеличение хг скажется на вычислении значений всех базовых переменных. Если в r-м столбце имеются положительные ajr, то при постепенном увеличении х, одна из базовых переменных обратится в нуль первой. Какая? Та, для которой выполняется соотношение

Вот эту базовую переменную и надо поменять местами со свободной переменной хг, что обеспечит переход именно в соседнюю вершину симплекса. Проделав соответствующий шаг модифицированных жордановых исключений, построим новую таблицу по типу табл. 14.1. Описанная процедура повторяется до тех пор, пока не получим допустимого решения либо не убедимся, что система ограничений несовместна.

Алгоритм улучшения опорного плана (собственно оптимизации). Пусть получено допустимое решение, т.е. Vp Рр > 0. Рассмотрим строку коэффициентов целевой функции. Если все уг> 0, то опорное решение является оптимальным. Действительно, увеличение любой свободной переменной может лишь уменьшить значение L. Значит, при нулевых значениях свободных переменных L наибольшее. Задача решена.

Если же существует уг < 0, то увеличение соответствующей свободной переменной хг увеличивает значение целевой функции, так как уг(-хг) > 0. Рассмотрим возможные при этом две ситуации.

  • 1. Все коэффициенты в столбце г неположительны (конечно, кроме строки L). Это означает, что беспредельное увеличение свободной переменной хп увеличивая L, не обращает базисные переменные в отрицательные числа и является допустимым. В этом случае говорят, что задача (14.1), (14.6), (14.7) не имеет конечного решения.
  • 2. Существует какое-то asr > 0. Тогда увеличение хг может привести к появлению отрицательной базовой переменной. Первой обратится в нуль та базовая переменная, для которой выполняется условие (14.11). Именно это соотношение и определяет базовую переменную х*, которую необходимо обменять на свободную хг. Покажем, что значение целевой функции при этом не уменьшится (может возрасти или останется неизменным).

Действительно, в соответствии с алгоритмом проведения жордановых исключений новое значение у0 (именно ему равна L при нулевых значениях всех свободных переменных) вычисляется по формуле

т.е. новое значение целевой функции не меньше прежнего.

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

Пример 14.4

Найти максимум функции при ограничениях

Решение. Запишем задачу в виде жордановой таблицы:

~Х1

-*2

-*з

—*4

—*5

1

0

-1

4

-2

1

0

6

0

1

1

2

0

-1

6

0

2

-1

2

0

0

4

L

-1

-2

1

0

0

0

Для разделения неизвестных на свободные и базисные последовательно проведем три шага модифицированных жордановых исключений.

После первого шага имеем

-*i

-*2

-*з

0

—*5

1

*4

-1

4

-2

1

0

6

0

1

1

2

0

-1

6

0

2

-1

2

0

0

4

L

-1

-2

1

0

0

0

После второго шага получаем следующую таблицу:

-*2

—*3

-*5

1

*4

5

0

-1

12

*1

1

2

-1

6

-*2

-*3

-*5

1

0

-3

-2

2

-8

L

-1

3

-1

6

Наконец, после третьего шага все переменные разделились:

"*2

-*з

1

х4

7/2

-1

8

*1

-1/2

1

2

*5

-3/2

-1

-4

L

-5/2

2

2

РешениеХ= (2,0,0, 8, -4), получаемое непосредственно из последней таблицы, не является допустимым, так как одна переменная имеет отрицательное значение (х5 = -4).

Проведем еще один шаг жордановых исключений. Используя правило (14.11), заменим х: нах3. Получим

2

-*1

1

х4

3

1

0

*3

-1/2

1

2

*5

-2

1

-2

L

-3/2

-2

-2

Полученное решение (2, 0, -2, 0, 0) также недопустимо, так как х3=-2. Проведем в соответствии с правилами алгоритма еще один шаг модифицированных жордановых исключений, заменив теперь х5 нах2:

~Х5

-*i

1

х4

3/2

5/2

7

*3

-1/4

3/4

5/2

х2

-1/2

-1/2

1

L

-3/4

-11/4

-1/2

Полученное решение (0,1, 5/2, 7, 0) допустимо, но не оптимально, так как коэффициенты целевой функции отрицательны. Сделав замену х4 на х1; получим

~хъ

4

1

*1

3/5

2/5

14/5

*3

-7/10

-3/10

2/5

х2

-1/5

1/5

12/5

L

9/10

11/10

72/10

Теперь решение X* = (xj = 14 / 5, х*2 = 2 / 5, Хз = 2 / 5) оптимально, при этом наибольшее значение целевой функции V = 7,2. Переменные х4 и х5 не входят в ответ задачи, поскольку были введены в процессе решения в качестве дополнительных.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >