Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – А условных единиц, второй – В условных единиц, третий – С условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны Д, Е и К условных единиц, соответственно. Необходимо определить наиболее дешевый вариант перевозок, если транспортные расходы на одну условную единицу составляют:
Поставщик Потребитель Запасы
B1 B2 B3
A1 7
9
11
150
A2 4
5
8
150
A3 6
7
12
150
Потребность 50 300 100
Часть выполненной работы
Строим для этой клетки цикл, помечая клетки цикла знаками “плюс” и “минус”.
Поставщик Потребитель Запасы
B1 B2 B3
A1 + 7
M
– 9
50 M
11
100 M
150
A2 – 4
50 M
+ 5
100 M
8
M
150
A3 6
M
7
150 M
12
M
150
Потребность 50 300 100
Перемещаем по циклу груз величиной в 50 единиц, прибавляя эту величину к грузу в клетках со знаком “плюс” и отнимая ее от товара в клетках со знаком “минус”.В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы
B1 B2 B3
A1 7
50 M
9
M
11
100 M
150
A2 4
M
5
150 M
8
M
150
A3 6
M
7
150 M
12
M
150
Потребность 50 300 100
Целевая функция F= 3250
Значение целевой функции изменилось на 50 единиц по сравнению с предыдущим этапом.
Этап 3
Опорный план является вырожденным, так как число занятых клеток, удовлетворяющих условию 0 < Xi,j < Di,j меньше, чем m+n-1=5.
Перечислим эти клетки:(1,1) (1,3) (2,2) (3,2)
Сделаем план невырожденным, добавляя (в случае Xi,j = 0) или отнимая (в случае Xi,j = Di,j) бесконечно малые, не равные между собой фиктивные перевозки e, 2e, 3e… в клетки с координатами (i,j): (2,1)
Введение в план фиктивных перевозок необходимо для избежания зацикливания в ходе решения задачи. При их введении будем модифицировать потребности/запасы товара соответствующих потребителей/поставщиков для сохранения баланса между запасами/потребностями
Поставщик Потребитель Запасы
B1 B2 B3
A1 7
50 M
9
M
11
100 M
150
A2 4
e M
5
150 M
8
M
150+e
A3 6
M
7
150 M
12
M
150
Потребность 50+e 300 100
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.Потенциалы Ui:U1=0V1=C1,1-U1= 7V3=C1,3-U1= 11U2=C1,2-V1= -3V2=C2,2-U2= 8U3=C2,3-V2= -1Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.Для случая Xi,j = Di,…
Купить уже готовую работу
Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут .
