Материал: М. М. Стальмакова

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 2 войдет переменная x₁.

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

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

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

B	x1	x2	x3	x4	x5	x6	x7
2125	0.5	1	1.5	2.5	0	0	0
427.5	0.25	0	-0.05	-0.25	1	0	0
92.5	-0.05	0	-0.35	-0.75	0	1	0
575	0.3	0	-0.1	-0.5	0	0	1
318750	-45	0	115	375	0	0	0

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	1270	0	1	1.6	3	-2	0	0
x1	1710	1	0	-0.2	-1	4	0	0
x6	178	0	0	-0.36	-0.8	0.2	1	0
x7	62	0	0	-0.04	-0.2	-1.2	0	1
F(X2)	395700	0	0	106	330	180	0	0

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	1270	0	1	1.6	3	-2	0	0
x1	1710	1	0	-0.2	-1	4	0	0
x6	178	0	0	-0.36	-0.8	0.2	1	0
x7	62	0	0	-0.04	-0.2	-1.2	0	1
F(X3)	395700	0	0	106	330	180	0	0

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

x₁ = 1710, x₂ = 1270, x₃ = 0

F(X) = 120*1710 + 150*1270 + 110*0 = 395700

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

В оптимальный план вошла дополнительная переменная x₆. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 178.

В оптимальный план вошла дополнительная переменная x₇. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 4-го вида в количестве 62.

Значение 0 в столбце x₁ означает, что использование x₁ - выгодно.

Значение 0 в столбце x₂ означает, что использование x₂ - выгодно.

Значение 106> 0 в столбце x₃ означает, что использование x₃ - не выгодно.

Значение 330 в столбце x₄ означает, что теневая цена (двойственная оценка) равна y₁=330.

Значение 180 в столбце x₅ означает, что теневая цена (двойственная оценка) равна y₂=180.

Значение 0 в столбце x₆ означает, что теневая цена (двойственная оценка) равна y₃

=0.

Значение 0 в столбце x₇ означает, что теневая цена (двойственная оценка) равна y₄=0.
Ответ: максимальная прибыль 395700 при производстве 1710 единиц Продукта 1 и 1270 единиц Продукта 2

№ 2. Распределить план перевозок однотипного груза от трёх поставщиков к четырём потребителям, обеспечив минимальные затраты на перевозку.

Исходные данные представлены в таблице 2.

Таблица 2. Транспортная задача.

	Тарифы по перемещению единицы груза, тыс. руб.
	Потребитель1	Потребитель2	Потребитель2	Потребитель4	Возможности поставщика
Поставщик1	7	4	9	3	400
Поставщик2	2	11	8	4	550
Поставщик 3	3	8	6	5	300
Потребности потребителя	450	250	200	350

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

F = ∑∑c_ijx_ij, (1)

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

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

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

x_ij ≥ 0

Запишем экономико-математическую модель для нашей задачи.

Переменные:

x₁₁ – количество груза из 1-го поставщика к 1-у потребителю.

x₁₂ – количество груза из 1-го поставщика к 2-у потребителю.

x₁₃ – количество груза из 1-го поставщика к 3-у потребителю.

x₁₄ – количество груза из 1-го поставщика к 4-у потребителю.

x₂₁ – количество груза из 2-го поставщика к 1-у потребителю.

x₂₂ – количество груза из 2-го поставщика к 2-у потребителю.

x₂₃ – количество груза из 2-го поставщика к 3-у потребителю.

x₂₄ – количество груза из 2-го поставщика к 4-у потребителю.

x₃₁ – количество груза из 3-го поставщика к 1-у потребителю.

x₃₂ – количество груза из 3-го поставщика к 2-у потребителю.

x₃₃ – количество груза из 3-го поставщика к 3-у потребителю.

x₃₄ – количество груза из 3-го поставщика к 4-у потребителю.

Ограничения по запасам:

x₁₁ + x₁₂ + x₁₃ + x₁₄ ≤ 400 (для 1 базы)

x₂₁ + x₂₂ + x₂₃ + x₂₄ ≤ 550 (для 2 базы)

x₃₁ + x₃₂ + x₃₃ + x₃₄ ≤ 300 (для 3 базы)

Ограничения по потребностям:

x₁₁ + x₂₁ + x₃₁ = 450 (для 1-го потребителя.)

x₁₂ + x₂₂ + x₃₂ = 250 (для 2-го потребителя.)

x₁₃ + x₂₃ + x₃₃ = 200 (для 3-го потребителя.)

x₁₄ + x₂₄ + x₃₄ = 350 (для 4-го потребителя.)

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

7x₁₁ + 4x₁₂ + 9x₁₃ + 3x₁₄ + 2x₂₁ + 11x₂₂ + 8x₂₃ + 4x₂₄ + 3x₃₁ + 8x₃₂ + 6x₃₃ + 5x₃₄ → min

С целью составления двойственной задачи переменные x_ij в условии (2) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,.., v_n.

Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа u_i (при i = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию:

G = ∑a_iu_i + ∑b_jv_j

при условии:

u_i + v_j ≤ c_ij, i = 1,2,..,m; j = 1,2,..,n (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

u_i + v_j ≤ c_ij, если x_ij = 0,

u_i + v_j = c_ij, если x_ij ≥ 0,

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

Числа u_i , v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j – потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

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

U – переменные для поставщиков, поставщиков;

V - переменные для магазинов, потребителей.

U₁ + V₁≤7

U₁ + V₂≤4

U₁ + V₃≤9

U₁ + V₄≤3

U₂ + V₁≤2

U₂ + V₂≤11

U₂ + V₃≤8

U₂ + V₄≤4

U₃ + V₁≤3

U₃ + V₂≤8

U₃ + V₃≤6

U₃ + V₄≤5

G(y)=450U₁ + 250U₂ + 200U₃ + 350U₄ + 400V₁ + 550V₂ + 300V₃ → max

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

	B1	B2	B3	B4	Запасы
A1	7	4	9	3	400
A2	2	11	8	4	550
A3	3	8	6	5	300
Потребности	450	250	200	350

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

∑a = 400 + 550 + 300 = 1250

∑b = 450 + 250 + 200 + 350 = 1250

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

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

	B1	B2	B3	B4	Запасы
A1	7	4	9	3	400
A2	2	11	8	4	550
A3	3	8	6	5	300
Потребности	450	250	200	350

Этап I. Поиск первого опорного плана.
1. Используя