48824 (588614), страница 3
Текст из файла (страница 3)
Ячейка х33 , в которой находится это число, становится свободной в новой таблице метода потенциалов. Другие значения ячеек цикла в новой таблице получаются следующим образом: новое значение в минусовой ячейке равно: 
, новое значение в плюсовой ячейке равно: 
.
В полученной таким образом новой таблице ячейка 
становится свободной. После выполненных на этапе 5 преобразований получаем новое допустимое решение транспортной задачи с лучшим значением целевой функции F(x)=209.5. Этому допустимому решению соответствует новая таблица метода потенциалов, которая имеет следующий вид, таблица 2.7.
После получения таблицы 2.7 следует приступить к проверке условия получения оптимального решения (вторая итерация, этап 3).
Таблица 2.7. Метода потенциалов на
второй итерации
| F(x)=209,5 | 0 15 | 2 12 | 4 8,5 | 1 5,5 |
| 3 10 | 3 1 | 5 0,5 | 7 8,5 | 11 |
| 1 14 | 1 14 | 4 | 6 | 3 |
| 6 17 | 5 | 8 11,5 | 12 | 7 5,5 |
Для этого предварительно необходимо найти новые потенциалы пунктов производства и потребления. Для определения значений потенциалов следует решить следующую систему уравнений: {v1+u1=3, v1+u2=1, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=2, v3=4 v4=1, u1=3, u2=1 u3=6.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на второй итерации алгоритма будет иметь следующий вид, таблица 2.7.
Для выполнения этапа 4 на второй итерации алгоритма по формуле (2.11) необходимо последовательно рассчитать значения для свободных ячеек: 
11-3-1=-7, 
4-1-2=1,
6-1-4=1, 
3-1-1=1, 
5-6-0=-1, 
12-6-4=2.
Поскольку среди оценок свободных ячеек имеется единственная отрицательная, то условие (2.12) не выполняется, и найденное решение не является оптимальным, т.е. его можно улучшить. Для единственного значения 
соответствующая свободная ячейка для х31 помечается знаком (+), и для нее в таблице метода потенциалов строится цикл, содержащий занятые ячейки: х11, х12,х32. После этого следует перейти к выполнению действий этапа 5 второй итерации.
На этапе 5 необходимо определить плюсовые и минусовые ячейки. Поскольку ячейка для х31 имеет знак (+), то соседние с ней в цикле занятые ячейки х11 и х32 будут иметь знак (-). Следуя правилу чередования знаков, оставшаяся ячейка х12, будет иметь знак (+). Наименьшее из чисел в минусовых ячейках равно 1. Ячейка х11, в которой находится это число, становится свободной в новой таблице метода потенциалов. Другие значения ячеек цикла в новой таблице получаются следующим образом: новое значение в минусовой ячейке равно: x’32=x32-1=10.5, а новое значение в плюсовой ячейке равно: x’12=x12+1=1,5. В полученной таким образом новой таблице ячейка x’31=0 становится свободной. После выполненных на этапе 5 преобразований получаем новое допустимое решения транспортной задачи с лучшим значением целевой функции F(x)= 208.5. Этому допустимому решению соответствует новая таблица методов потенциалов, которая имеет следующий вид, таблица 2.8.
После получения таблицы 8 следует снова проверить условия получения оптимального решения (третья итерация, этап 3). Для этого необходимо найти новые потенциалы пунктов производства и потребления, т. е. решить следующую систему уравнений: {v1+u2=1, v1+u3=5, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=3, v3=5 v4=2, u1=2, u2=1 u3=5. На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на третьей итерации алгоритма будет иметь следующий вид , таблица 9.
После получения таблицы 2.8 следует снова проверить условия получения оптимального решения (третья итерация, этап 3).
Для этого необходимо найти новые потенциалы пунктов производства и потребления, т. е. решить следующую систему уравнений: {v1+u2=1, v1+u3=5, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=3, v3=5 v4=2, u1=2, u2=1 u3=5.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на третьей итерации алгоритма будет иметь следующий вид , таблица 2.9.
Таблица 2.8. Таблица метода потенциалов
после выполнения второй итерации
| F(x)=209,5 | V1 15 | V2 12 | V3 8,5 | V4 5,5 |
| u1 10 | 3 (-) | 5 1,5(-) | 7 8,5 | 11 |
| u2 14 | 1 14 | 4 | 6 | 3 |
| U3 17 | 5 1(+) | 8 10,5(-) | 12 | 7 5,5 |
Для выполнения этапа 4 на третьей итерации алгоритма по формуле (2.11) необходимо последовательно рассчитать значения оценок для свободных ячеек: 
3-2-0=1, 11-2-2=7, 4-1-3=0, 6-1-5=0, 3-1-2=0, 12-5-5=2. Поскольку среди оценок свободных ячеек отсутствуют отрицательные значения, то условие (2.12) выполняется, и найденное решение является оптимальным.
Таблица 2.9. Таблица метода потенциалов
на третьей итерации
| F(x)=209,5 | 0 15 | 3 12 | 5 8,5 | 2 5,5 |
| 2 10 | 3 | 5 1,5 | 7 8,5 | 11 |
| 1 14 | 1 14 | 4 | 6 | 3 |
| 5 17 | 5 1 | 8 10,5 | 12 | 7 5,5 |
Таким образом, искомое оптимальное решение исходной транспортной задачи, полученное с использованием описанного алгоритма метода потенциалов, содержится в таблице9 и равно: х12=1,5, х13=8,5, х21=14, х31=1, х32=10,5, х34=5,5, значения остальных переменных равны 0. Оптимальное значение целевой функции при этом равно: F(x)=208.5.
Сравнение найденных оптимальных решений транспортной задачи с помощью программы MS Excel и метода потенциалов показывает их полное совпадение, что может свидетельствовать о достоверности соответствующих результатов.
2.4 Рекомендации по решению задач оптимизации с
помощью надстройки Поиск решения.
Построение математической модели задачи.
Работа по решению некоторой оптимизационной задачи всегда начинается с построения математической модели, для чего необходимо ответить на следующие вопросы:
-
Каковы переменные модели (для определения каких величин строится модель)?
-
В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?
-
Каким ограничениям должны удовлетворять неизвестные?
Стоит также учесть, что при конструировании модели формулировка ограничений является самой ответственной частью конструкции. В некоторых случаях ограничения очевидны, например, ограничение на количество сырья. Другие же ограничения могут быть менее очевидны и могут быть указаны неверно. Например:
-
В модели с несколькими периодами времени величина материального ресурса на начало следующего периода должна равняться величине этого ресурса на конец предыдущего периода;
-
В модели поставок величина запаса на начало периода плюс количество полученного должна равняться величине запаса на конец период плюс количество отправленного;
-
Многие величины в модели по своему физическому смыслу не могут быть отрицательными, например, количество полученных единиц товара.
Таким образом, на данном этапе делаются выводы об исходных данных (детерминировать или случайные), искомых переменных (непрерывные или дискретные), о пределах, в которых могут находиться значения искомых величин, о зависимостях между переменными (линейные или нелинейные), о критериях, по которым необходимо находить оптимальное решение. Сюда же входит преодоление несовместимости, а также неограниченности целевой функции: при максимизации целевой функции область допустимых решений должна быть ограничена сверху, при минимизации - ограничена снизу.
Решение задач с помощью надстройки Поиск решения.
Прежде всего подготовьте рабочий лист MS Excel-корректно разместите на нем все исходные данные, грамотно введите необходимые формулы для целевой функции и для других зависимостей, выберите место для значений переменных.
Правильно выберите все ограничения, переменные, целевую функцию и другие значения в окно Поиск решения.
Большую часть задач оптимизации представляют собой задачи линейного программирования, т.е. такие, у которых критерий оптимизации и ограничения- линейные функции. В этом случае для решения задачи следует установить флажок Линейная модель в окне Параметры поиска решения. Это обеспечит применение симплекс-метода. В противном случае даже для решения линейной задачи будут использованы более общие (т.е. более медленные)методы.
Поиск решения может работать также и с нелинейными зависимостями и ограничениями. Это, как правило, задачи нелинейного программирования или, например, решение системы нелинейных уравнений. Для успешной работы средства Поиск решения следует стремиться к тому, чтобы зависимости были гладкими или, по крайней мере, непрерывными. Наиболее часто разрывные зависимости возникают при использовании функции ЕСЛИ(), среди аргументов которой имеются переменные величины модели. Проблемы могут возникнуть также и при использовании в модели функций типа ABS(), ОКРУГЛ() и т.д.
Решая задачи с нелинейными зависимостями, следует:
-
Ввести предварительно предположительные значения искомых переменных (иногда легко получить графическое представление решение и сделать приблизительные выводы о решении).
-
В окне Параметры поиска снять (если установлен) флажок Линейная модель.
Решая задачи целочисленного программирования, не следует забывать также о требованиях целочисленности и булевости.
Анализ решения задачи оптимизации.
При необходимости анализ решения. Часто добавляется также представление в виде графиков или диаграмм. Можно получить и отчет о поиске решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
