Тема 3. Решение задач линейного программирования

МЕТОДОМ ИСКУССТВЕННОГО БАЗИСА (10 часа, в т.ч. 1 час - тематический контроль, 6 часов - ВАРС)

 

Цель – освоить алгоритм модифицированного симплексного метода в симплексных таблицах.

 

Содержание

 

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

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

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

Последовательность выполнения заданий

Для успешного выполнения заданий необходимо:

1. Изучить правило перехода от исходной задачи к М-задаче и алгоритм М - метода по учебному пособию (параграф 3.3. учебного пособия Водолазская Л.В.[3]).

2. Запомнить, как выглядит целевая функция М-задачи на максимум и на минимум целевой функции.

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

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

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

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

7. При составлении числовой экономико-математической модели по условиям заданий 3.15 и 3.16 присвоить имена переменным и дать названия ограничениям.

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

 

Варианты заданий

 

3.1. Z min = x1 – x2 + x3 + x4 – x5	3.2. Z min = x1 – 2x2 + 3x3
3.3. Z min = x1 + x2 – x3 – 2x4	3.4. Z max = 3x1 + 5x2 + 4x3
3.5. Z max = 4x1 + 10x2 + 9x3 + 3x4	3.6. Z min = 12x1 + 27x2 + 6x3
3.7. Z max = x1 + 2x2 + 3x3 – x4	3.8. Z max = –x1 – 2x2 + x3

 

 

3.9. Задача максимизации целевой функции Z решалась методом искусственного базиса. На каком-то шаге получилась следующая таблица (табл. 11).

Таблица 11

Симплексная таблица

СП БП	Сj Сi			-1
ai0	X2	X3	X4
X1		3/2	-3/2	1/2	1/2
Y2	-M	3/2	3/2	3/2	-3/2
Y3	-M	7/2	11/2	-1/2	-3/2
Z		3/2	-7/2	3/2	-1/2
M		-5	-7	-1

 

1. Проверить правильность заполнения Z- и M-строки.

2. Записать в аналитической форме исходную и М-задачу.

3. Довести решение до конца.

3.10.Задача минимизации целевой функции решалась методом искусственного базиса. На некотором шаге получена таблица 12.

Таблица 12

Симплексная таблица

СП БП	Сj Сi			-1	-1
ai0	X1	X3	X4
X2			-1	-2	-1
Y2	M		(3)	-1
Y3	M			-1
Z
M

 

1. Заполнить Z- и М-строку.

2. Записать математическую модель М-задачи.

3. Существует ли максимум функции Т?

4. Правильно ли выбран разрешающий столбец и разрешающий элемент?

5. Довести решение до конца.

Домашние задания

 

3.11. Z min = -2x1 - x2 + x3

 

3.15.Составить рацион для свиней на откорме. В рационе должно быть не менее: 25 МДж обменной энергии, 287 г сырого протеина, 16 г кальция и не более 130 г клетчатки.

Критерий оптимальности – минимальная себестоимость рациона. Остальная информация задана в таблице 13.

Таблица 13

Исходная информация

Вид корма	Содержание в 1кг корма	Себестоимость 1кг корма, коп.
обменной энергии, МДж	сырого протеина	кальция	клетчатки
г
Ячмень
Горох					8,5
Трава люцерны	2,2				0,6
Свекла			0,4

 

 

3.16.Определить максимальное количество продукции в стоимостном выражении. Имеются следующие ресурсы: пашня – 500 га, объем трудовых ресурсов – 980 чел. дн., материально-денежные средства (МДС)- 1000 тыс. руб. Остальная информация задана в таблице 14.

Таблица 14

Исходная информация

Культура	Урожайность, ц/га	Затраты на 1 га	Выход продукции с 1га, тыс.руб.
Труда, чел.дн.	МДС, тыс.руб.
Пшеница
Ячмень
Капуста

 

Зерна должно быть произведено не менее 6000 ц, а капусты – не менее 120 ц. Ресурсы могут быть недоиспользованы. Дать экономическое описание оптимального решения.

 

 

Вопросы для контроля

 

1. При решении каких задач применяется метод искусственного базиса?

2. Каким образом записывается целевая функция при решении задач модифицированным симплексным методом?

3. Назовите теорему, устанавливающую связь между оптимальными решениями М-задачи и Z-задачи.