2015-06-30
635
Ai=(A1, A2, A3)=(250, 200, 200)
Bj=(B1, B2, B3, B4, B5)=(120, 130, 100, 160, 110)
D= 
Математическая постановка задачи приведена в таблице 2.1
В самую верхнюю левую клетку таблицы заносится максимально допустимая перевозка, при этом либо вывозится весь груз со станции А1 и все остальные клетки первой строки вычеркиваются, либо потребности первого потребителя B1 полностью удовлетворяются, тогда все клетки первого столбца вычеркиваются. После этого самой верхней левой клеткой становится клетка A1B2 или B2A1. Алгоритм продолжается до заполнения таблицы.
Таблица 2.1
Математическая постановка задачи
| B1 | B2 | B3 | B4 | B5 | Запросы | |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Потребности |
Проверил, является ли данная задача закрытой. Для этого считаю сумму запасов и сумму потребностей и сравним их:
250+200+200=120+130+100+160+110
Задача открытая, потому что сумма запасов не совпала с суммой потребностей.
Для того что бы сделать задачу закрытой смотрю на запасы - их больше, поэтому добавляю нулевого потребителя, с потребностью 30. Ищу не занятую клетку и ставим вместо прочерка ноль, показано в таблице 2.1.1.
|
|
|
Таблица 2.1.1.
| B1 | B2 | B3 | B4 | B5 | В6 | Запросы |
| A1 | |||||||
| A2 | |||||||
| A3 | |||||||
| Потребности |
Теперь задача закрытая.
На этом, математическая постановка задачи завершена.
2.2 Составление опорного плана методом северо-западного угла
Решение задачи методом северо-западного угла приведена в
таблице 2.2
Составляю опорный план методом северо-западного угла.
 |
Опорный план методом северо-западного угла
Таблица 2.2
| B1 | B2 | B3 | B4 | B5 | B6 | Запросы | αi | |
| A1 |   120
| - | - |   -
| - | |||
| A2 |  0
| - |  100
| - | - | -5 | ||
| A3 | - | - | - |  60
| -5 | |||
| Потребности | ||||||||
| βj |
Нахожу сумму произведения стоимостей и занятых клеток - нахожу Z0.
Z0=27*120+36*130+100*26+100*32+60*32+110*39+30*0=19930
Далее - нахожу потенциалы с помощью занятых клеток по формуле 1:
αi+ βj=Cij (1)
α1=0
α2=-5
α3=-5
β1=27
β2=36
β3=31
β4=37
β5=44
β6=5
Даю оценку свободным клеткам по формуле 2:
∆ij=(αi+ βj)-cij (2)
∆14=6
∆15=15
∆13=5
∆16=-4
∆22=9
∆25=4
∆26=0
∆31=-13
∆32=-11
∆33=-12
План не является оптимальным, так как ∆ij>0
Смотрю на клетку плана с самой положительной оценкой; строю замкнутую ломаную линию так, что одна ее вершина – это отмеченная свободная клетка. Все остальные вершины должны быть только в занятых клетках. Стороны этой ломаной или вертикальны или горизонтальны, они могут пересекаться, но точка пересечения вершиной не является. Эта ломанная называется многоугольником перераспределения или цыклом.
|
|
|
Каждый цикл имеет четное число вершин и ребер, то есть в таблице в каждой строке или столбце может находится только четное число клеток, содержащих вершины. Поэтому в клетках-вершинах можно менять значения перевозки так, что в сумма по строкам и столбцам не изменяется. вершины цикла, в которых увеличиваю перевозки «+», а в которых уменьшаю перевозки «-». Величин изменения обозначим ∆, ее буду перемещать по циклу. Максимальное значение ∆, на которое можно уменьшить перевозку, определяется условием неотрицательности перевозок.
Строю многоугольник перераспределения как показано на Рисунке 1 и Рисунке 2.
120 - 20 100
- +
+ -
0 100 100 -
+ -
60 110 160 10
Рисунок 1 Рисунок 2
 |
Начинаю с заполнения ячейки (1-1), пока не будет загружен 1-ый, склад ко 2-ому не переходим.
Потребители обслуживаются поочередно согласно их номеру.
2.3 Нахождение оптимального плана методом потенциалов
Первый план приведен в таблице 2.3
Первый план
Таблица 2.3
| B1 | B2 | B3 | B4 | B5 | B6 | Запросы | αi | |
| A1 |   20
|  130
| - | - | - | |||
| A2 |  100
|  -
| - | - | - | -5 | ||
| A3 | - | - | - | |||||
| Потребности | ||||||||
| βj | -10 |
Для построения 1-го плана найду число занятых клеток, оно равно 8.
Проверяю условие - число занятых клеток удовлетворяет этому условию.
Нахожу сумму произведения стоимостей и занятых клеток - нахожу Z1
Z1=540+4680+2900+2200+2600+5120+390=18430
Далее - нахожу потенциалы с помощью занятых клеток по формуле 1:
α1=0
α2=-5
α3=10
β1=27
β2=36
β3=31
β4=22
β5=29
β6= -10
Даю оценку свободным клеткам по формуле 2:
∆13= -4
∆14= -9
∆16= -10
∆22=8
∆24= -15
∆25= -11
∆26= -15
∆31=2
∆32=4
∆33=3
 |
План не является оптимальным, так как ∆ij>0
Строю многоугольник перераспределения как показано на Рисунке 3 и Рисунке 4.
20 130 120 30
+ - - +
- + + -
100 - - 100
Рисунок 3 Рисунок 4
Второй план приведен в таблице 2.4
Второй план
Таблица 2.4
| B1 | B2 | B3 | B4 | B5 | B6 | Запасы | αi | |
| A1 |   30
| - | - |  100
| - | |||
| A2 | - |  100
|  100
| - | - | - | -13 | |
| A3 | - | - |   -
| |||||
| Потребности | ||||||||
| βj | -10 |
Для построения 2-го плана найду число занятых клеток, оно равно 8.
Проверяю условие m+n-1=3+6-1=8, число занятых клеток удовлетворяет этому условию.
Нахожу сумму произведения стоимостей и занятых клеток – нахожу Z2
Z2=3240+1080+2900+2300+2600+5120+390=17630
Далее - нахожу потенциалы с помощью занятых клеток по формуле 1:
α1=0
α2= -13
α3=10
β1=27
β2=36
β3=39
β4=22
β5=29
β6= -10
Даю оценку свободным клеткам по формуле 2:
∆13= 4
∆14= 9
∆16= -10
∆21= -8
∆24= -23
∆25= -19
∆26= -23
∆31= 2
∆32= 4
∆33= 11
План не является оптимальным, так как ∆ij>0
Построю многоугольник перераспределения как показано на Рисунке 5 и Рисунке 6.
30 100 20 110
- +
+ -
100 100 110 90
+ -
- 10 10 -
Рисунок 7 Рисунок 8
 |
Третий план приведен в таблице 2.5
Третий план
Таблица 2.5
| B1 | B2 | B3 | B4 | B5 | B6 | Запасы | αi | |
| A1 |   20
|   -
| - | - | ||||
| A2 | - |  110
| - | - | - | -13 | ||
| A3 | - | - | - | -1 | ||||
| Потребности | ||||||||
| Βj |
Для построения 3-го плана найду число занятых клеток, оно равно 8.
Проверяю условие m+n-1=3+6-1=8, число занятых клеток удовлетворяет этому условию.
Z3=3240+720+3190+2530+2340+380+0=17520
Далее - нахожу потенциалы с помощью занятых клеток по формуле 1:
α1=0
α2= -13
α3= -1
β1= 27
β2= 36
β3= 39
|
|
|
β4= 33
β5= 29
β6= 1
Даю оценку свободным клеткам по формуле 2:
∆13= 4
∆14= 2
∆16= 1
∆21= -8
∆24= -12
∆25= -19
∆26= -12
∆31= -9
∆32= -7
∆35= -11
План не является оптимальным, так как ∆ij>0
Построю многоугольник перераспределения как показано на Рисунке 9 и Рисунке 10.
20 - - 20
- +
+ -
110 90 130 70
Рисунок 9 Рисунок 10
Четвертый план приведен в таблице 2.6
Четвертый план
Таблица 2.6
| B1 | B2 | B3 | B4 | B5 | B6 | Запасы | αi | |
| A1 | - | - | - | |||||
| A2 | - | - | - | - | -9 | |||
| A3 | - | - | - | |||||
| Потребности | ||||||||
| Βj |
Для построения 4-го плана найду число занятых клеток, оно равно 8.
Проверяю условие m+n-1=3+6-1=8, число занятых клеток удовлетворяет этому условию.
Z4=3240+700+3190+2990+1820+380+5120=17440
Далее - нахожу потенциалы с помощью занятых клеток по формуле 1:
α1= 0
α2= -9
α3= 3
β1= 27
β2= 32
β3= 35
β4= 29
β5= 29
β6= -3
Даю оценку свободным клеткам по формуле 2:
∆12= -4
∆14= -2
∆16= -3
∆21= -4
∆24= -12
∆25= -15
∆26= -12
∆31= -5
∆32= -7
∆35= -7
План оптимален, так как ∆ij<0
Задание выполнено.
