Реферат: Математическое програмирование
Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):
При этом должна быть минимизирована целевая функция
Построим опорный план методом северо-западного угла:
Пункты отправления | Пункты назначения | Запасы | ||||
| В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 | |
Получили новую таблицу, для которой повторяем расчет потенциалов: