Мат_моделир_2015_заоч_ЭП_ФИН / Транспортная / Транспортная

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

Постановка задачи. Имеется пунктов производства с заданными объемами производства некоторого однородного продукта и пунктов потребления с заданными объемами потребления . Известны затраты на перевозку единицы продукта из -го пункта производства в -й пункт потребления - . Требуется составить такой план перевозок , чтобы суммарные затраты на перевозку были минимальными и были удовлетворены потребности во всех пунктах потребления.

Для удобства составления математической модели в таблице 3.1 представлена сводка исходных данных.

Таблица 3.1. Сводка исходных данных

Пункты производства	Пункты потребления						Объемы производства
	В1	В2	…	Вj	…	Вn
А1	с11 х11	c12 х12	…	c1j х1j	…	c1n х1n	а1
А2	с21 х21	c22 х22	…	c2j х2j	…	c2n х2n	а2
…	…	…	…	…	…	…	…
Аi	ci1 хi1	ci2 хi2	…	cij хij	…	cin хin	ai
…	…	…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmj xmj	…	cmn xmn	am
Объемы потребления	b1	b2	…	bj	…	bn

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

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

Ограничения:

• на объемы производства (из каждого пункта производства нельзя вывезти больше того, что он может произвести)

(3.1)

• на объемы потребления (каждому потребителю нельзя привезти меньше того, что он требует)

(3.2)

Граничные условия: (количество перевозимого продукта не может быть отрицательным).

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

Виды моделей транспортной задачи

Транспортная задача может иметь закрытые и открытые модели.

Если , то имеем закрытую модель транспортной модели. В этом случае ограничения(3.1) и (3.2) записываются в виде равенств.

Если , то в этом случае модель транспортной задачи открытая. Чтобы решить задачу, создают фиктивный пункт потребления с объемом потребления

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

При также имеем открытую модель транспортной задачи. В этом случае создается фиктивный пункт производства с объемом производства и стоимостью перевозок

Пример 3.1. Бетон производят на трех бетонных заводах и потребляют на 4-х строительных объектах. Мощность заводов, потребности строительных объектов и стоимости перевозок 1м³ бетона от каждого завода к каждой строительной площадке приведены в таблице 3.2. Суммарная суточная мощность всех заводов равна 430 м³ . Суммарная потребность в бетоне 530 м³. Требуется так прикрепить строительные объекты к заводам, чтобы транспортные расходы были минимальными.

Таблица 3.2. Сводка исходных данных

Строит. объекты	В1	В2	В3	В4	Мощность заводов, м^3
Заводы
А1	2 х11	3 х12	4 х13	1 х14	100
А2	3 х21	3 х22	6 х23	2 х24	150
А3	3 х31	2 х32	4 х33	5 х34	180
Фиктивный	0 х41	0 х42	0 х43	0 х44	100
Потребности объектов, м^3	80	220	200	30	530

Математическая модель задачи

Поскольку задача имеет открытую модель, то вводим фиктивного производителя с нулевой стоимостью перевозок и объемом производства 100 м³.

Ограничения:

Граничные условия:

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

Транспортная задача является задачей линейного программирования специального типа. В частности, коэффициенты в ограничениях принимают значения 0 или 1 и каждая переменная входит только в два ограничения.

Решаем задачу в среде ЭТ с помощью надстройки «Поиск решения». Стоимости перевозок размещены в ячейках B5-E8. Решение задачи, т.е. объемы перевозок, будет получено в ячейках B14-E17. Целевая функция будет вычислена в ячейке В10 с помошью надстройки «Поиск решения». Предварительно эти ячейки должны быть отформатированы как содержащие целые числа (Формат - ячейки – число – числовой – количество десятичных знаков 0). Размещение информации и расчетные формулы представлены на рис. 3.1. При обращении к надстройке «Поиск решения» ограничения, которые следует ввести, следующие:

$B$14:$E$17=целое

$B$14:$E$17>=0

$B$18=$B$9

$C$18=$C$9

$D$18=$D$9

$E$18=$E$9

$F$14=$F$5

$F$15=$F$6

$F$16=$F$7

$F$17=$F$8

Рис.3.1. Размещение информации на рабочем листе ЭТ

В результате получим решение рис 3.2.

Рис. 3.2 Решение транспортной задачи

Анализ результатов оптимизации. Получили план (, , , , , , , , (ячейки В14:Е17)), удовлетворяющий всем ограничениям, граничным условиям и обеспечивающий транспортные затраты в сумме 1180 денежных единиц (ячейка B10). Следует учесть, что получатель В3 недополучит 100 м³ , т.к. именно этому получателю поставляет продукцию фиктивный завод.

4