ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 816
Скачиваний: 2
3. Составим первый опорный план методом «минимальной стоимости».
В первую очередь заполняется ячейка с минимальной стоимостью. Это ячейки с нулевой стоимостью. Сравним максимально возможные поставки для этих ячеек: для ячейки
(1,5) x15 = min{20,70}= 20 , для ячейки (2,5) x25 = min{20,90}= 20 ,
для ячейки (3,5) x35 = min{20,60}= 20 . Так как для ячеек (1,5),
(2,5) и (3,5) эти значения равны, то произведем максимально возможную поставку в любую из них. Например, в ячейку (1,5) даем поставку, равную 20. В результате потребность фиктивного рынка сбыта удовлетворена, и последний столбец таблицы поставок выпадает из рассмотрения.
|
90 |
40 |
50 |
20 |
20 |
|
|
|
|
|
|
|
|
70 |
2 |
1 |
5 |
3 |
0 |
|
20 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
90 |
5 |
2 |
3 |
5 |
0 |
|
|
|
|||||
|
|
|
|
|
|
|
60 |
3 |
4 |
4 |
6 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В оставшейся таблице наименьшей стоимостью, равной 1, обладает ячейка (1,2). Поскольку на складе в наличии имеется 70-20 = 50 единиц товара, то мы можем полностью удовлетворить потребность 2-ого рынка сбыта, и 2-ой столбец выпадает из дальнейшего рассмотрения.
59
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
|
90 |
40 |
|
50 |
20 |
20 |
|
|
|
|
|
|
|
|
|
70 |
2 |
1 |
|
5 |
3 |
0 |
|
|
|
40 |
|
|
20 |
|
|
|
|
|
|
|
|
|
|
90 |
5 |
2 |
|
3 |
5 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
60 |
3 |
4 |
|
4 |
6 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее заполняем ячейку (1,1), т.к. она обладает наименьшей стоимостью перевозки, равной 2. Потребность 2- ого склада равна 90 единицам товара, но с 1-ого склада ранее были вывезены 40 единиц товара для 2-ого рынка сбыта и 20 единиц товара для 5-ого склада. Поэтому на 1-ый рынок сбыта мы можем поставить только 10 единиц товара, и товары, находившиеся в наличии 1-ого склада, полностью вывезены, т.е. 1-ая строка выпадает из дальнейшего рассмотрения.
|
90 |
40 |
50 |
20 |
20 |
70 |
2 |
1 |
5 |
3 |
0 |
10 |
40 |
|
|
20 |
|
90 |
5 |
2 |
3 |
5 |
0 |
|
|
|
|
|
|
60 |
3 |
4 |
4 |
6 |
0 |
|
|
|
|
|
В оставшейся таблице минимальными стоимостями (равной 3) обладают ячейки (2,3) и (3,1). Потребность 3-ого рынка сбыта равна 50 единицам товара, и 2-ой склад (его мощность составляет 90 единиц товара) может полностью её удовлетворить. Потребность 1-ого рынка сбыта равна 60
60
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
единицам товара, и 1-ый склад также может полностью её удовлетворить (оставшаяся мощность равна 90 - 10=80 единиц).
Максимально возможную поставку, равную 60 единицам, произведем в ячейку (1,3), тогда последняя строка выпадает из рассмотрения.
|
90 |
40 |
50 |
20 |
20 |
2 |
1 |
|
5 |
3 |
0 |
70 |
10 |
40 |
|
|
20 |
5 |
2 |
|
3 |
5 |
0 |
90 |
|
|
|
|
|
3 |
4 |
|
4 |
6 |
0 |
60 |
60 |
|
|
|
|
Рассуждая аналогичным образом, заполним оставшуюся часть распределительной таблицы. В результате получим:
|
90 |
40 |
50 |
20 |
20 |
|
|
|
|
|
|
2 |
|
1 |
5 |
3 |
0 |
70 |
10 |
40 |
|
|
20 |
|
|
|
|
|
|
5 |
|
2 |
3 |
5 |
0 |
90 |
20 |
|
50 |
20 |
|
|
|
|
|
|
|
3 |
|
4 |
4 |
6 |
0 |
6060
4.Проверим полученный опорный план на невырожденность.
Число заполненных ячеек распределительной таблицы равно 7. Для выполнения условия невырожденности плана
необходимо, чтобы число заполненных ячеек равнялось
61
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
m + n −1, где |
m – число поставщиков (складов), |
n – |
число |
|||||||
потребителей (рынков сбыта). |
|
|
|
|
|
|
|
|||
Для |
данной задачи значение |
m + n −1 = 7 |
совпадает |
с |
||||||
число заполненных ячеек. Таким образом, построенный |
||||||||||
опорный план является невырожденным. |
|
|
|
|
||||||
5. |
Определим |
потенциалы |
поставщиков |
Ui |
и |
|||||
потребителей V j . |
|
|
|
|
|
|
|
|
||
Потенциалы поставщиков и потребителей определяются |
||||||||||
для заполненных ячеек распределительной таблицы из |
||||||||||
уравнений |
Ui + V j = cij . При этом предполагается, |
что |
u1 ≡ 0 . |
|||||||
Потенциалы складов размещаются в крайнем правом углу, |
||||||||||
потенциалы |
рынков |
сбыта |
- |
в |
нижней |
строке |
||||
распределительной таблицы. |
|
|
|
|
|
|
|
|||
|
|
90 |
40 |
50 |
|
20 |
20 |
|
|
|
70 |
2 |
1 |
5 |
|
3 |
|
0 |
U1 |
|
|
|
10 |
40 |
|
|
|
20 |
|
|
|
|
90 |
5 |
2 |
3 |
50 |
5 |
20 |
0 |
U2 |
|
|
|
20 |
|
|
|
|
|
|
|||
60 |
3 |
4 |
4 |
|
6 |
|
0 |
U3 |
|
|
|
60 |
|
|
|
|
|
|
|
|
|
|
|
V1 |
V2 |
V3 |
|
V4 |
V5 |
|
|
|
Для определения потенциалов составляем уравнения: |
|
|||||||||
|
|
|
|
U1 + V1 = 2 |
|
|
|
|
||
|
|
|
|
U1 + V2 =1 |
|
|
|
|
||
|
|
|
|
U1 + V5 = 0 |
|
|
|
|
||
|
|
|
|
U2 +V1 = 5 |
|
|
|
|
||
|
|
|
|
U2 +V3 = 3 |
|
|
|
|
||
|
|
|
|
U2 +V4 = 5 |
|
|
|
|
||
|
|
|
|
U3 + V1 = 3 |
|
|
|
|
||
62
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com