Методы оптимальных решений (стр. 2 )

То, что план не оптимальный, видно из четвертой строки: имеются отрицательные числа.

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

Так, число -30 означает, что при включении в план производства одного изделия А обеспечивается увеличение прибыли выпуска продукции на 30 руб. Если включить в план производства одно изделие В, то общая прибыль возрастет на 40 руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий В.

Определим, какой вектор включить в базис:

.

Вектор Р2 включаем в базис.

Определяем, какой вектор исключить из базиса:

для аi2 > 0.

.

Соответствует Р5. Этот вектор исключаем из базиса.

Столбец вектора Р2 и 3-я строка являются направляющими.

Составляем таблицу II итерации (табл. 2).

Таблица 2.

i	Базис	Сб	Р0	30	40	0	0	0
P1	P2	P3	P4	P5
1	P3	0	216	11	0	1	0	-1/3
2	P4	0	36	3	0	0	1	-1/3
3	P2	40	21	1/4	1	0	0	1/12
4			840	-20	0	0	0	10/3

Заполняем строку вектора Р2: элементы строки получаются из соответствующих элементов предыдущей таблицы 1 делением на разрешающий элемент (на 12).

.

Заполняем столбцы для базисных векторов. На пересечении Pi´Pi ставим единицы, остальные элементы – нули.

Вычисляем следующие элементы в столбцах:

r = 5 (исключенный вектор), k = 2 (включенный вектор)

,

,

,

,

,

.

Вычислим элементы в 4-й строке по рекуррентным формулам:

,

,

.

Найденный план не является оптимальным, т. к. в столбце вектора Р1 – отрицательное число: -20 < 0.

Х = (0, 21, 216 36, 0).

Значит, Р1 вводим в базис.

Р4 – исключаем из базиса.

Составляем таблицу III итерации:

Таблица 3.

i	Базис	Сб	Р0	30	40	0	0	0
P1	P2	P3	P4	P5
1	P3	0	84	0	0	1	-11/3	8/9
2	P1	30	12	1	0	0	1/3	-1/9
3	P2	40	18	0	1	0	-1/12	1/9
4			1080	0	0	0	20/3	10/9

Сначала заполняем элементы 2-й строки (для Р1). Получаем их из элементов 2-й строки таблицы 2 делением на разрешающий элемент: на 3 (Р1´Р4).

Заполняем остальные строчки: сначала столбцы для Р3, Р1, Р2 (единицы Pi´Pi и нули)

Остальные ячейки – по рекуррентным формулам:

r = 4 (исключенный вектор), k = 1 (включенный вектор)

,

,

,

,

.

Заполняем последнюю строчку.

,

,

.

В четвертой строке таблицы нет отрицательных Dj. Значит, найденный опорный план является оптимальным: Х = (12, 18, 84, 0, 0).

Ответ: план выпуска продукции, являющийся оптимальным, включает изготовление:

12 изделий А,

18 изделий В.

На изделие А: 12×12 = 144 кг – I вида сырья,

12×4 = 48 кг – II вида сырья,

12×3 = 36 кг – III вида сырья.

На изделие В: 18×4 = 72 кг – I вида сырья,

18×4 = 72 кг – II вида сырья,

18×12 = 216 кг – III вила сырья.

Использовано I вида сырья: 144+72 = 216 кг – осталось 300 – 216 = 84 кг,

использовано II вида сырья: 48+72 = 120 кг – использовано полностью,

использовано III вида сырья: 36+216 = 252 кг –использовано полностью.

Прибыль от производимой продукции 1080 руб.

Задание

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

Предположим, что для производства двух видов продукции А и В можно использовать только материал трех сортов. При этом на изготовление единицы изделия вида А расходуется (19 – 0, 02k) кг материала первого сорта, (20 + 0,03k) кг материала второго сорта и (20 + 0,02k) кг материала третьего сорта. На изготовление единицы изделия вида В расходуется (24 + 0,1k) кг материала первого сорта, (42 – 0, 05k) кг материала второго сорта, (20 – 0,02k) кг материала третьего сорта. На складе фабрики имеется всего материала первого сорта (5100 + k) кг, материала второго сорта (7200 + 2k) кг, материала третьего сорта (5000 + 3k) кг. От реализации готовой продукции вида А фабрика имеет прибыль (5 + 0,1×k) руб., а от продукции вида В прибыль (6 + 0,2×k) руб. Здесь k – номер варианта студента. Определить максимальную прибыль от реализации всей продукции видов А и В.