Similar presentations:
Основная идея метода решения транспортной задачи по критерию стоимости
1. Основная идея метода решения транспортной задачи по критерию стоимости
Выполнил: Попова Д., С-18412. Формулировка
Имеется М пунктов отправления (производства) А1, А2,…,Аm, в которых расположены запасы некоторого однородного
продукта (груза). Объем этого продукта Аi составляет аi
единиц. Кроме того имеется n пунктов потребления В1, В2,…,
Вn. Объем потребления в пункте Вj составляет bj единиц.
Предполагается, что из каждого пункта отправления
возможна транспортировка продукта в любой пункт
потребления. Известна также стоимость cij перевозки
единицы продукта из пункта Аi в пункт Вj.
Требуется составить такой план перевозок, при котором все
заявки пунктов потребления полностью выполнялись бы
пунктами отправления, а общая стоимость перевозок
(суммарные транспортные издержки) была бы минимальной.
3.
ПППО
В1
В2
…
Вn
Запасы
ai
А1
c11
c12
…
c1n
a1
А2
c21
c22
…
с2n
a2
…
…
…
…
…
…
Аm
cm1
cm2
…
cmn
am
Заявки
Bj
b1
b2
bn
4. Целевая функция
Функция должна иметь минимальное значение, илистремиться к минимуму
5. Необходимые условия
6. План транспортной задачи
7. Пример
На складах A1, A2, A3 имеются запасы продукции вколичествах 180,300, 120 т. соответственно.
Потребители B1,B2,B3 должны получить эту
продукцию в количествах 110, 350, 140 т.
соответственно. Найти такой вариант прикрепления
поставщиков к потребителям, при котором сумма
затрат на перевозки была бы минимальной. Расходы
по перевозке 1 т. продукции заданы матрицей С
(ден. ед.)
8.
9.
110+350+140=600180+300+120=600
закрытый тип Т-задачи
10.
• Построим первый опорныйплан.
F(X)=40*2+140*2+300*7+50*6+70*3
• Выбираем наименьший
=2970(ед.)
тариф стоимости перевозки,
отправляем столько, сколько
может вместить потребитель.
11.
• На складах A1, А2, А3 имеются запасы продукции вколичествах 90, 400, 110 т соответственно. Потребители
В1, В2, B3 должны получить эту продукцию в количествах
140, 300, 160 т соответственно. Найти такой вариант
прикрепления поставщиков к потребителям, при котором
сумма затрат на перевозки была бы минимальной.
Расходы по перевозке 1 т продукции заданы матрицей
(усл. ед.)