5. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ задач линейного программирования

5.1. Переход от одного опорного плана к другому

Пусть известна К-матрица на S-ом шаге алгоритма решения ЗЛП

.                                   (5.1)

Обозначим через  вектор номеров базисных (единичных) столбцов матрицы ,  - вектор, компоненты которого есть базисные компоненты опорного плана (базисные переменные), определяемого матрицей , и могут быть отличны от нуля. Остальные (n - m) компонент опорного плана, определяемого матрицей , равны нулю (свободные переменные). Очевидно, что векторы и полностью задают опорный план, определяемый матрицей . Например, пусть

=,

тогда ;  и, следовательно, опорный план, определяемый , имеет вид =(2,0,1,0,0,4).

Итак, пусть К-матрица (5.1) определяет невырожденный опорный план

                                      (5.2)

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

Пусть . Считая  направляющим элементом, совершим над матрицей  один шаг метода Жордана-Гаусса. В результате получим новую матрицу

,                         (5.2)

в которой столбец  стал единичным, но которая может и не быть К-матрицей, так как среди величин могут быть отрицательные. Условия выбора направляющего (опорного) элемента , позволяющие получить новую К-матрицу - , т.е. обосновывающие способ перехода от опорного плана  к опорному плану , составляет содержание следующей теоремы:

Теорема 5.1 Пусть в k-м столбце К-матрицы -  есть хотя бы один строго положительный элемент (,). Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую К-матрицу - , выбрав направляющий элемент из условия:

.                        (5.3)

Доказательство теоремы следует из следующих соображений. Представим К-матрицу в следующем виде

.                         (5.4)

Тогда переход к следующей К-матрице () с помощью метода Жордана-Гаусса, полагая элемент  направляющим, можно описать посредством выражений:

, где ,                           (5.5)

, где ,                                    (5.6)

, где ,                           (5.7)

, где .                                     (5.8)

Итак, если задан k-й столбц К-матрицы , в котором следует выбрать направляющий элемент  так, чтобы полученная в процессе шага метода Жордана-Гаусса матрица была К-матрицей (т.е. все её элементы  оставались неотрицательными), то рассматривая (5.7) получим  или иначе , откуда следует (5.3). Для (5.8) выражение (5.3) следует автоматически.

5.2. Определение симплекс-разности. Способ перехода к лучшему опорному плану. Критерии оптимальности опорного плана и         отсутствия конечного решения

Определение 5.1. Величину

                               ,                                  (5.4)

где  - вектор, компонентами которого являются коэффициенты целевой функции  при базисных () переменных опорного плана, определяемого матрицей , назовем j-й симплекс-разностью матрицы .

Если столбец  является единичным в матрице , то =0.

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

; ;      (5.5)

,         (5.6)

где k - номер столбца , вводимого в базис при получении матрицы из, а определяется по формуле (5.3).

Выражение (5.6) следует из следующих соображений:

1. Так как в базисном решении на S-ом шаге переменная  была свободной и соответственно , а при введении столбца  в базис на (S+1)-ом шаге переменная . Таким образом целевая функция увеличится на величину равную . С другой стороны на основании (5.8) . Откуда окончательно имеем, что целевая функция возрастёт на величину

.                                                   (5.7)

2. Из рассмотрния (5.7) видно, что значения базисных переменных с индексами  при переходе с S-го на (S+1)-й шаг уменьшаются соответственно на величины . Но тогда и целевая функция уменьшиться на сумму вида

.                                    (5.8)

Объединяя (5.7), (5.8) получим

,

откуда с учётом (5.4) непосредственно следует (5.6).

Теорема 5.2. Пусть в матрице есть  и в столбце  (, ) есть хотя бы один строго положительный элемент. Тогда от матрицы можно перейти к матрице , причем

.                                   (5.9)

Неравенство (5.9) вытекает из выражения (5.6), так как , а .

Теорема 5.3. Пусть все симплекс-разности матрицы  неотрицателные. Тогда опорный план , определяемый матрицей , является оптимальным.

Теорема 5.4. Пусть в матрице есть , и в столбце  (, ) нет ни одного строго положительного элемента. Тогда ЗЛП, определяемая К-матрицей на S-ом шаге алгоритма, не имеет конечного решения.

5.3. Алгоритм симплекс-метода

Будем считать, что известна исходная К-матрица К⁽⁰⁾ ЗЛП, определяющая исходный опорный план:

, .

В симплексном методе последовательно строят К-матрицы К⁽⁰⁾, К⁽¹⁾, …, К^(s) задачи линейного программирования, пока не выполнится критерий оптимальности или критерий, позволяющий убедиться в отсутствии конечного решения. Рассмотрим алгоритм S-й итерации симплексного метода. В начале S-й итерации имеем К-матрицу  задачи линейного программирования, определяющую опорный план

, .

Шаг 1. Вычисляем для столбцов  (, ) матрицы  симплекс-разности  и находим номер k из условия .

Шаг 2. Если , то опорный план  ,  является оптимальным, а  есть оптимальное значение целевой функции, иначе переходим к шагу 3.

Шаг 3. Если , , то ЗЛП не имеет конечного решения, иначе находим номер l из условия 

Таким образом, направляющий элемент на S-й итерации метода найден: .

Шаг 4. Вычисляем компоненты вектора : , , .

Шаг 5. Производим один шаг метода Жордана-Гаусса с направляющим элементом . Присваиваем переменной S алгоритма следующее значение и переходим к шагу 1.

5.4. Примеры решения задач симплекс-методом

Пример 5.1.            Симплекс-методом решить ЗЛП:

                                 (5.10)

при наличии ограничений:

                                      (5.11)

, .                                           (5.12)

Приводим систему линейных неравенств  (5.11) к каноническому виду, вводя в каждое неравенство дополнительную переменную , . Получим систему линейных уравнений:

                                      (5.11)

Целевая функция принимает вид

             (5.12)

Расширенная матрица 

системы линейных уравнений (5.11) является исходной К-матрицей ЗЛП, которая определяет исходный опорный план:

, .

Кроме того, .

Результаты последовательных итераций симплекс-алгоритма удобно оформить в виде симплекс-таблицы (см. табл. 5.1).

Таблица 5.1

На второй итерации S = 2, все , следовательно, опорный план

, ,

определяемый К-матрицей К⁽²⁾, оптимальный. Тогда

, .

Пример 5.2.            Симплекс-методом решить ЗЛП:

                                     (5.13)

при наличии ограничений:

                                           (5.14)

, .                                           (5.15)

Приводим систему линейных неравенств  (5.14) к каноническому виду, вводя в каждое неравенство дополнительную переменную , . Получим систему линейных уравнений:

                                           (5.16)

Целевая функция принимает вид

                             (5.12)

Результаты последовательных итераций записываем в симплекс-таблицу.

Таблица 5.2

Из симплекс-таблицы при S=2 следует, что согласно шагу 3 симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны. Следовательно,.

5.5. Задачи и упражнения

5.5.1. Предприятие производит 3 вида продукции: А₁, А₂, А₃, используя сырье двух видов: В₁ и В₂. Известны затраты сырья i-го вида на единицу изделия j-го вида (),  количество сырья каждого вида  (i=1,2), а так же прибыль, полученная от единицы изделия j-го вида с_j (j=1,2,3).

Сколько изделий каждого вида необходимо произвести, чтобы получить:            1) максимум прибыли;

                2) максимум товарной продукции?

Обозначения для вариантов: в таблице приведена матрица затрат: А=(а_ij), справа от таблицы значение b_i (i=1,2) и внизу - с_j (j=1,2,3).

у меня четвертый вариант

3) Решить задачу при дополнительных условиях: предприятие платит за хранение единицы сырья В₁ и В₂ соответственно 0,1 и 0,3 денежных единицы.

4) Решить задачу при условии, что задан план выпуска изделий. При решении учитывать возможность перевыполнения плана.

4. (200, 100, 250)    

5.5.2. Решить симплекс-методом задачу из п 1.5.1.

5.5.3. Решить симплекс-методом задачу из п 1.5.2.