Постановка транспортной задачи по критерию стоимости в матричной форме
В m пунктах отправления 
сосредоточен однородный груз в количествах соответственно 
единиц. Имеющийся груз необходимо доставить потребителям 
, спрос которых выражается величинами 
единиц. Известна стоимость 
перевозки единицы груза из 
-го ( 
) пункта отправления в 
-й ( 
) пункт назначения.
Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.
Для наглядности, условие транспортной задачи (ТЗ) можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ (см. таблицу 14).
Таблица 14
| Поставщик | Потребитель | Запас груза 
| |||
| 
| ... | 
| ||
| 
| 
| ... | 
| 
|
| 
| 
| ... | 
| 
|
| ... | ... | ... | ... | ... | |
| 
| 
| ... | 
| 
|
Потребность в грузе 
| 
| 
| ... | 
| |
Для построения экономико-математической модели ТЗ введем переменные 
– количество груза, которое необходимо доставить из -го пункта отправления в 
-й пункт назначения.
Матрицу 
будем называть матрицей перевозок.
Цель ТЗ - минимизировать общие затраты на реализацию плана перевозок, следовательно, целевая функция будет иметь вид:
(3.1)
Составим систему ограничений, которая будет определять ОДР данной задачи в случае, когда 
.
|
|
|
Первые m уравнений системы (3.2) – это ограничения на запас груза у поставщиков, следующие n уравнений системы (3.2) – это ограничения на потребности потребителей в грузе, неравенства системы – это ограничения на смысл переменных (количество груза не может быть отрицательным).
(3.2)
Будем называть план перевозок
допустимым, если он удовлетворяет системе ограничений (3.2).
Допустимый план перевозок, доставляющий минимум целевой функции, называется оптимальным.
Закрытая и открытая модели транспортной задачи
Модель ТЗ называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, то есть выполняется равенство:
.
Если для транспортной задачи выполняется одно из условий:
, (3.3)
, (3.4)
то модель задачи называют открытой (несбалансированной).
Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую модель.
Так, при выполнении условия (3.3) необходимо ввести фиктивный (n+1)-й пункт назначения 
, то есть в матрице задачи добавляется столбец. Спрос фиктивного потребителя полагают равным небалансу, то есть 
, а стоимость перевозок равной нулю, то есть 
. Переменные 
– это количество груза, которое останется в i-ом пункте отправления. Аналогично при выполнении условия (3.4) вводится фиктивный поставщик 
, то есть в матрице задачи добавляется строка. Запас груза фиктивного поставщика равен: 
, а тарифы (стоимости перевозок) равны нулю, то есть 
. Переменные 
– это количество груза, недостающее j-му пункту назначения.
|
|
|
При преобразовании открытой модели задачи в закрытую модель, целевая функция не изменяется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
Целевая функция (3.1) и система ограничений (3.2) являются экономико-математической моделью сбалансированной ТЗ.
Дата добавления: 2018-09-20; просмотров: 336; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!