Математическое програмирование (стр. 2 из 3)
Построим опорный план методом северо-западного угла:
| Пункты отправления | Пункты назначения | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | 9 20 | 5 30 | 1 | 1 | 9 | 50 |
| А2 | 7 | 1 | 4 30 | 9 | 4 | 30 |
| А3 | 5 | 3 | 4 20 | 9 30 | 9 20 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 |
Принцип заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки (принцип северо-западного угла), количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился.
Построим систему потенциалов. Ui - потенциалы, соответствующие поставщикам, Vi- потенциалы, соответствующие потребителям.
Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.
| Пункты отправления | Пункты назначения | Запасы | |||||
| В1 | В2 | В3 | В4 | В5 | |||
| V1 =9 | V2=5 | V3=4 | V4=9 | V5=9 | |||
| А1 | U1 =0 | 9 20 | 5 30 | 1 | 1 | 9 | 50 |
| А2 | U2=0 | 7 | 1 | 4 30 | 9 | 4 | 30 |
| А3 | U3=0 | 5 | 3 | 4 20 | 9 30 | 9 20 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 | |
Проверим критерий оптимальности :
для свободных клеток. 
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (1 , 4). Перебросим в ячейку (1 , 4) 20 единиц груза из ячейки (1 , 1).
| Пункты отправления | Пункты назначения | Запасы | |||||
| В1 | В2 | В3 | В4 | В5 | |||
| V1 =9 | V2=5 | V3=4 | V4=9 | V5=9 | |||
| А1 | U1 =0 | 9 | 5 30 | 1 | 1 20 | 9 | 50 |
| А2 | U2=0 | 7 | 1 | 4 30 | 9 | 4 | 30 |
| А3 | U3=0 | 5 20 | 3 | 4 20 | 9 10 | 9 20 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 | |
Чтобы компенсировать недостаток в третьей строке, перебросим те же 20 единиц груза из ячейки (3 , 4) в ячейку (3 , 1).
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.
| Пункты отправления | Пункты назначения | Запасы | |||||
| В1 | В2 | В3 | В4 | В5 | |||
| V1 =5 | V2=5 | V3=4 | V4=1 | V5=9 | |||
| А1 | U1 =0 | 9 | 5 30 | 1 | 1 20 | 9 | 50 |
| А2 | U2=0 | 7 | 1 | 4 30 | 9 | 4 | 30 |
| А3 | U3=0 | 5 20 | 3 | 4 20 | 9 10 | 9 20 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 | |
Проверим критерий оптимальности :
для свободных клеток. 
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2 , 5). Перебросим в ячейку (2 ,5) 20 единиц груза из ячейки (1 , 2).
| Пункты отправления | Пункты назначения | Запасы | |||||
| В1 | В2 | В3 | В4 | В5 | |||
| V1 =5 | V2=5 | V3=4 | V4=1 | V5=9 | |||
| А1 | U1 =0 | 9 | 5 10 | 1 20 | 1 20 | 9 | 50 |
| А2 | U2=0 | 7 | 1 | 4 10 | 9 | 4 20 | 30 |
| А3 | U3=0 | 5 20 | 3 20 | 4 20 | 9 10 | 9 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 | |
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.
| Пункты отправления | Пункты назначения | Запасы | |||||
| В1 | В2 | В3 | В4 | В5 | |||
| V1 =2 | V2=5 | V3=1 | V4=1 | V5=1 | |||
| А1 | U1 =0 | 9 | 5 10 | 1 20 | 1 20 | 9 | 50 |
| А2 | U2=3 | 7 | 1 | 4 10 | 9 | 4 20 | 30 |
| А3 | U3=3 | 5 20 | 3 20 | 4 20 | 9 10 | 9 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 | |
Проверим критерий оптимальности :
для свободных клеток. 
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2 , 2). Перебросим в ячейку (2 ,2) 10 единиц груза из ячейки (1 , 2).
| Пункты отправления | Пункты назначения | Запасы | |||||
| В1 | В2 | В3 | В4 | В5 | |||
| V1 =2 | V2=5 | V3=1 | V4=1 | V5=1 | |||
| А1 | U1 =0 | 9 | 5 | 1 20 | 1 30 | 9 | 50 |
| А2 | U2=3 | 7 | 1 10 | 4 | 9 | 4 20 | 30 |
| А3 | U3=3 | 5 20 | 3 20 | 4 30 | 9 | 9 | 70 |
| Потребности | 20 | 30 | 50 | 30 | 20 | 150 | |
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.
