Поиск первоначального опорного плана

Предположим, что каноническая задача ЛП имеет не совсем специальный вид, а к примеру, правые части уравнений системы ограничений могут быть отрицательны.
Этот случай возникает при решении задачи о рационе. Канонический вид задачи выглядит так:


F = 20х1 + 20х2 + 10х3 → min.

Запишем задачу в симплекс-таблицу (табл. 1).

Таблица 1

Базисное решение, соответствующее базису {x4, x5, x6} и равное (0; 0; 0; -33; 23; -12), не является допустимым ввиду отрицательности х4 < 0, x5 < 0, x6 < 0.

Сформулируем правило нахождения допустимого опорного плана.
Если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2-5.
Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. Далее симплекс-методом дорешать задачу. Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом.
Проведем этот шаг для задачи о рационе. В качестве разрешающей строки табл. 1 нужно выбрать первую. А разрешающим элементом выберем, к примеру, элемент -4.

Таблица 2

базисные

-х4

-х2

-х3

свободные

х1

х5

х6

F

5

5

0

165

Заметим, что переменная х1 вошла в базис вместо х4, все вычисления осуществлялись по правилу 2-5. В правом столбце еще остался отрицательный элемент, воспользуемся правилом еще раз. Строка переменной х6 - разрешающая, а в качестве разрешающего элемента возьмем, к примеру, 3/2, здесь есть некоторая возможность выбора.

Таблица 2

базисные

-х4

-х2

-х6

свободные

х1

7

х5

х3

F

5

5

0

165

Полученный базисный план х* = (х1, х2, х3, х4, х5, х6) = (7, 0, 5/2, 0, 1/2, 0) является допустимым и, к тому же, оказывается оптимальным, т.к. в индексной строке нет отрицательных элементов. Оптимальное значение целевой функции равно F* = 165. Действительно,
F = 20х1 + 20х2 + 10х3 = 20 · 7 + 0 + 10· = 140 + 25 = 165.

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

Решение задачи о плане симплекс-методом

Задача. Предприятие располагает тремя видами сырья и намеревается выпускать четыре вида продукции. Коэффициенты в таблице 3.12 указывают затраты соответствующего вида сырья на единицу определенного вида продукции, а также прибыль от реализации единицы продукции и общие запасы ресурсов. Задача: найти оптимальный план производства продукции, при котором будет обеспечена максимальная прибыль.

Таблица 3

Виды продукции →

Виды сырья ↓

I

II

III

IV

Запасы ресурсов

1

5

0,4

2

0,5

400

2

0

5

1

1

300

3

1

0

1

1

100

Прибыль

3

5

4

5

 

Составим математическую модель. Пусть х1, х2, х3, х4 - количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:

F = 3x1 + 5x2 + 4x3 + 5x4 → max.

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

Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х5, х6, х7 в каждое из неравенств.
Очевидно, что, если первого ресурса необходимо для производства плановой продукции 5х1 + 0,4х2 + 2х3 + 0,5х4, то х5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х6 и х7. Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Запишем задачу в таблицу 4, предварительно выписав ее каноническую форму:

I этап. Это задача специального вида, базис составляют переменные {х5, х6, х7}, правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) - опорный. Он соответствует симплекс-таблице.

Таблица 4

базисные

-х1

-х2

-х3

-х4

свободные

х5

5

0,4

2

0,5

400

х6

0

5

1

1

300

х7

1

0

1

1 ←

100

-F

-3

-5

-4

-5 ↑

0

II этап. Проверим план на оптимальность. Так как в индексной F-строке есть отрицательные элементы, то план неоптимален, переходим к III этапу.

III этап. Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, но могли бы выбрать и второй, т.к. в обоих (-5). Остановившись на четвертом, выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум соотношений . С разрешающим элементом 1 проводим преобразование таблицы по правилам 2-5 (табл. 5).

Таблица 5

Полученный план опять неоптимален, т.к. в F-строке есть отрицательный элемент -5. этот столбец разрешающий.

В качестве разрешающего элемента выбираем 5, т.к. .

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять "внутренность" таблицы (табл. 6).

Таблица 6

базисные

-х1

-х6

-х3

-х7

свободные

х5

 

 

 

 

334

х2

 

 

 

 

40

х4

 

 

 

 

100

-F

1

1

1

4

700

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

IV этап. Базисные переменные {x5, x2, x4} принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х* = (0, 40, 0, 100, 334, 0, 0) и F* = 700. Действительно, = 3х1 + 4х3 + 5х2 + 5х4 = 5 · 40 + 5 · 100 = 700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV - вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х5  = 334, х6 = 0, х7 = 0).

загрузка...