Гайсин И.Ф., гр. 1308

Лабораторная работа №2 Применение симплексного метода для конкретной задачи Вариант №1

З а д а ч а

Предприятие выпускает два вида продукции: А и В, при этом используется сырьё трёх типов. На изготовление единицы изделия А необходимо затратить:

= 10 кг сырья первого типа,

= 5 кг сырья первого типа,

= 1 кг сырья первого типа,

Для изготовления единицы изделия В тратится:

= 8 кг сырья первого типа,

= 10 кг сырья первого типа,

= 2 кг сырья первого типа,

Производство обеспечено сырьём каждого типа в количествах:

= 168 кг сырья первого типа,

= 180 кг сырья первого типа,

= 24 кг сырья первого типа,

Прибыль от реализации единицы изделия А составляет = 14 денежных единиц, единицы

изделия = 18 денежных единиц.

Составить план производства изделий А и В, обеспечивающий максимальную прибыль при их реализации.

План выполнения работы:

1. Составим математическую модель ЗЛП.

2. Решить ЗЛП симплексным методом. Дать Экономический анализ решения.

3. Решить задачу графически. Сравнить полученные результаты.

Контрольные вопросы:

1. Математическая формулировка ЗЛП?

2. Какие неизвестные в системе называются базисными и как их выбирать?

3. В чем заключается идея симплексного метода?

4. Каковы содержание и последовательность шагов симплекс – алгоритма, реализованного на симплекс таблицах?

5. Формулировка критерия оптимальности решения ЗЛП для симплексного метода?

6. Каково назначения искусственного базиса и когда он вводится?

7. В чем сущность зацикливания при решение ЗЛП и как оно устраняется?

Р е ш е н и е

Сформулируем задачу математически: пусть — количество изделий А и — количество изделий В, спланированных к производству. Тогда потребуется:

Таким образом, система ограничений будет иметь вид:

При реализации продукции будет получено денежных единиц, следовательно целевая функция запишется в виде:

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

таблица 1

неизв. базис	х1	х2	х3	х4	х5	bi	Оценочное отношение
х3	10	8	1	0	0	168	21
х4	5	10	0	1	0	180	18
х5	1	2	0	0	1	24	12
-F	14	18	0	0	0	0

таблица 2

неизв. базис	х1	х2	х3	х4	х5	bi	Оценочное отношение
х3	6	0	1	0	-4	72	12
х4	0	0	0	1	-5	60
х2	0,5	1	0	0	0,5	12	24
-F	5	0	0	0	-9	-216

Опорное решение, соответствующее таблице 2: Х=(0; 12; 72; 60; 0) F_max= 216

Таблица 2 не оптимальна, следует составить следующую таблицу 3 по аналогии с таблицей 2.

таблица 3

неизв. базис	х1	х2	х3	х4	х5	bi	Оценочное отношение
х1	1	0	1/6	0	-2/3	12
х4	0	0	0	1	-5	60
х2	0	1	-1/12	0	5/6	6
-F	0	0	-5/6	0	-17/3	-276

Опорное решение, соответствующее таблице 3: Х=(12; 6; 0; 60; 0) F_max = 276

Таблица 3 оптимальна, так как в индексной строке нет положительных элементов, и значит, мы достигли оптимального решения F_max = 276.

Изделие вида А – 12 ед., вида В – 6 ед., при этом остается 60 кг сырья 2 типа.

Опорное решение, соответствующее таблице 3: Х=(12; 6; 0; 60; 0) является допустимым и оптимальным, так как в индексной строке нет отрицательных элементов и все свободные члены положительны. Х=(12; 6; 0; 60; 0) и значение целевой функции = ( ) = 276..

Экономический вывод: продукцию вида А необходимо произвести 12 единиц, вида В — 6 единиц. При этом прибыль будет максимальна и равна 276 денежных единиц, при этом остается 60 кг сырья 2 типа.