Проверим необходимое и достаточное условие разрешимости
задачи
Потребность в грузе равна запасам груза задача закрытая, следовательно,
имеет единственное решение.
Используя метод наименьшей стоимости заполним таблицу.
Среди тарифов наилучшим является и . Направим например,
в клетку
в клетку
в клетку
в клетку
в клетку
в клетку
в клетку
Запасы поставщиков исчерпаны, запросы потребителей
удовлетворены полностью. В результате получили первый опорный план. Подсчитаем
число занятых клеток таблицы их 7, а должно быть опорный план не вырожденный.
Определим значение целевой функции первого опорного плана
Проверим оптимальность плана.
Найдём потенциалы и по занятым клеткам таблицы
Пусть , тогда:
Подсчитаем оценки свободных клеток
Первый опорный план не является оптимальным так как .
Переходим к его улучшению. Для клетки строим цикл перераспределения
В результате получили новый опорный план
|
60
|
50
|
85
|
75
|
65
|
8
|
10
|
6
|
5
65
|
80
|
4
55
|
3
25
|
5
|
9
|
35
|
11
|
4
25
|
4
|
8
10
|
90
|
5
5
|
5
|
3
85
|
6
|
Определим значение целевой функции
Проверим оптимальность плана
Подсчитаем оценки свободных клеток
План близок к оптимальному.
При дальнейшем перераспределении груза, задача входит в
циклическую фазу, план не улучшается. Таким образом, полученное решение
является наиболее оптимальным для нашей задачи
Страницы: 1, 2, 3, 4
|