Математические методы

Базис	B	x1	x2	x3	x4	min
x3	43	63/7	0	1	-2/7	631/45
x2	3	2/7	1	0	1/7	101/2
F(X2)	21	-2	0	0	1	0

 

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

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

Вместо переменной x₃ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₃ плана 1 на разрешающий элемент РЭ=6³/₇

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

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

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

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

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

Базис	B	x1	x2	x3	x4
x1	631/45	1	0	7/45	-2/45
x2	14/45	0	1	-2/45	7/45
F(X2)	3417/45	0	0	14/45	41/45

 

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

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

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

Базис	B	x1	x2	x3	x4
x1	631/45	1	0	7/45	-2/45
x2	14/45	0	1	-2/45	7/45
F(X3)	3417/45	0	0	14/45	41/45

 

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

x₁ = 6³¹/₄₅

x₂ = 1⁴/₄₅

F(X) = 4•6³¹/₄₅ + 7•1⁴/₄₅ = 34¹⁷/₄₅

Ответ: максимальная прибыль в размере 34,77 тыс. у.е. возможна при приобретении оборудования первого вида в количестве 6 единиц, второго вида 1 единицы.

Задача № 3.

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

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

	12	19	9
18	5	8	2
22	8	9	4
15	6	7	3

 

Решение:

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

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	5	8	2	18
2	8	9	4	22
3	6	7	3	15
Потребности	12	19	9

 

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

∑a = 18 + 22 + 15 = 55

∑b = 12 + 19 + 9 = 40

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

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

	1	2	3	4	Запасы
1	5	8	2	0	18
2	8	9	4	0	22
3	6	7	3	0	15
Потребности	12	19	9	15

 

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

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

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

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

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

 

 

	1	2	3	4	Запасы
1	5[9]	8	2[9]	0	18
2	8	9[7]	4	0[15]	22
3	6[3]	7[12]	3	0	15
Потребности	12	19	9	15

 

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

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

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

F(x) = 5*9 + 2*9 + 9*7 + 0*15 + 6*3 + 7*12  = 228

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

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

u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5

u₃ + v₁ = 6; 5 + u₃ = 6; u₃ = 1

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

u₂ + v₂ = 9; 6 + u₂ = 9; u₂ = 3

u₂ + v₄ = 0; 3 + v₄ = 0; v₄ = -3

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

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

 

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

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

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

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

	1	2	3	4	Запасы
1	5[9][+]	8	2[9][-]	0	18
2	8	9[7][-]	4[+]	0[15]	22
3	6[3][-]	7[12][+]	3	0	15
Потребности	12	19	9	15

 

Цикл приведен в таблице (2,3; 2,2; 3,2; 3,1; 1,1; 1,3; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	5[12]	8	2[6]	0	18
2	8	9[4]	4[3]	0[15]	22
3	6	7[15]	3	0	15
Потребности	12	19	9	15

 

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

u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5

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

u₂ + v₃ = 4; 2 + u₂ = 4; u₂ = 2

u₂ + v₂ = 9; 2 + v₂ = 9; v₂ = 7

u₃ + v₂ = 7; 7 + u₃ = 7; u₃ = 0

u₂ + v₄ = 0; 2 + v₄ = 0; v₄ = -2

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

 

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

Минимальные затраты составят:

F(x) = 5*12 + 2*6 + 9*4 + 4*3 + 0*15 + 7*15  = 225

Анализ оптимального плана.