Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Алгоритм:
Для базисного элемента ;
Для свободных и небазисных ;
Если вариант решения вырожденный, то от вырожденности избавляются (например при помощи заведения значащего нуля).
;
где - потенциал i-ой строки,
- потенциал j-го столбца.
;
Характеристика означает величину экономии ресурсов на единицу груза, полученную в результате перераспределения ресурсов в данную свободную клетку, поэтому может выступать в качестве дополнительного критерия оптимальности.
ПРАВИЛА ПОСТРОЕНИЯ КОНТУРА
1. Все углы контура прямые.
2. Одна вершина находится в клетке с максимальным элементом не оптимальности, все другие в базисных клетках
;
.
Рассмотрим пример варианта решения которого были получены ранее и в качестве начально допустимого варианта выберем план, полученный методом минимального элемента в матрице, так как при ?? Имеет наименьшую целевую функцию.
вj | |||||
аi | 3,2 | 1,0 | 2,4 | 3,0 | |
2,6 | з 4,3 | 3,6 | 4,3 | 12 р 5,6 | |
21 р 3,2 | 2,9 | 6,1 | 27 з 3,0 | ||
0,8 | 5,0 | 4,0 | 3,2 | 3,8 |
Рассчитываем потенциалы:
клетка 21:
;
клетка 24:
;
клетка 14:
;
клетка 12:
;
клетка 34:
;
клетка 33:
;
Рассчитаем характеристики для свободных клеток:
-
максимальный элемент неоптимальности плана при
Данный вариант решения не является оптимальным, т.к. присутствует положительная характеристика при .
На основании максимального элемента не оптимальности строим контур перераспределения ресурсов
вj | |||||
аi | 3,2 | 2,5 | 2,4 | 3,0 | |
1,1 | 4,3 | 3,6 | 4,3 | 5,6 | |
3,2 | 2,9 | 6,1 | 3,0 | ||
0,8 | 5,0 | 4,0 | 3,2 | 3,8 |
Рассчитываем потенциалы:
клетка 21:
;
клетка 11:
;
клетка 12:
;
клетка 24:
;
клетка 34:
;
клетка 14:
;
у.е.
Данный вариант решения является оптимальным, так как для всех i и j; F=Fopt
у.е.
Дата публикования: 2015-04-07; Прочитано: 226 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!