Разработка оптимального плана поставок
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
я, таким образом, заполним транспортную таблицу перевозками Xi,j до конца.
Таблица 2
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 40 15 30 18 - 0 15 - 20 - 18 70A 2 - 25 - 30 - 20 20 12 40 16 20 22 80A 3 - 20 - 25 - 18 - 20 - 18 50 25 50A 4 - 18 - 20 50 15 - 16 10 15 - 60Заявки 403050 20 50 70 260
Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу - заявке соответствующего пункта назначения. Значит, все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и выражается числом 260, стоящим в правом нижнем углу таблицы).
В таблицах будем проставлять отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем свободными. Проверим, является ли план перевозок, данный в таблице -----, опорным. Число свободных клеток с нулевыми перевозками равно (4-1)(6-1)=3*5=15, так что план опорный.
Общие затраты для этого плана составят:
L1= 15 * 40 + 18 * 30 + 12 * 20 + 16 * 40 + 22 * 20 + 25 * 50 + 15 * 50 + 15 * 10 = 4610 у.е.
2.4 Оптимизация задачи методом отрицательных циклов
Этот план можно улучшить, если произвести в нем циклическую перестановку перевозок между клетками таблицы, уменьшив перевозки в дорогой клетке (3.6) со стоимостью 25, но зато увеличив перевозки в дешевой (3.5) со стоимостью 18.
Таблица 3
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 40 15 30 18 - 0 15 - 20 - 18 70A 2 - 25 - 30 - 20 20 12 40 16 20 22 80A 3 - 20 - 25 - 18 - 20 - 18 50 25 50A 4 - 18 - 20 50 15 - 16 10 15 - 60Заявки 403050 20 50 70 260
Чтобы план оставался опорным, необходимо сделать одну из свободных клеток базисной, а одну из базисных - свободной. По циклу (3.5) -> (2.5) -> (2.6) -> (3.6) можно перенести не более 40 единиц груза.
Таким образом, стоимость перевозок уменьшилась на 18-25+22-16=-1*40=-40
L2=4610+ (-40) =4570у.е.
Таким образом, продолжим улучшать план перевозок путем перемещения груза из более дорогих клеток в более дешевые.
Таблица 4
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 40 15 30 18 - - 15 - 20 - 18 70A 2 - 25 - 30 - 20 20 12 16 60 22 80A 3 - 20 - 25 - 18 - 20 40 18 10 25 50A 4 - 18 - 20 50 15 - 16 10 15 - 60Заявки 403050 20 50 70 260
Таким образом, переносим 10 единиц груза из более дорогой клетки, в более дешевую, при этом цена цикла уменьшится и будет равна:
-25+18-15=-2*10=-20 L3=4570+ (-20) =4550у.е;
Еще раз улучшим план стоимости перевозок.
Таблица 5
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 30 15 30 18 - 15 - 20 10 18 70A 2 - 25 - 30 - 20 20 12 - 16 60 22 80A 3 10 20 - 25 - 18 - 20 40 18 - 25 50A 4 - 18 - 20 50 15 - 16 10 15 - 60Заявки 403050 20 50 70 260
В результате этого циклического переноса мы переносим из более дорогих клеток 30 единиц груза в более дешевые.
Таким образом, цена цикла становится равна:
16-22+18-15+20-18=-1*30=-30 L4=4550+ (-30) =4520 у.е.
Таблица 6
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 - 15 30 18 - 15 - 20 40 18 70A 2 - 25 - 30 - 20 20 12 30 16 30 22 80A 3 40 20 - 25 - 18 - 20 10 18 - 25 50A 4 - 18 - 20 50 15 - 16 10 15 - 60Заявки 403050 20 50 70 260
Улучшим план поставок.
Таблица 7
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 - 15 20 18 - 15 - 20 50 18 70A 2 - 25 - 30 - 20 20 12 40 16 20 22 80A 3 40 20 - 25 - 18 - 20 10 18 - 25 50A 4 - 18 10 20 50 15 - 16 - 15 - 60Заявки 403050 20 50 70 260
Цена цикла будет равна:
-15+16-22+18-18=-1*10=-10=4520+ (-10) =4510 у.е.
Таблица 8
Заводы БензохранилищаЗапасыB 1 B 2 B 3 B 4 B 5 B 6 A 1 - 15 10 18 - 15 - 20 60 18 70A 2 - 25 - 30 - 20 20 12 50 16 10 22 80A 3 40 20 - 25 10 18 - 20 - 18 - 25 50A 4 - 18 20 20 40 15 - 16 - 15 - 60Заявки 403050 20 50 70 260
Цена цикла будет равна:
-18+16-22+18-18+20-15=-1*10=-10=4510+ (-10) =4500 у.е.
В данной таблице отрицательные циклы отсутствуют, следовательно, данное решение будет являться оптимальным.
Оптимальная стоимость плана составит 4500 у.е.
2.5 Проверка решения задачи с использованием системы Mathcad
Критерий оптимизации - целевая функция
Y(X1,1,X1,2,X1,4,X1,5,X1,6,X2,1,X2,2,X2,3,X2,4,X2,5,X2,6,X3,1,X3,2,X3,3,X3,4,X3,5,X3,6,X4,1,X4,2,X4,3,X4,4,X4,5):=15X1,1+18X1,2+15X1,4+20X1,5+18X1,6+25X2,1+30X2,2+20X2,3+12X2,4+16X2,5+22X2,6+20X3,1+25X3,2+18X3,3+20X3,4+18X3,5+25X3,6+18X4,1+20X4,2+15X4,3+16X4,4++15X4,5;
Начальные приближения
X1,1:=0 X1,2:=0 X1,4:=0 X1,5:=0 X1,6:=0
X2,1:=0 X2,2:=0 X2,3:=0 X2,4:=0 X2,5:=0 X2,6:=0
X3,1:=0 X3,2:=0 X3,3:=0 X3,4:=0 X3,5:=0 X3,6:=0
X4,1:=0 X4,2:=0 X4,3:=0 X4,4:=0 X4,5:=0
Given
Система ограничений
X1,1+X1,2+X1,4+X1,5+X1,6=70,
X2,1+X2,2+X2,3+X2,4+X2,5+X2,6=80,
X3,1+X3,2+X3,3+X3,4+X3,5+X3,6=50,
X4,1+X4,2+X4,3+X4,4+X4,5=60;
X1,1+X2,1+X3,1+X4,1=40,
X1,2+X2,2+X3,2+X4,2=30,
X2,3+X3,3+X4,3=50,
X1,4+X2,4+X3,4+X4,4=20,
X1,5+X2,5+X3,5+X4,5=50,
X1,6+X2,6+X3,6=70;
Граничные условия
X1,1?0 X1,2?0 X1,4?0 X1,5?0 X1,6?0
X2,1?0 X2,2?0 X2,3?0 X2,4?0 X2,5?0 X2,6?0
X3,1?0 X3,2?0 X3,3?0 X3,4?0 X3,5?0 X3,6?0
X4,1?0 X4,2?0 X4,3?0 X4,4?0 X4,5?0
Найти оптимальное решение
X1,1,2,4,5,6,1,2
X2,3 := Minimize(Y, X1,1,X1,2,X1,4,X1,5,X1,6,X2,1,X2,2,X2,3,X2,4,X2,5,X2,6,X3,1,X3,2,
X2,4X3,3,X3,4,X3,5,X3,6,X4,1,X4,2,X4,3,X4,4,X4,5);
X2,5,6,1,2,3,4,5,6,1,2,3,4,5
X1,1 0,2 10,4 0,5 0
X1,660,10,20
X2,30
X2,420,550
X2,6 = 10
X3,140
X3,2 0
X3,310,40,50,604,10
X4,220
X4,340
X4,40
X4,50
Определить величину целевой функции для оптимального решения
план поставка оптимизация задача
Y(X1,1,X1,2,X1,4,X1,5,X1,6,X2,1,X2,2,X2,3,X2,4,X2,5,X2,6,X3,1,X3,2,X3,3,X3,4,X3,5,X3,6,X4,1,X4,2,X4,3,X4,4,X4,5) = 4500 у.е;
Заключение
Оптимальное распреде