Материал: Д6520 Алексеев Математические методы в инженерии

Так как из А₁ в В₁ перевозки не могут быть осуществлены, то в ячейке (1,1) тариф считаем равным некоторому сколь угодно большому числу М. Полагаем равным этому же числу и тариф для ячейки (3,1). Одновременно в эту клетку помещаем число 10, так как по условию из А₃ в В₁ нужно завезти 10 ед. груза. В дальнейшем ячейку (3,1) считаем свободной со сколь угодно большим тарифом М. Находим опорный план методом наименьшей стоимости и проверяем его на оптимальность.

Он не оптимален, так как одна оценка является положительной (1). Строим новый план (итерация 1). Он является оптимальным. Следовательно, исходная ТЗ имеет оптимальный план

Х^ = .

При этом общая стоимость перевозок является минимальной:

z^* = 430 + 135 + 440 + 520 + 225 + 510 + 160 = 575 ден. ед.

Пример 5. Найдем решение ТЗ, исходные данные которой приведены в табл. 8 с учетом того, что из пункта А₂ в пункт В₄ завезти не менее 5 ед. груза, а из А₂ в В₁ – не более 30 ед. груза.

Таблица 8
Вj Аi	50	80	30	60
65	3	5	5	1
85	4	5	6	2
70	5	1	3	3

Так как из А₂ в В₄ необходимо завезти не менее 5 ед. груза, то запасы этих пунктов отправления и назначения считаем меньшими на 5 ед. Кроме того, поскольку из А₂ в В₁ необходимо завезти не более 30 ед. груза, то пункт назначения В₁ разобьём на два пункта:

Потребности В₁ теперь считаем равными 30 ед. и рассмотрим дополнительный пункт В′′₁ с потребностями, равными 50–30 = 20 ед. В столбце В′′₁ записываем тарифы, помещённые в ячейках столбца В₁, за исключением ячейки (2,1′′). В этой ячейке тариф полагаем равным некоторому сколь угодно большому числу М.

Мы сложили соответствующие переменные столбцов В₁ и В′′₁ и добавили 5 ед. груза в ячейку (2,4) исходя из дополнительных условий задачи. При этом общая стоимость перевозок

z^* = 320 + 145 + 430 + 510 + 630 + 215 + 170 = 555 ден. ед.

является минимальной.

Пример 6. Пусть требуется найти решение ТЗ, исходные данные которой приведены в табл. 9, причём потребности В₂ и В₄ должны быть полностью удовлетворены.

Таблица 9
Вj Аi	50	80	30	60
12	9	14	12	10
19	8	6	10	8
7	7	8	7	10

Задача открытая, так как = 38, = 50. Вводим фиктивного поставщика, его мощность а₄ = 12. Так как потребности В₂ и В₄ должны быть полностью удовлетворены, то следует назначить очень высокую стоимость М перевозки в В₂ и В₄ от фиктивного поставщика.

Решение имеет вид:

Методические указания к лабораторной работе

Решение транспортных моделей целесообразно выполнять с помощью пакета прикладных программ MathCAD.

Рассмотрим, например, решение транспортной задачи по критерию стоимостей.

Условия ТЗ

Пусть на складах А₁, А₂, А₃ хранится а₁ = 70, а₂ = 90, и а₃ = 50 тонн топлива соответственно. Требуется доставить его четырем потребителям В₁, B₂, B₃, B₄, заказы которых составляют b₁ = 50, b₂ = 70, b₃ = 40, b₄ = 40 тонн соответственно. Стоимости перевозки с_ij одной тонны с i-го склада j-му потребителю указаны в таблице:

Требуется:

1. Установить, является ли модель транспортной задачи, задан-ная таблицей, открытой или закрытой. Если модель является открытой, то её необходимо закрыть.

2. Составить план перевозок, обеспечивающий минимальную стоимость перевозок.

3. Найти минимальную стоимость перевозок.

Решение

1. Суммарные запасы груза составляют 210, а суммарные потребности 200 т. Следовательно, задача является задачей открытого типа и ее необходимо закрыть, вводя фиктивного потребителя с потребностями 10 единиц груза при нулевых стоимостях перевозок. Приходим к задаче: