Решение с помощью симплексного метода

1. Решение с помощью симплексного метода.

Составим математическую модель задачи. Обозначим через х₁ и х₂ выпуск продукции А и В соответственно. Затраты материала первого сорта на план  составят 2х₁ + 5х₂ и они недолжны превосходить запасов 45 кг:

Аналогично, ограничения по материалу второго сорта

И по материалу третьего сорта:

Прибыль от реализации х₁ изделий А и х₂ изделий В составит

целевая функция задачи.

Получили модель задачи:

Вводом балансовых переменных приводим модель к каноническому виду:

 

Запишем начальное опорное решение:

Симплекс-таблицу заполняем из коэффициентов при неизвестных из системы ограничений и функции:

Баз.перем.	С	План	7	5	0	0	0
			х1	х2	х3	х4	х5
х3	0	45	2	5	1	0	0
х4	0	27	3	2	0	1	0
х5	0	38	4	3	0	0	1
∆Z		0	-7	-5	0	0	0
x3	0	27	0	11/3	1	-2/3	0
x1	7	9	1	2/3	0	1/3	0
х5	0	2	0	1/3	0	-4/3	1
∆Z		63	0	-1/3	0	7/3	0
x3	0	5	0	0	1	14	-11
x1	7	5	1	0	0	3	-2
x2	5	6	0	1	0	-4	3
∆Z		65	0	0	0	1	1

в индексной строке содержатся две отрицательные оценки , наибольшая по абсолютной величине (-7)

В индексной строке содержится отрицательная оценка (-1/3).

в индексной строке нет отрицательных оценок

Так как все оценки положительные записываем оптимальное решение:

При этом плане прибыль от реализации изделий х₁ = 5 и х₂ = 6 составит Z_max = 65; х₄ = 0 и х₅ = 0 означает, что материал второго и третьего сорта использован полностью, а х₃ = 5 говорит о том, что осталось еще 5 кг материала первого сорта.

Получили Z_max = 65 тыс. руб. при .

2. Графическое решение:

Рассмотрим систему линейных неравенств.

Строим область допустимых решений данной задачи. Для этого строим граничные линии в одной системе координат:

 (I),

 (II),

 (III),

х₁ = 0 (IV), х₂ = 0 (V).

Для построения прямых берем по две точки:

  

Областью решений является пятиугольник ABCDO.

Затем строим на графике линию уровня

 

и вектор

 

или

Теперь перемещаем линию уровня в направлении вектора . Последняя точка при выходе из данной области является точка С – в ней функция

 

достигает своего наибольшего значения.

Определим координаты точки С из системы уравнений (II) и (III):

Подставим найденные значения в целевую функцию:

.

Т.е. максимальная прибыль от реализации изделий А и В составит 65 тыс. рублей.

№46

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

Решение:

Модель предыдущей задачи:

Двойственная ей задача имеет вид:

Для предыдущей задачи ее решение:  при

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

Проверка:

 верно.

№ 66

Решить транспортную задачу.

Решение:

1. Занесем данные задачи в таблицу:

	В1	В2	В3	В4	В5
А1	5	8	7	10	3	100
А2	4	2	2	5	6	200
А3	7	3	5	9	2	200
А4	5	7	4	2	5	100
	190	100	130	80	100	600

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

 ограничения по поставкам

 ограничение по потребителям

 (,( ограничения по здравому смыслу.

Цель задачи (стоимость всей перевозки) в математической форме:

Задача разрешима, т.к.

.