Основы математического программирования (стр. 12 )

α11 = 4/10 – 0 = 4/10 (β11 = 0, т. к. β11 ≤ 4/10 и ≤ 18/10)

α12 = -2/10 – (-1) = 8/10 (β12 = -1, т. к. β12 ≤ -2/10 и ≤ 18/10)

α13 = 0 – (0) = 0 (β13 = 0, т. к. β13 ≤ 0 и ≤ 18/10)

α1св = 18/10 – (1) = 8/10 (β1св. = 1, т. к. β1св. ≤ 18/10)

Получаем дополнительное условие

4/10y1 + 8/10y2 + 0y3 ≥ 8/10

Вводим еще одну переменную

S = 4/10y1 + 8/10y2 + 0y3 - 8/10

Приводим полученное уравнение к каноническому виду:

S - 4/10y1 - 8/10y2 - 0y3 = - 8/10

Вводим переменную S в базис в последнюю таблицу

БП	СЧ	y1	y2	y3	x1	x2	x3	S
x1	18/10	4/10	-2/10	0	1	0	0	0
x2	23/10	-1/10	3/10	0	0	1	0	0
x3	7/10	-9/10	-3/10	1	0	0	1	0
S	-8/10	-4/10	-8/10	0	0	0	0	1
Z	194/10	2/10	4/10	1	0	0	0	0

Начинаем решать все сначала.

Строка S разрешающая, т. к. переменную S надо вывести из базиса.

Столбец по наименьшему положительному симплексному отношению.

БП	СЧ	y1	y2	y3	x1	x2	x3	S
x1	2		0
x2	2		0
x3	1		0
y2	1	1/2	1	0	0	0	0	-10/8
Z	19	0	0	1	0	0	0	1/2

Таблица последняя, нет отрицательных чисел в последней строке. Решение целочисленное.

x1 = 2

x2 = 2

x3 = 1

y1 = 0

y2 = 1

y3 = 0

S = 0

Zmax = 19

Проверяем

3x1 + 2x2 + y1 = 10 y1 = 10 –3x1 - 2x2 = 10 – 6 – 4 = 0

x1 + 4x2 + y2 = 11 y2 = 11 – x1 – 4x2 = 11 – 2 – 4*2 = 11 – 2 – 8 = 1

3x1 + 3x2 + x3 + y3 = 13 y3 = 13 – 3x1 – 3x2 – x3 = 13 – 6 – 6 – 1 = 0

S = 4/10y1 + 8/10y2 – 8/10 = 0 +8/10 – 8/10 = 0

Ответ:

x1 = 2

x2 = 2

x3 = 1

Zmax = 19

2.11. Постановка транспортной задачи

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью.

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

Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т. е. перевозка k единиц продукции вызывает расходы k* сij

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

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

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

Постановка задачи.

Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm.

Данный груз необходимо доставить n потребителям в объемах b1, b2, …, bn.

Известны сij, i = 1, 2, …, m; j = 1, 2, …, n – стоимости перевозки единицы груза от каждого i-ого поставщика j-тому потребителю.

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

Исходные данные транспортной задачи обычно записываются в таблице.

Поставщики	bj ai	Потребители
b1	b2	…	bn
a1	с11	c12	…	c1n
a2	c21	c22	…	c2n
…	…	…	…	…
am	cm1	cm2		cmn

Исходные данные задачи могут быть представлены также в виде: