Автор: Пользователь скрыл имя, 16 Января 2013 в 08:13, задача
Задача :
У поставщиков A1 , A2 , A3 , A4 , находится соответственно 70 , 80 , 90 , 80 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 в количестве 60 , 40 , 120 , 100 единиц соответственно.
Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 4 , 8 , 1 , 6 ден.ед.
Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 3 , 5 , 3 , 4 ден.ед.
Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 2 , 6 , 4 , 3 ден.ед.
Стоимость доставки единицы продукции от поставщика A4 к указанным потребителям равна 1 , 4 , 5 , 3 ден.ед.
Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.
Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное решение. |
Ответ: |
X 1 опт = |
0 |
0 |
70 |
0 |
||
0 |
30 |
50 |
0 | |||
0 |
0 |
0 |
90 | |||
60 |
10 |
0 |
10 |
Smin = 1 * 70 + 5 * 30 + 3 * 50 + 3 * 90 + 1 * 60 + 4 * 10 + 3 * 10 = 770 |
Общие затраты на доставку всей продукции, для оптимального решения, составляют 770 ден. ед. |
Замечание: |
|
· Построим цикл для ячейки A2B4. |
Пусть ячейка A2B4, для которой мы строили цикл, имеет порядковый номер один. |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
Среди ячеек цикла A2B2 , A4B4 , номера которых четные, найдем ячейку, обладающую найменьшим значением. |
min = { 30, 10 } = 10 |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
Общие затраты на доставку всей продукции, по-прежнему, составляют S0 = 770 + 24 * 10 = 770 + 0 * 10 = 770 ден. ед. . |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
X 2 опт = |
0 |
0 |
70 |
0 |
||
0 |
20 |
50 |
10 | |||
0 |
0 |
0 |
90 | |||
60 |
20 |
0 |
0 |