Решение задач с помощью линейного программирования

 

4) Пересчет симплекс-таблицы

Формируем следующую  часть симплексной таблицы.

Вместо переменной x₃ в план 2 войдет переменная x₂. Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₃ плана 1 на разрешающий элемент РЭ=3. На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x₂ плана 2 записываем нули. Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂ . Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

 

 

 

 

Представим  расчет каждого элемента в виде таблицы:

Таблица 2.2.6

B	x1	x2	x3	x4	x5

 

После преобразований получаем новую таблицу:

Таблица 2.2.7

Базис	В	x1	x2	x3	x4	x5
X2	81	0	1	0,333	-0,333	0
X1	92	1	0	-0,11	0,44	0
X5	130	0	0	-1,44	1,11	1
F(X2)	5970	0	0	4	10	0

 

1) Проверка критерия оптимальности

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Таблица 2.2.8

Базис	В	x1	x2	x3	x4	x5
X2	81	0	0	0,333	-0,333	0
X1	92	0	1	-0,11	0,44	0
X5	130	1	0	-1,44	1,11	1
F(X3)	5970	0	0	4	10	0

 

Оптимальный план можно записать так:

X₂ = 81

X₁ = 92

X₅ = 130

F(X) = 42 92 + 26 81 = 5970

 

Ответ: Для достижения максимальной прибыли 5970 ден.ед. следует производить 92 ед. продукции вида А₁ и 81 ед. продукции вида А₂. (ответ совпадает с ответом полученным графическим способом).

2.3. Решение задачи планирования производства с помощью теории двойственности

 

Составим двойственную задачу к прямой задаче.

3y1+4y2+1y3≥42

4y1+1y2+5y3≥26

600y1+357y2+600y3 => min

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

 Решение  двойственной задачи дает оптимальную  систему оценок ресурсов.

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

 Из первой  теоремы двойственности следует,  что Y = C A^-1.

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

А(a₁, a₂, a₅)=

Определив обратную матрицу А^-1 через алгебраические дополнения, получим:

A^-1=

 

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C A^-1 = (42,26,0)       

          

Оптимальный план двойственной задачи равен:

 y1 = 11,1

 y2 = -1,93

 y3 = 0

 Z(Y) = 600 11,1+357 (-1,93)+600 0 = 5970

Ответ: Для достижения максимальной прибыли 5970 ден.ед. следует производить 92 ед. продукции вида А₁ и 81 ед. продукции вида А₂.

2.4 Составление математической модели транспортной задачи

 

На три базы А₁, А₂, А₃ поступил однородный груз в количествах: 370, 450, 480 усл. ед. соответственно. Груз требуется развести в пять пунктов: 300 в пункт В1, 280 в пункт В2, 330 в пункт В3, 290 в пункт В4, 100 в пункт В5.

Спланировать перевозки  так, чтобы их общая стоимость  была минимальной.

Математическая  модель транспортной задачи:

Пусть Хij – количество груза, отправляемого с базы Аi в пункт Вj.

Целевая функция:

 

 

 

 

 

Таблица 2.4.1

Пункт отправления	В1	В2	В3	В4	В5	Запасы, аi
A1	21	18	14	3	6	370
A2	7	11	10	5	12	450
A3	4	8	16	9	13	480
Потребности, bj	300	280	330	290	100

 

Ограничения:

2.5 Нахождение опорного плана транспортной задачи методом наименьшего элемента

 

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

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 370 + 450 + 480 = 1300

∑b = 300 + 280 + 330 + 290 + 100 = 1300

Условие баланса  соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

 

Таблица 2.5.1

Пункт отправления	В1	В2	В3	В4	В5	Запасы, аi
A1	21	18	14	3	6	370
A2	7	11	10	5	12	450
A3	4	8	16	9	13	480
Потребности,bj	300	280	330	290	100	1300

 

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

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

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

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

Искомый элемент  равен 3. Для этого элемента запасы равны 370, потребности 290. Поскольку минимальным является 290, то вычитаем его.

X₁₄ = min(370,290) = 290.

Таблица 2.5.2

21	18	14	3	6	370-290
7	11	10	х	12	450
4	8	16	х	13	480
300	280	330	290-290	100	0

 

Искомый элемент  равен 4. Для этого элемента запасы равны 480, потребности 100. Поскольку минимальным является 100, то вычитаем его.

X₃₁ = min(480,100) = 100.

Таблица 2.5.3

x	18	14	3	6	80
х	11	10	х	12	450
4	8	16	х	13	480-300
300 - 300	280	330	0	100	0

 

Искомый элемент  равен 6. Для этого элемента запасы равны 80, потребности 100. Поскольку минимальным является 100, то вычитаем его.

X₁₅ = min(80,100) = 80.

Таблица 2.5.4

x	18	14	3	6	80-80
х	11	10	х	х	450
4	8	16	х	х	180
0	280	330	0	100-80=20	0

 

Искомый элемент  равен 12. Для этого элемента запасы равны 450, потребности 20. Поскольку минимальным является 20, то вычитаем его.

X₃₂ = min(450,20) = 20.

Таблица 2.5.5

x	18	14	3	х	0
х	11	10	х	12	450-20
4	8	16	х	х	180
0	280	330	0	20-20	0