Методы оптимизации

Потенциал первого столбца  v₁ = u₂ + c₂₁ = 0 + 4 = 4;

второго: v₂ = u₂ + c₂₂ = 0 + 7 = 7;

третьего: v₃ = u₂ + c₂₃ = 0 + 13 = 13;

пятого: v₅ = u₂ + c₂₅ = 0 + 2 = 2.

Рассчитанные потенциалы записываем напротив соответствующих  столбцов ниже матрицы. Поскольку по всем базисным клеткам строки 2 потенциалы столбов найдены, переходим к  расчету потенциалов строк.

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 3 и  базисной клетке А₁В₃ по формуле 

,                                                          (3.5)

где u₁ = v₃ – c₃₁ = 13 – 8 = 5.

Для строки 3 потенциал будет  равен:

u₃ =  v₅ – c₃₅ = 2 – 1 = 1.

Также рассчитываем потенциалы для всех строк и столбцов (табл. 5).

Расстановка потенциалов  и перераспределение поставок 

Таблица 5

Операция 2.2. Проверка небазисных клеток на соответствие их условию  оптимальности.

Оптимальный план транспортной задачи должен отвечать критерию оптимальности, который выражается в том, соответствуют ли небазисные клетки матрицы условию, формулируемому следующим выражением:  

,                                                     (3.6)

Если это условие  для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки  единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже c_ij, значит, использование данного маршрута не улучшит план, а если c_ij ниже разности потенциалов, т. е. условие (2.8) не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать.

Проверим условие (2.8) для  табл. 5.

Клетка А₁В₁: 4 – 5 < 10, условие выполняется.

Клетка А₁В₂: 7 – 5 < 9, условие выполняется и т. д.

Если для всех небазисных клеток условие 3 выполняется, то рассматриваемый  план будет оптимален. Дальнейшие действия переходят по алгоритму к операции 4.

Однако для нашего примера  это не так. Не выполняется условие  для клетки А₂В₄ (10 – 0> 6), клетки А₃В₃ (13 – 1 > 9), а также для клеток А₃В₄, А₄В₃, из чего следует, что разработанный опорный план не оптимален. Отметим эти клетки. 

Операция 3. Улучшение  плана.

Поскольку полученный план не оптимален, дальнейшие действия алгоритма состоят в его преобразовании в лучшую сторону или просто улучшения.

Операция 3.1. Построение цепи (контура, цикла) перераспределения  поставок.

Улучшение плана  осуществляется по одной из небазисных клеток, для которой условие оптимальности  оказалось невыполненным. В нашем  плане имеется четыре такие клетки. Выбираем одну из них, для которой  условие оптимальности не выполняется  в наибольшей степени. В нашем  плане это клетка А₂В₄. Для нее условие оптимальности не выполнено на 4 единицы (10 – 0 – 6 = 4). Для этой клетки строим цепь перераспределения поставок. Цепь перераспределения поставок – это такая замкнутая ломаная линия, которая проходит по клеткам матрицы ходом шахматной ладьи. В вершинах контура обязательно лежит одна небазисная клетка (несоответствующая условию оптимальности, найденная ранее), а остальные соответствуют только базисным клеткам. Линии контура могут пересекаться. Для небазисной клетки А₂В₄ цепь будет проходить по клеткам А₁В₄, А₁В₃, А₂В₃ (табл. 6).

Возможные варианты построения цикла перераспределения 

Таблица 6

В нашем случае форма цепи простая. Однако цепь может иметь  любую форму, в том числе и  причудливую (см. табл. 6). Её нужно научиться отыскивать, используя эвристические подходы. При этом необходимо учитывать, что каждая небазисная клетка транспортной матрицы обязательно имеет одну цепь перераспределения поставок.

Операция 3.2. Перераспределение  поставок.

Перераспределение поставок (см. табл. 5) производится по цепи. Вначале определим объем перераспределения поставок. Для этого присвоим клеткам – вершинам цепи – знаки. В небазисную клетку А₂В₄ ставим «+», поскольку в нее будет вводиться поставка. Далее, чередуя «+» с «–», расставляем знаки по остальным вершинам контура. Величина объема перераспределения поставок принимается равной минимальной поставке в отрицательной клетке. Для нашего случая это 50 единиц груза. Перераспределение заключается в том, что к поставкам в положительных клетках найденный объем прибавляется, а для отрицательных клеток отнимается. Результат представлен в табл. 5

Функционал F' нового плана, представленного в табл. 5 (выделенные поставки), составляет 1950 ткм, что на 200 ткм меньше значения функционала F предыдущего плана.

Полученный улучшенный план, представленный в табл. 5, в свою очередь, требует проверки на оптимальность, поэтому необходимо вернуться к операции 2.

Совокупность действий, описанных  в операциях 2 и 3, в процессе решения  задачи повторяется до тех пор, пока не будет получен оптимальный  план. Эта совокупность носит итеративный (циклический) характер, поэтому она  называется итерацией. Через определенное число итераций план становится оптимальным. После этого осуществляется переход  от второй операции к четвертой (табл. 7).

Повторение операций 2, 3 

Таблица 7

От матрицы к матрице  грузооборот (затраты на транспортировку) должны снижаться. Если план не оптимален, то необходимо произвести повторный  расчёт потенциалов, проверить небазисные клетки на соответствие условию оптимальности.

Покажем дальнейшее решение  задачи, основываясь на данных табл.  5 Результат действий второй и третьей итераций приведен в табл. 7

Проверка плана на оптимальность  свидетельствует о том, что для  двух клеток условия оптимальности  не выполняются. После перераспределения  поставок по клетке А₄В₃, получаем новый план (табл. 8).

Оптимальный план поставок  

Таблица 8

Проверка плана перевозок  на оптимальность по условию (3.6) показала, что для всех небазисных клеток матрицы условия оптимальности выполняются. Функционал F'' оптимального плана равен 1920 ткм. Таким образом, получен план перевозок, обеспечивающий минимальный объем перевозочной работы для транспортировки всего груза между станциями погрузки и выгрузки.

 

 

 

 

 

 

 

 

Заключение.

 

 

Методы оптимизации  составляют методы нахождения экстремумов функций нескольких переменных на множествах, которые задаются линейными или нелинейными равенствами и неравенствами.

Сейчас стало общепринятым утверждение о том, что анализ, синтез и управление сложными системами  практически любого происхождения  возможны лишь на основе описания этих систем в форме математических моделей. Характерным для этих моделей является наличие в их составе двух групп элементов, увязанных в единую систему, в которой они тем или иным образом взаимодействуют. Значения одних элементов являются альтернативными, могут избираться в определенной области; значения других - производны от первых. Говорят о параметрах управления и целевой функции.

Оптимизация системы состоит  в поиске такого набора параметров управления, при котором целевая  функция достигает экстремума. Этим достигается новое качественное состояние системы — экстремальность результата ее функционирования по заданному критерию качества. Новое качество постигается сознанием в этом процессе на более высокой ступени познания не как первичная логическая категория, обеспечивающая лишь весьма элементарные различения и оценку качества (типа “больше - меньше”), а как значительно более развитая категория количественно определенной оценки качества. Оптимальное (наилучшее из всех возможных) состояние управляемой системы и представляет собой такую количественно определенную оценку качественного состояния системы. Оптимизация решений в сложных системах придает им новое качество, количественно выражающееся в существенном повышении эффективности их функционирования.

 

Список использованной литературы.

 

1.Аттетков А. В., Галкин С. В., Зарубин В. С. Методы оптимизации, 2008-440с 2.Корнев В.В, Курдюмов В.В. Прикладные методы оптимизации, 2009 –172с

3.Пантелеев, А.В. Методы оптимизации в примерах и задачах, 2009- 544с.

4.Юдин Д. Б. Вычислительные методы теории принятия решений, 2010 г.- 320 с.