Поскольку система содержит m+n-1уравнение и m+nнеизвестных, то один из потенциалов можно задать произвольно. После этого остальные неизвестные vjи ui- определяются однозначно.
Критерий оптимальности
Для того чтобы допустимый план транспортной задачи xi,j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы ui, vj, для которых
vj-ui=ci,j, если xi,j>0,
vj-ui≤ci,j, если xi,j=0
Вычислите коэффициенты изменения стоимости (dci,j) для незаполненных клеток плана: dci,j =vj- ui - ci,j;
Заметьте: если все dci,j оказались отрицательными, то полученный план оптимальный. Если есть хотя бы один положительный элемент dci,j, то далее ведущей (опорной) клеткой будет клетка [i,j] (при dci,j>0).
Для того чтобы найти новый план перевозок необходимо составить цикл пересчета.
Цикл пересчета представляет собой замкнутую ломаную линию, состоящую из горизонтальных и вертикальных линий, концы которых лежат в заполненных клетках. Ломаная начинается и заканчивается в опорной клетке. Узел в опорной клетке считается положительным, следующий - отрицательный, и так далее чередуясь. Берется минимальное по абсолютной величине значение в отрицательных клетках. Во всех отрицательных клетках это значение отнимается, в положительных прибавляется. Получили новый план перевозок.
Решение задачи
1. Определим модель задачи
b1+b2+b3+b4+b5+b6=230+220+130+170+190+110=1050
a1+a2+a3+a4+a5=240+360+180+120+150=1050
Так как Σai=Σbj, то модель задачи является закрытой.
2. Построим распределительную таблицу по методу северо-западного угла.
V1=8 V2=0 V3=5 V4=2 V5=1 V6=6
230 220 130 170 190 110
U1=0 240 150 90
U2=5 360 80 170 110
U3=4 180 180
U4=6 120 40 80
U5=9 150 40 110
3.Определяем целевую функцию Z для первого этапа по формуле
Z= ΣCij*Xij
Z1=90*5+150*8+80*13+170*7+110*6+180*4+40*6+80*7+40*14+110*15=8270
4.Определим потенциалы для заданных клеток, где U1=0 по формуле
Ui+Vj=Cij
5.определим оценки свободных клеток, исходя из условия:
Δij=Cij-( Ui+Vj)
Δ12=7 Δ35=5
Δ14=8 Δ36=1
Δ15=11 Δ41=0
Δ16=2 Δ43=1
Δ22=3 Δ44=5
Δ23=0 Δ46=2
Δ26=2 Δ51=-8
Δ31=0 Δ52=3
Δ33=2 Δ54=4
Δ34=3 Δ55=-2
Т.к среди оценок свободных клеток есть отрицательная оценка Δ51=-8 то решение является не оптимальным, значит, продолжаем решение задачи.
6.Для перехода к следующей итерации строим цикл по λ=min|Xij| по четным клеткам λ=min|150;40|=40
7.Определим целевую функцию для второго этапа
Z2=Z-λ|Xij|=8270-40*8=7950
V1=8 V2=0 V3=5 V4=2 V5=1 V6=14
230 220 130 170 190 110
U1=0 240 110 130
U2=5 360 80 170 110
U3=4 180 180
U4=6 120 40 80
U5=1 150 40 110
Экономическая интерпретация
Для достижения минимальной стоимости перевозок в размере 7210 ед. кирпича следует перевозить следующим образом:
1. От первого кирпичного завода кирпич в количестве 80 ед. был перевезен к первому строящемуся объекту. В количестве 130 ед. был перевезен к третьему строящемуся объекту. В количестве 30 ед. был перевезен к шестому строящемуся объекту.
2. От второго кирпичного завода кирпич в количестве 170 ед. был перевезен к четвертому строящемуся объекту. В количестве 190 ед. был перевезен к пятому строящемуся объекту.
3. От первого кирпичного завода кирпич в количестве 100 ед. был перевезен ко второму строящемуся объекту. В количестве 80 ед. был перевезен к шестому строящемуся объекту.
4. От четвертого кирпичного завода кирпич в количестве 120 ед. был перевезен ко второму строящемуся объекту.
5. От пятого кирпичного завода кирпич в количестве 150 ед. был перевезен к первому строящемуся объекту.
Характеристика программы оптимизации
Для вызова программы оптимизатора необходимо выбрать команду меню Сервис→Поиск решения. Если команда Поиска решения отсутствует в меню Сервис, то надо установить эту настройку.
Для установки программы Поиск решения необходимо в меню Сервис выбрать команду Настройки. Далее в диалоговом окне Настройки необходимо установить флажок Поиск решения. Надстройка, останется активной до тех пор, пока она не будет удалена.
Для обработки таблицы Excel оптимизатором, необходимо вызвать его диалоговое окно Поиск решения и построить экономико-математическую модель. Отличие экономико-математической постановки задачи оптимизации в табличном процессоре от традиционной экономико-математической постановки состоит в том, что в формулах задаются не символьные обозначения переменных и параметров, а координаты ячеек таблицы, в которых хранятся эти переменные. Excel позволяет писать в формулы символьные имена ячеек, но программа Поиск решения в 70% случаев имена не воспринимает, приходится использовать координатные ссылки на ячейки.
Окно Поиск решения вызывается командой меню Сервис→Поиск решения.
Поле «Установить целевую ячейку» служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.
Кнопка «Равной» служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить заданное число необходимо ввести его в поле.
Поле «Изменяя ячейки» служит для указания ячеек, значение которого изменяется в процессе Поиска решения до тех пор, пока не будут выполняться наложенные ограничения и условия оптимизации значения ячейки вводятся имена или адреса изменяемых ячеек, разделяя их запятыми, Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
Поле «Предложить» используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.
Поле «Ограничения» служит для отображения списка граничных условий поставленной задачи. Команда Добавить служит для отображения диалогового окна Добавить ограничения.
Команда «Изменить» служит для отображения диалогового окна Изменение ограничения.
Команда «Удалить» служит для снятия указанного курсором ограничения.
Команда «Выполнить» служит для запроса поиска решения поставленной задачи.
Команда «Закрыть» служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Параметры», «Добавить», «Изменить» или «Удалить».
Команда «Параметры» служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Кнопка «Восстановить» служит для очистки полей окна диалогового и восстановления значений параметров поиска решения, используемых по умолчанию.
Поиск решения предоставляет возможность сохранения вариантов моделей и быстрой их загрузки. Для этого необходимо выполнить следующие действия:
1. В меню Сервис выбрать команду Поиск решения
2. Нажать кнопку «Параметры».
3. Нажать кнопку «Сохранить модель». Появится окно сохранить модель.
4. В поле «Задайте область модели» введите ссылку на верхнюю ячейку столбца, в котором нужно разместить модель оптимизации.
Значение элементов управления диалоговых окон «Поиска решения» и «Параметры» поиска решения записываются на лист. Чтобы использовать на листе несколько моделей оптимизации, нужно сохранить их в разных диапазонах.
Предлагаемый диапазон содержит ячейку для каждого ограничения. Можно также ввести ссылку только на верхнюю ячейку столбца, в котором следует сохранить модель.
Диалоговое окно «Загрузить модель» используется для задания ссылки на область загружаемой модели оптимизации. Ссылка должна адресовать область модели целиком, недостаточно указывать только первую ячейку.
Для запуска оптимизатора нужно нажать на кнопку «Выполнить» в окне «Поиск решения».
Чтобы прервать поиск решения, нужно нажать клавишу Esc.
Инструкция по выполнению
Для того чтобы решить исходную задачу с использованием программы оптимизатора табличного процессора MSExcel необходимо выполнить следующие действия:
1. Создать исходную таблицу.
2. В меню Сервис выбрать команду Поиск решения.
3. Откроется диалоговое окно «Поиск решения».
4. В поле «Установить целевую ячейку» выбрать ячейку В18.
5. В поле «Равной» нажимать на кнопку минимальному значению.
6. В поле «Изменяя ячейки» ввести имена или адреса изменяемых ячеек, разделяя их запятыми. В моем примере введен диапазон ячеек $C$4; $E$7, содержащий искомые величины плана производства продукции. Изменение ячеек должна быть прямо или косвенно связана с целевой ячейкой.
7. Поле «Ограничения» служит для отображения списка граничных условий поставленной задачи. В исходной задаче это следующее ограничение.
1) $В$4:$В$7>=$В$13:$В$16 - количество перевозимой продукции не может превышать производственных возможностей филиалов.
2) $С$11:$Е$11>=$С$9:$Е$9 – количество доставляемой продукции не должна быть меньше потребностей потребителей.
3) $С$4:$Е$7>=0 – число перевозок не может быть отрицательным.
8. Далее необходимо сохранить модель. Для этого:
а) В меню Сервис выбрать команду Поиск решения
б) Нажать кнопку параметры.
в) В поле «Задайте область модели» ввести ячейку столбца, в котором хотим разместить модель оптимизации.
9. В окне «Параметры поиска решения» нажать на кнопку ОК. А в окне «Поиск решения» щелкнуть по кнопке Выполнить, чтобы получить решение данной задачи.
10. После чего появится окно «Результаты поиска решения». В этом окне будет написано «Решение найдено». Все ограничения и условия оптимальности выполнены, нажав на кнопку «Сохранить найденное решение». Закрыть данное окно при помощи кнопки ОК.