Контрольная работа по "Методам оптимальных решений"

 

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

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

Вместо переменной x₉ в план 7 войдет переменная x₆.

Строка, соответствующая  переменной x₆ в плане 7, получена в результате деления всех элементов строки x₉ плана 6 на разрешающий элемент РЭ=²⁸/₈₇

На месте разрешающего элемента в плане 7 получаем 1.

В остальных клетках  столбца x₆ плана 7 записываем нули.

Таким образом, в новом  плане 7 заполнены строка x₆ и столбец x₆.

Все остальные элементы нового плана 7, включая элементы индексной строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12
x8	105/28	0	0	0	-1/28	5/28	0	0	1	19/28	0	-1	-19/28
x6	2311/28	0	0	0	-19/28	-17/28	1	0	0	33/28	0	0	-33/28
x7	813/14	0	0	0	3/14	-1/14	0	1	0	1/14	-1	0	-1/14
x1	1813/14	1	0	0	3/14	-1/14	0	0	0	1/14	0	0	-1/14
x2	305/28	0	1	0	-1/28	5/28	0	0	0	19/28	0	0	-19/28
x3	15	0	0	1	0	0	0	0	0	-1	0	0	1
F(X7)	7005/7	0	0	0	6/7	15/7	0	0	0	12/7	M	M	-12/7+M

 

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12
x8	105/28	0	0	0	-1/28	5/28	0	0	1	19/28	0	-1	-19/28
x6	2311/28	0	0	0	-19/28	-17/28	1	0	0	33/28	0	0	-33/28
x7	813/14	0	0	0	3/14	-1/14	0	1	0	1/14	-1	0	-1/14
x1	1813/14	1	0	0	3/14	-1/14	0	0	0	1/14	0	0	-1/14
x2	305/28	0	1	0	-1/28	5/28	0	0	0	19/28	0	0	-19/28
x3	15	0	0	1	0	0	0	0	0	-1	0	0	1
F(X8)	7005/7	0	0	0	6/7	15/7	0	0	0	12/7	M	M	-12/7+M

 

Так как в оптимальном  решении отсутствуют искусственные  переменные (они равны нулю), то данное решение является допустимым.

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

x₁ = 18¹³/₁₄

x₂ = 30⁵/₂₈

x₃ = 15

F(X) = 6•18¹³/₁₄ + 12•30⁵/₂₈ + 15•15 = 700⁵/₇

Ответ: максимальная суммарная прибыль от выпуска продукции в размере 700⁵/₇ у.е. возможна при выпуске продукции первого вида в количестве 18 единиц, при выпуске продукции второго вида в количестве 30 единиц и при выпуске продукции третьего вида в количестве 15 единиц.

Задача № 3.

Транспортная задача.

Построить опорный план методом минимальной стоимости  и найти оптимальное решение  задачи методом потенциалов.

	17	13	25
20	8	3	6
15	4	2	5
30	9	4	7

 

Решение:

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

F = ∑∑c_ijx_ij,    (1)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

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

	1	2	3	Запасы
1	8	3	6	20
2	4	2	5	15
3	9	4	7	30
Потребности	17	13	25

 

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

∑a = 20 + 15 + 30 = 65

∑b = 17 + 13 + 25 = 55

Как видно, суммарная  потребность груза в пунктах  назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 10 (65—55). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

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

	1	2	3	4	Запасы
1	8	3	6	0	20
2	4	2	5	0	15
3	9	4	7	0	30
Потребности	17	13	25	10

 

Этап I. Поиск первого  опорного плана.

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

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

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

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

 

 

	1	2	3	4	Запасы
1	8	3	6[20]	0	20
2	4[2]	2[13]	5	0	15
3	9[15]	4	7[5]	0[10]	30
Потребности	17	13	25	10

 

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

2. Подсчитаем число  занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции  для этого опорного плана равно:

F(x) = 6*20 + 4*2 + 2*13 + 9*15 + 7*5 + 0*10  = 324

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 6; 0 + v₃ = 6; v₃ = 6

u₃ + v₃ = 7; 6 + u₃ = 7; u₃ = 1

u₃ + v₁ = 9; 1 + v₁ = 9; v₁ = 8

u₂ + v₁ = 4; 8 + u₂ = 4; u₂ = -4

u₂ + v₂ = 2; -4 + v₂ = 2; v₂ = 6

u₃ + v₄ = 0; 1 + v₄ = 0; v₄ = -1

	v1=8	v2=6	v3=6	v4=-1
u1=0	8	3	6[20]	0
u2=-4	4[2]	2[13]	5	0
u3=1	9[15]	4	7[5]	0[10]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;2): 0 + 6 > 3; ∆₁₂ = 0 + 6 - 3 = 3

(3;2): 1 + 6 > 4; ∆₃₂ = 1 + 6 - 4 = 3

max(3,3) = 3

Выбираем максимальную оценку свободной клетки (1;2): 3

Для этого в перспективную  клетку (1;2) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	8	3[+]	6[20][-]	0	20
2	4[2][+]	2[13][-]	5	0	15
3	9[15][-]	4	7[5][+]	0[10]	30
Потребности	17	13	25	10