По критерию стоимости в матричной форме

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

Лекция 19.

Дыхательная система.

Большинство животных – аэробы. Диффузия газов из атмосферы посредством водного раствора осуществляется при дыхании. Элементы кожного и водного дыхания сохраняются даже в высших позвоночных животных. В ходе эволюции у животных возникли разнообразные дыхательные приспособления – производные кожи и пищеварительной трубки. Жабры и легкие – производные глотки.

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

Рассмотрим простейший вариант модели транспортной задачи (ТЗ), когда речь идет о рациональной перевозке некоторого однородного продукта от производителя к потребителям; при этом имеется баланс между суммарным спросом потребителей и возможностями поставщиков по их удовлетворению. Причем потребителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Так как от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы, возникает задача о наиболее рацио-нальном прикреплении, правильном направлении перевозок грузов, при котором потреб-ности полностью удовлетворяются, вся продукция от поставщиков вывозиться, а затраты на транспортировку минимальны.

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

Поставщики	Потребители	Запас груза, ai
B 1	B 2	…	Bn
A 1	c 11 x 11	c 12 x 12	…	c 1 n x 1 n	a 1
A 2	c 12 x 12	c 22 x 22	…	c 2 n x 2 n	a 2
…	…	…	…	…	…
Am	cm 1 xm 1	cm 2 xm 2	…	cmn xmn	am
Потребность в грузе, bj	b 1	b 2	…	bn

В m пунктах отправления A ₁, …, A_m сосредоточен однородный груз в количествах соответственно a ₁, …, a_m единиц. Имеющийся груз необходимо доставить потребителям B ₁, …, B_n, спрос которых выражается величинами b ₁, …, b_n единиц. Известна стоимость c_ij перевозки единицы груза из i -го пункта отправления в j -й пункт назначения. Удельные транспортные издержки (расходы) записывают в форме матрицы , которую называют матрицей тарифов. Требуется спланировать перевозки, т.е. указать, сколько единиц груза должно быть отправлено от i -го поставщика j -му потребителю, так, чтобы максимально удовлетворить спрос потребителей и чтобы суммарные транспортные затраты на перевозки были при этом минимальными. Рассмотрим простейший случай, когда суммарные запасы поставщиков равны суммарным потребностям

Для составления математической модели задачи введем переменные x_ij , обозначающие количество единиц груза, которые необходимо доставить из i -го пункта отправления в j -й пункт назначения. Все эти переменные можно записать в виде матрицы , которая будет называться матрицей перевозок:

.

Цель транспортной задачи – минимизировать общие затраты на реализацию плана перевозок, которые можно представить целевой функцией:

. (17.1.1.)

Переменные должны удовлетворять следующим условиям:

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

(17.1.2.)

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

(17.1.3.)

3) условия неотрицательности:

x_ij ³0 . (17.1.4.)

где c_ij – стоимость перевозки единицы груза из i -го пункта отправления в j -й пункт назначения;

- количество груза, сосредоточенного в пункте ;

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

Если план перевозок удовлетворяет ограничениям (17.1.2) – (17.1.4.), то такой план называется допустимым. Допустимый план перевозок, доставляющий минимум целевой функции называется оптимальным. В следующей теореме, которую примем без доказательства, введем критерий существования допустимого плана.

Теорема 17.1. (о существовании допустимого плана).

Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выпол-нение равенства

(17.1.5.)

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

.

Если для ТЗ выполняется одно из условий:

или ,

то модель задачи называется открытой.

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

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

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

Дата добавления: 2014-01-04