Исследование операций

1. Симплекс-метод решения ОЗЛП.

2. Распределительный метод оптимизации опорных планов ТЗ.

3. Прямая и обратная прогонка модели ОП. Оптимальные и условно оптимальные решения.

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

1. Симплекс-метод решения ОЗЛП

Рассматриваемый метод является универсальным в том смысле, что позволяет решать задачи линейного программирования в общей постановке, хотя требует их приведения к так называемому стандартному виду: найти

х1, …, xn , доставляющие минимум функции при условиях

Часто используется матричная форма представления условий (1), например z=CX →min; AX = B; X≥0, где А— матрица коэффициентов аij ; X и B – столбцы (х1, …, хn) и (b1, …, bm) соответственно; С – строка (c1,…, cn).

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

Условия (1) представляют собой систему линейных неоднородных уравнений, особенности которой определяют характер решения задачи в целом. Если система (1) неразрешима (множество U пусто), то задача теряет смысл. Если существует единственное решение (1), то оно является одновременно и решением исходной задачи, поскольку нет другого выбора. Наконец, если система (1) имеет более одного решения, задача становится объектом исследования.

Известно, что в последнем случае искомое множество решений системы (1) может быть представлено как

где ψ1, …, ψn – линейные комбинации переменных xm+1, …, xn называемых свободными. Вследствие линейности ψi(i = 1, m) равенства (2) приводятся к виду:

причем коэффициенты А1<т+1, . . ., Атп и правые части В1 . . ., Вт однозначно определяются теми аij, bi , которые присутствуют в (1).

Система (3) имеет следующую особенность: если номер jпеременной xj находится в пределах 1≤j≤n, то эта переменная входит только в строку с номером i=j, имея коэффициент, равный единице, и не входит в остальные строки, для которых i≠j. Такая система называется канонической. Она позволяет легко указать множество всех возможных решений для (1), среди которых находятся так называемые базисные решения, представляющие особый интерес.

Частное решение системы (3), получаемое приравниванием свободных переменных xm+1,…, хп нулю, называется базисным. Оно имеет вид:

X1= В1 …,хт = Вm, , хт+1= . . . = хп = 0 (4)

и является допустимым (в смысле требований хj≥ 0) при VBi≥0 (i=l, m). Появление хотя бы одного Вi=0 делает решение (4) вырожденным.

Понятия, относящиеся к стандартной постановке задачи линейного программирования, связаны с геометрическими представлениями.Так, существует соответствие между крайними точками многогранника U и решениями вида (4). Пусть U определяется условиями.

Предполагая все bi строго положительными, рассмотрим возможные решения системы (6), в которой свободными удобно считать переменные x1 ,. . ., хп. Каждый набор их значений соответствует некоторой точке в U и, кроме того, входит составной частью в решение хг, …, xn,xn+i, . . ., хп+т, получаемое подстановкой принятых x1,…, хп в (6). Тем самым устанавливается общее соответствие между конкретными числами хи …, хп, xn+i, ..., хп+т и точками X € U.

Пусть теперь xn+i=bi(i=l, m), Xj=O(j—l, n) — допустимое базисное решение системы (6). Представим его компоненты xn+i, xjв виде xn+i=axn+i,1 + (1-а)хп+i, 2; Xj==axn+ (1—а)хj2(0<а<1; i=1, т; j=1, п), где xj1 , xn+i,1 и xj2,xn+i,2— двадругие произвольно взятые решения (6). Очевидно, для номеров j=1, п рассматриваемые формулы примут вид 0= ахj2+(1—a)xj2, но это означает Xj1=0 и Xj2=0 (иначе при 0<а<1 будет нарушено требование неотрицательности переменных). Таким образом, исследуемые решения (базисное и два других) совпадают друг с другом, и точка X € U, отвечающая заданным xjt xn+i не может находиться на отрезке, соединяющем две другие точки многогранника U, т. е. она оказывается крайней.

Из сказанного следует важный вывод: если исходная стандартная задача линейного программирования имеет решение, то оно обязательно совпадет с каким-либо допустимым базисным решением системы (1). Идея перебора крайних точек многогранника U, лежащая в основе симплекс-метода, переходит в требование последовательного анализа базисных решений названной системы.

Для этого необходимо:

а) найти некоторое допустимое базисное решение (1), если оно существует;

б) проверить найденное решение на оптимальность;

в) осуществить переход к новому допустимому базисному решению, если предыдущее оказалось неоптимальным;

г) повторять операции б), в) до тех пор, пока не будет получено оптимальное базисное решение системы (1) или подтверждена возможность неограниченного увеличения |z|.

Для многих практических задач удается сравнительно легко отыскать каноническую форму (3) условий (1), но часто это вызывает трудности. Можно, конечно, предварительно исследовать вопрос существования решений, однако желательно, чтобы сам метод исключал необходимость подобных исследований и не был бы связан с априорными предположениями свойств системы (1). Симплекс-метод удовлетворяет поставленному требованию. Он реализуется в два этапа: на первом решается вспомогательная задача, а на втором — основная.

Предположим, что исходные условия (1) рассматриваются в случае, когда все bi (i=l, m) неотрицательны (иначе нужно было бы умножить на —1 строки, содержащие bi<;0). Первый этап исследований начинают с формального введения в каждую строку (1) искусственной неотрицательной переменной, что позволяет построить систему:

Если существует решение для (1), то оно допустимо и для (7) при хn+1=. . .=хп+т=0. Наоборот, если получено решение системы (7), содержащее нулевые xn+1 (i=1, т), то оно допустимо для (1).

Далее рассматривается сумма, наименьшее возможное значение которой есть 0 вследствие неотрицательности всех xn+i. Именно оно будет получено, если (1) имеет решение, причем проверка условия min w=0 проводится путем анализа вспомогательной задачи линейного программирования: найти xi≥ 0, xn+i≥ 0 (i=1, п, i=1, m), доставляющие min при условиях (7). Особенностью этой задачи является то, что для нее легко назвать начальное базисное решение xj= 0(j=1, n), xn+i=bi(i = 1, т), как это следует из (7).

Если окажется min w>0, то процесс вычислений можно прекратить и считать исходную задачу с условиями (1) неразрешимой. Если же min w=0, то оптимальное решение вспомогательной задачи фиксируется и используется на втором этапе исследований.

Второй этап начинается с оценки и решения вспомогательной задачи, полученного в конце этапа 1. В лучшем случае это решение является невырожденным и содержит все xn+i в числе свободных переменных. В худшем случае некоторые xn+i войдут в базис и тогда необходимо сохранять их нулевые значения неизменными на каждом шаге этапа 2. Это достигается отбрасыванием тех Xj, xn+i, которые имеют отличные от нуля коэффициенты в рассматриваемом решении.

После того как указанная оценка проведена, становится возможным возвратиться к исходной задаче линейного программирования, имея в своем распоряжении некоторое допустимое базисное решение системы (1), найденное в ходе исследования задачи на минимум w.

Основу рассмотренных этапов симплекс-метода составляет так называемый симплекс-алгоритм, предусматривающий проведение ряда операций с базисными решениями систем (7) (на первом этапе) и (1) (на втором этапе).

2. Распределительный метод оптимизации опорных планов ТЗ

Разнообразие нелинейных задач математического программирования (с полной или неполной информацией) вызывает необходимость разработки методов оптимизации, не связанных непосредственно с анализом условий существования X* и базирующихся на вычислительных и логических операциях. Идеи этих методов обычно просты. Как правило, они следуют из соображений «здравого смысла» и сводят проблему решения той или иной задачи к выбору надлежащего алгоритма поиска x*, z*, причем желаемые свойства таких алгоритмов оговариваются заранее. Общим здесь является утверждение целесообразности (достаточности) предлагаемых подходов к решению экстремальных задач. Необходимость того или иного подхода чаще всего недоказуема.

Численные методы играют значительную роль в прикладных исследованиях. Это обусловлено рядом причин, среди которых главное место занимает разнообразие функций f(X) и gi(X), а также форм их задания. В отдельных случаях бывает трудно определить, к какому классу относится та или иная задача и существует ли для нее обоснованный метод решения. На выбор метода может влиять и требование максимально использовать мощности ЭВМ с целью снижения затрат на исследования (если подобная перспектива реальна). Большое значение приобретает вычислительный эксперимент как источник информации о свойствах изучаемой задачи в условиях, когда ее сложность или неопределенность каких-то параметров затрудняют разработку удобной математической модели.

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

Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода. Следует помнить, что перед нахождением опорного плана транспортная задача должна быть сбалансирована.

Метод северо-западного угла

На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов.

Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце .

Если существующий запас позволяет перевезти всю потребность, то

· в клетку (i,j) в качестве перевозки вписывается значение потребности ;

· j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

· от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. .

Если существующий запас не позволяет перевезти всю потребность, то

· в клетку (i,j) в качестве перевозки вписывается значение запаса ;

· i-я строка вычеркивается, поскольку ее запас уже исчерпан;

· от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. .

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

Метод минимального элемента

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

Метод Фогеля

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом .

Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом .

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

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

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

Общая распределительная задача ЛП – это РЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов.

3. Прямая и обратная прогонка модели ОП. Оптимальные и условно оптимальные решения

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

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных х1 , х2, .. ., хп, удовлетворяющие т условиям-равенствам

и обращающие в максимум линейную функцию этих переменных:

L= c1x1+ c2x2+ …+cnxn→ max (2)

Для простоты предположим, что все условия (1) линейно независимы (r=т), и будем вести рассуждения в этом предположении.

Назовем допустимымрешением ОП всякую совокупность неотрицательных значений х1, х2, ... , хп, удовлетворяющую условиям (1). Оптимальным назовем то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда. Во-первых, может оказаться, что уравнения (1) вообще несовместны (противоречат друг другу). Может оказаться и так, что они совместны, но не в области неотрицательных решений, т. е. не существует ни одной совокупности чисел х1 > 0, х2> 0, …, хп ≥0, удовлетворяющей условиям (1). Наконец, может быть и так, что допустимые решения ОП существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена сверху. Все эти опасности подстерегают нас, главным образом, в «придуманных», искусственно поставленных задачах, хотя иногда легкомысленное планирование (неполный учет имеющихся ресурсов) приводит к неразрешимым задачам линейного программирования.

Чтобы представить себе принципиальную сторону ОЗЛП, обратимся к геометрической интерпретации. Пусть число уравнений т на два меньше числа переменных п (п-т = к = 2).Такой частный случай дает возможность геометрической интерпретации ОЗЛП на плоскости.

Мы знаем, что т линейно независимых уравнений (1) всегда можно разрешить относительно каких-то т базисных переменных, выразив их через остальные, свободные, число которых равно п— т=к (в нашем случае к = 2). Предположим, что свободные переменные — это x1и x2(если это не так, то всегда можно заново перенумеровать переменные), а остальные: x3, x4,…,xn — базисные. Тогда вместо т уравнений (1) мы получим тоже т уравнений, но записанных в другой форме, разрешенных относительно xs, x4,…:

На этой прямой х3 = 0; по одну сторону от нее х3 > 0, по другую — х3 < 0. Отметим штриховкой ту сторону (полуплоскость), где х3 > 0 (рис. 4). Пусть эта сторона оказалась правее и выше прямой х3 = 0. Значит, вся область допустимых решений (ОДР) лежит в первом координатном угле, правее и выше прямой х3 = 0. Аналогично поступим и со всеми остальными условиями. Каждое из них изобразится прямой со штриховкой, указывающей «допустимую» полуплоскость, где только и может лежать решение (рис. 4).

Таким образом, мы построили п прямых: две оси координат (Ox1 и Ox2) и п — 2 прямых xз = 0, x4 = 0,…, хп = 0. Каждая из них определяет «допустимую» полуплоскость, где может лежать решение. Часть первого координатного угла, принадлежащая одновременно всем этим полуплоскостям, и есть ОДР. На рис. 4 показан случай, когда ОДР существует, т. е. система уравнений (3) имеет неотрицательные решения. Заметим, что этих решений— бесконечное множество, так как любая пара значений свободных переменных, взятая из ОДР, «годится», а из х1 и х2 могут быть определены и базисные переменные.

Может оказаться, что область допустимых решений не существует, и значит, уравнения (3) несовместны в области неотрицательных значений.

А может ли оказаться, что оптимального решения не существует? Да, может, если в ОДР функция L’ (а значит и L) не ограничена сверху. Пример такого ненормального случая показан на рис. 5 (в разумно поставленных задачах обычно такого недоразумения не возникает).

Оптимальное решение ОЗЛП (если оно существует) достигается при такой совокупности значений переменных х1, х2, .., Xn, где по крайней мере к из них обращаются в нуль, а остальные неотрицательны.

Отсюда вытекает идея, лежащая в основе боль¬шинства рабочих методов решения ОЗЛП,— идея «последовательных проб». Действительно, попробуем разрешить уравнения (1) относительно каких-нибудь m базисных переменных и выразим их через остальные к свободных.

Попробуем положить эти свободные переменные равными нулю — авось повезет, наткнемся на опорную точку. Вычислим базисные переменные при нулевых значениях свободных. Если все они оказались неотрицательными, значит, нам повезло, мы сразу же получим допустимое (опорное) решение, и его остается только оптимизировать. А если нет? Значит, данный выбор свободных и базисных переменных допустимого решения не дает; точка лежит не на границе, а вне ОДР. Что делать? Надо «переразрешить» уравнения относительно каких-то других базисных переменных, но не как попало, а так, чтобы это приближало нас к области допустимых решений (для этого в линейном программировании существуют специальные приемы, на которых мы останавливаться не будем). Пусть, наконец, несколько раз повторив такую процедуру, мы нашли опорное решение ОЗЛП. Но это еще не все. Тут надо поставить вопрос: а является ли это решение оптимальным? Выразим функцию L через последние получившиеся свободные переменные и попробуем увеличивать их сверх нуля. Если от этого значение L только уменьшается, значит, нам повезло, и мы нашли оптимальное решение, ОЗЛП решена.

А если нет? Снова «переразрешаем» систему уравнений относительно других базисных переменных, и снова не как попало, а так, чтобы, не выходя за пределы допустимых решений, приблизиться к оптимальному.

Разработанные в теории линейного программирования вычислительные методы («симплекс-метод», «двойственный симплекс-метод» и другие,) позволяют находить оптимальное решение не «слепым» перебором, а «целенаправленным», с постоянным приближением к решению. Добавим, что современные ЭВМ, как правило, снабжены подпрограммами для решение задач линейного программирования, так что лицу, желающему их решать, нет даже особой надобности обучаться решению таких задач «вручную» — труд крайне неприятный и изнурительный.

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

1. Вентцель Е. Исследование операций : Задачи, принципы, методол./ Е. С. Вентцель,. -2-е изд., стер.. -М.: Наука, 1988. -206 с.

2. Дегтярев Ю. Исследование операций : [Учеб. для вузов по спец. "АСУ"]/ Ю. И. Дегтярев,. -М.: Высш. шк., 1986. -319 с.

3. Зайченко Ю. Исследование операций : Нечеткая оптимизация : [Учеб. пособие для вузов по спец. "Автоматизир. системы обраб. информ. и управления" и "Прикл. математика"]/ Юрий Зайченко,. -К.: Выща шк., 1991. -191 с.

4. Исследование операций и АСУ : Респ. межвед. науч. сб./ Киев. гос. ун-т им. Т. Г. Шевченко; Редкол.: И. И. Ляшко (отв. ред.) и др.;. -К. : Вища шк. Изд-во при Киев. гос. ун-те. -Вып. 30. -1987. -108 с.

5. Исследование операций и АСУ : Респ. межвед. науч. сб./ Киев. гос. ун-т им. Т. Г. Шевченко; Редкол.: И. И. Ляшко (отв. ред.) и др.;. -К. : Вища шк. Изд-во при Киев. гос. ун-те. -Вып. 31. -1988. -118 с.

6. Исследование операций и АСУ : Респ. межвед. науч. сб./ Киев. гос. ун-т им. Т. Г. Шевченко; Редкол.: И. И. Ляшко (отв. ред.) и др.;. -К. : Вища шк. Изд-во при Киев. гос. ун-те. -Вып. 32. -1988. -111 с.