Открытая транспортная задача.
а) - — излишек продукта
Способ сведения к замкнутой задаче. Пусть — величина избытка продукции, т.е. - штраф за единицу продукта, не реализованного в пункте i; уi — количество продукта, не реализованного в пункте i.
Замкнутая транспортная задача имеет вид
, (1.11)
, , (1.12)
, , (1.13)
, (1.14)
уi ; . (1.15)
б) — дефицит продукта.
Способ сведения к замкнутой задаче. Пусть — величина дефицита продукции, т.е. - штраф за единицу продукта, недопоставленного в пункт j; — количество продукта, недопоставленного в пункту.
Замкнутая транспортная задача имеет вид
, (1.16)
, , (1.17)
, , (1.18)
, (1.19)
; . (1.20)
3. Транспортная задача с запретами. Пусть Е — множество пар индексов (ij), таких, что из пункта i в пункт j допускается транспортировка продукта. Между любыми другими двумя пунктами транспортировка не допускается.
Пусть М— большое число, например
, , .
Тогда в оптимальном плане транспортной задачи при ограничениях (1.8)—(1.10) = 0, .
4. Транспортная задача с фиксированными перевозками. Если объем перевозок между пунктами и задан, то в задаче (1.7)—(1.10) вводится дополнительное ограничение: где — заданный объем перевозок.
5. Транспортная задача с ограничениями на пропускную способность. Если объем перевозок из пункта i в пункт j ограничен величиной , то в задаче (1.7)—(1.10) вводится дополнительное ограничение:
6. Транспортная задача с фиксированными доплатами. Предположим, что в открытой транспортной задаче имеет место дефицит продукта и для его устранения в пунктах возможно создание новых мощностей .
Пусть переменные , если в пункте вводятся мощности di и , если в пункте i мощности не вводятся. Издержки на ввод мощностей d, в пункте i (i = n + 1, ..., k)составляют иi.
С учетом возможности создания новых мощностей транспортная задача может быть записана в следующем виде:
, (1.21)
, , (1.22)
, , (1.23)
, , (1.24)
; . (1.25)
Здесь (1.21)— целевая функция (минимум затрат на транспортировку и ввод мощностей);
(1.22) — ограничения по величине предложения в каждом существующем пункте производства;
(1.23) — ограничения по величине предложения в каждом новом пункте производства;
(1.24) — ограничения по величине спроса в каждом пункте потребления;
(1.25) — условия неотрицательности объемов перевозок.
Помимо непрерывных переменных в модель включены булевы переменные . Задача (1.21)— (1.25) является задачей линейного программирования со «смешанными» переменными.
Все приведенные модели описывают транспортную задачу в виде задачи линейного программирования. В такой форме она может быть решена стандартными средствами линейного программирования, например симплекс-методом.
Для решения транспортной задачи могут быть использованы также и менее трудоемкие (по объему вычислений) алгоритмы, например метод потенциалов.
Большинство специальных алгоритмов решения транспортной задачи использует исходную информацию в форме транспортной таблицы:
Таблица 1.1
Пункт потребления Пункт производства | … | j | ... | m | Пред- ложе- ние | ||
… | ... | ||||||
… | ... | ||||||
… | ... | ... | ... | ... | ... | ... | ... |
i | … | ... | |||||
... | ... | ... | ... | ... | ... | ... | ... |
n | … | ... | |||||
Спрос | ... | ... |
Оптимальный план перевозок имеет вид
Таблица 1.2
Пункт потребления Пункт производства | … | j | ... | m | ||
… | ... | |||||
… | ... | |||||
… | ... | ... | ... | ... | ... | ... |
i | … | ... | ||||
... | ... | ... | ... | ... | ... | ... |
n | … | ... |
Пример 2.Задача организации оптимального снабжения.
Три фермерских хозяйства , , ежедневно могут доставлять в город соответственно 180, 220 и 100 ц молока для обеспечения пяти торговых точек: , , , , .Стоимость перевозки 1 ц молока и потребности торговых точек в молоке указаны в табл. 1.3.
Таблица 1.3
.
Фермерские хозяйства | Затраты на перевозку 1ц к торговым точкам | Запас молока, ц | ||||
Потребности в молоке, ц |
Определить оптимальный план поставки молока в каждую точку для удовлетворения потребностей, чтобы суммарные транспортные издержки были минимальными.
Решение. Так как целевая функция и неравенства-ограничения линейны, эта задача является задачей линейного программирования. Данная задача является транспортной задачей закрытого типа, так как запасы молока у поставщиков (фермерских хозяйств) равны потребностям в молоке у торговых точек. Для задачи открытого типа меняется изменяется вид системы ограничений.
Математическая модель задачи
Переменные: ; ) — количество молока, поставляемое -м фермерским хозяйством в -ю торговую точку.
Целевая функция — суммарные транспортные издержки, которые необходимо минимизировать:
Функциональные ограничения:
• по поставщикам
,
•по потребителям
Прямые ограничения: .
1.Укажем адреса ячеек, в которые будет помещен результат решения. Изменяемые ячейки — B11:F13. В эти ячейки в результате решения задачи будут записаны оптимальные значения .
2.Введем исходные данные. Введите исходные данные задачи, как показано на рис. 1.14.
Рис. 1.14. Введены исходные данные
3. Введем зависимости для ограничений. Сначала введем условия реализации мощностей поставщиков:
где — мощность поставщика ; — объем поставки груза от поставщика к потребителю ; — количество потребителей.
· Поместим курсор в ячейку G11.
· Выберем функцию СУММ.
· Выделим необходимые для суммирования ячейки B11:F11.
· Нажмем кнопку ОК для подтверждения ввода формулы для суммирования
Содержимое ячейки G11 скопируем в ячейки G12, G13.
Затем введите условия удовлетворения запросов потребителей:
где — мощность потребителя у; — количество поставщиков.
· Поместим курсор в ячейку В14.
· Выберем функцию СУММ.
· Выделим необходимые для суммирования ячейки В11: В13.
· Нажмем кнопку ОК для подтверждения ввода формулы для суммирования.
Содержимое ячейки В14скопируем в ячейки С14 и F14.
4.Введем зависимость для целевой функции. Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, зарезервируем ячейку и введем формулу для ее вычисления:
, где — стоимость доставки 1 ц молока от поставщика к потребителю .
· Поместим курсор в ячейку G14 (после решения задачи в данной ячейке будет находиться значение целевой функции).
· Запускаем Мастер функций (значок fx). ■
· В окне Категория выбираем Математические.
· В окне Функция выбираем СУММПРОИЗВ.
· Нажимаем кнопку ОК.
· В окне СУММПРОИЗВ укажем адреса массивов, элементы которых обрабатываются этой функцией.
В нашей задаче целевая функция представляет собой произведение затрат на доставку молока (ячейки B3:F5) и объемов поставок для каждого потребителя (содержимое ячеек В11:F13).
· В поле Массив 1 указываем адреса B3:F5. В поле Массив 2 укажите адреса B11:F13.
· Нажимаем кнопку ОК — подтверждение окончания ввода адресов массивов.
В поле ячейки G14 появится некоторое числовое значение, равное произведению поставок на коэффициенты затрат по доставке грузов (в данной задаче — это число 0, рис. 1.15).
Рис. 1.15. Создана форма для решения задачи, введена зависимость для целевой функции
На рис. 1.16 отражены введенные формулы.
Рис. 1.16. Вид введенных формул
5. Запускаем команду Поиск решений.
6. Назначаем ячейку для целевой функции.
Поместим курсор в окно Установить целевую ячейку.
Введем адрес ячейки $G$14 (рис. 1.17).
Введем тип целевой функции. Для этого отметим, чему равна целевая функция — Минимальному значению.
7.Вводим ограничения.
· Помещаем указатель мыши на кнопку Добавить. Появится диалоговое окно добавление ограничения.
Первая запись в группе Ограничения (см. рис. 1.17) представляет собой фиксированную перевозку, вторая запись - ограничения по уровню спроса, третья и четвертая запись- запрет на перевозки, пятая запись — ограничения по уровню запасов.
· После ввода всех ограничений нажимаем кнопку ОК.
Рис. 1.17. Введены все условия задачи