Реферат: Методы исследования операций

--PAGE_BREAK--Используя результаты теорем 2.1 и 2.2, можно сделать вывод, что для отыскания оптимального решения задачи линейного программирования достаточно перебрать лишь допустимые базисные решения. Этот вы­вод лежит в основе многих методов решения задач линейного программирования.
Симплекс-метод.
Общая идея симплекс-метода заключается в следующем: начиная с некоторой исходной допустимой угловой точки (обычно начала координат), осуществляются последовательные переходы от одной крайней точки к другой до тех пор, пока не будет найдена точка соответствующая оптимальному решению. Решение задачи линейного программирования симплекс-методом удобно оформлять в виде симплекс-таблиц.
Алгоритм симплекс-метода состоит из следующих шагов:
Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n-m (небазисных) переменных. При этом если матрица системы ограничений задачи линейного программирования содержит единичную подматрицу порядка m, то это решение очевидно. Переменные, столбцы которых образуют эту единичную матрицу, являются базисными, остальные – свободными. Если же такой единичной матрицы нет, то для получения начального базисного решения вводятся искусственные переменные. Затем базисные переменные выражаются через небазисные из соответствующих ограничений и полученные выражения подставляются в целевую функцию. Если используются искусственные переменные, то применяются специальные методы (метод больших штрафов, двухэтапный метод).
Шаг 1. Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как полученное базисное решение оптимально. В противном случае переходят к шагу 2.
Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое решение (стать небазисной) при введении в состав базисных новой переменной.
Шаг 3. С помощью метода исключения переменных или метода Гаусса-Жордана находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных и осуществляется переход к шагу 1.
Пример. Решить симплекс-методом задачу
Максимизировать z=3x1+2x2
при ограничениях x1+2x2£ 6;
2x1+x2£ 8;
-x1+x2£ 1;
x1£ 2;
x1³ 0, x2³ 0.
Решение.
Запишем задачу в стандартном виде z-3x1-2x2=0
x1+2x2+s1= 6;
2x1+x2+s2= 8;
-x1+x2+s3= 1;
x1+s4= 2,
где s1, s2, s3, s4 – дополнительные неотрицательные переменные, которые вводятся в правые части ограничений имеющих знак «£» и называются остаточными. Если задача линейного программирования является задачей оптимального распределения ограниченных ресурсов, и правые части каждого ограничения представляют запасы ресурсов, то значения остаточных переменных в любом решении показывают остаток этих ресурсов. Матрица системы ограничений содержит единичную матрицу порядка 4. Ее образуют коэффициенты при остаточных переменных, значит переменные s1, s2, s3, s4 будут базисными переменными, а x1, x2 – свободными или нулевыми.
Шаг 0. Заполняем начальную симплекс-таблицу.
Шаг 1. Условие оптимальности или правило выбора включаемой в базис переменной. Вводимой в базис переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая в Z-строке наибольший по модулю отрицательный (положительный) коэффициент. Если таких коэффициентов несколько, то выбор – произвольный и после этого переходят к шагу 2. Если таких коэффициентов нет, то решение оптимально.
Столбец симплекс-таблицы, соответствующий включаемой переменной, будем называть ведущим столбцом. В нашем случае включаем в базис переменную x1.
Шаг 2. Условие допустимости или правило выбора исключаемой из базиса переменной (одинаковое в задачах максимизации и минимизации). В качестве исключаемой из базиса переменной выбирается та базисная переменная, для которой отношение постоянной в правой части соответствующего ограничения к положительному коэффициенту ведущего столбца минимально. В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно.
Строку симплекс-таблицы, соответствующую исключаемой переменной, будем называть ведущей строкой. В нашем случае исключаем из базиса переменную s2.
Шаг 3. Вычисляем новое базисное решение и переходим к шагу 1.
Симплекс-таблица, соответствующая первой итерации:
Решение не оптимально. Включаем в базис x2 вместо s1. Вторая итерация:
Решение оптимально.
Анализ решения на чувствительность.
Из оптимальной симплекс-таблицы либо непосредственно, либо при помощи простых преобразований можно получить информацию относительно
1.                Оптимального решения: значения базисных переменных записаны в столбце В оптимальной симплекс-таблицы. Оптимальное значение целевой функции находится на пересечении Z-строки и столбца В оптимальной симплекс таблицы. Для рассмотренного примера: x1=10/3, x2=4/3, s1=s2=0, s3=3, s4=2/3, Zmax=12 2/3.
2.                Статуса ресурсов: ресурс называется дефицитным, если в оптимальном решении он использован полностью. Остаточная переменная, соответствующая дефицитному ресурсу в оптимальном решении равна нулю. Для рассмотренного примера дефицитными будут ресурсы 1 и 2, т.к. s1=s2=0,
3.                Ценности каждого ресурса: характеризуются величиной улучшения оптимального значения целевой функции, приходящегося на единицу прироста объема данного ресурса. Их еще называют теневыми ценами ресурсов или двойственными оценками. Эта информация представлена в Z-строке оптимальной симплекс-таблицы в столбцах, соответствующих остаточным переменным.
4.                Чувствительности оптимального решения к изменениям запасов ресурсов, вариациям коэффициентов целевой функции и интенсивности потребления ресурсов.
Двойственность в линейном программировании.
Любую задачу максимизации с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1, b2,…, bn между различными потребителями, например, между некоторыми технологическими процессами, которые представляются столбцами A1, А2, ..., Аm матрицы ограничений задачи. Любое допустимое решение задачи линейного программирования х1, х2, ..., хm дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.
Рассмотрим пример. Завод производит три вида продукции х1, x2 и x3, каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пусть с1, c2 и c3 — прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль.
Формально эта задача записывается так:
найти
<shape id="_x0000_i1046" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image042.wmz» o:><img width=«187» height=«37» src=«dopb174721.zip» v:shapes="_x0000_i1046"> (1)
при ограничениях
<shape id="_x0000_i1047" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image044.wmz» o:><img width=«193» height=«83» src=«dopb174722.zip» v:shapes="_x0000_i1047"> (2)
где a1j, a2j, a3j — время, необходимое для обработки единицы j-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j = 1, 2, 3); b1, b2, b3 — недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.
Обозначим y1, y2 и y3 — цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогда a1jy1 + a2jy2+ a3jy3 мож­но трактовать как расходы на изготовление единицы продукции вида j.
Предположим, что цены ресурсов y1, y2 и y3 выбраны так, что выполняются следующие соотношения:
<shape id="_x0000_i1048" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image046.wmz» o:><img width=«196» height=«83» src=«dopb174723.zip» v:shapes="_x0000_i1048"> (3)
Поскольку b1, b2, b3 — использованный ресурс машинного времени для каждого из станков, то b1y1 + b2y2 + b3y3 — суммарные расходы на производство.
Требуется найти такие y1, y2 и y3, удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:
min g(y1, y2, y3)= b1y1 + b2y2 + b3y3, (4)
y1³ 0, y2³ 0, y3³ 0.
Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.
Запишем теперь прямую и двойственную задачи в общем случае. Прямая задача
 <shape id="_x0000_i1049" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image048.wmz» o:><img width=«104» height=«59» src=«dopb174724.zip» v:shapes="_x0000_i1049"> (5)
при условиях
<shape id="_x0000_i1050" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image050.wmz» o:><img width=«179» height=«59» src=«dopb174725.zip» v:shapes="_x0000_i1050"> (6)
<shape id="_x0000_i1051" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image052.wmz» o:><img width=«133» height=«35» src=«dopb174726.zip» v:shapes="_x0000_i1051">. (7)
Двойственная задача
<shape id="_x0000_i1052" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image054.wmz» o:><img width=«94» height=«58» src=«dopb174727.zip» v:shapes="_x0000_i1052"> (8)
при условиях
<shape id="_x0000_i1053" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image056.wmz» o:><img width=«184» height=«58» src=«dopb174728.zip» v:shapes="_x0000_i1053"> (9)
<shape id="_x0000_i1054" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image058.wmz» o:><img width=«133» height=«34» src=«dopb174729.zip» v:shapes="_x0000_i1054">. (10)
Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи:
1) если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;
2) коэффициенты целевой функции прямой задачи c1, c2, …, cn становятся свободными членами ограничений двойственной задачи;
3) свободные члены ограничений прямой задачи b1, b2, …, bm становятся коэффициентами целевой функции двойственной задачи;
4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;
5) если знаки всех неравенств в ограничениях прямой «£», то в двойственной задаче все ограничения будут иметь знак «³»;
6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.
Переменные y1, y2,…, ym двойственной задачи иногда называют «теневыми ценами».
Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (т > n).
Связь между оптимальными решениями прямой и двойственной за­дач устанавливают посредством следующих теорем теории двойственности.
Теорема. Если x0 и у0 — допустимые решения прямой и двойственной задач, т. е. если Ах0 £ b и АTy0 ³ с, то
cTx0£ bTy0,
т. е. значения целевой функции прямой задачи никогда не превышают значений целевой функции двойственной задачи.
Теорема(основная теорема двойственности). Если x0 и у0 — допустимые решения прямой и двойственной задач и если cTx0=bTy0, то x0 и у0 — оптимальные решения пары двойственных задач.
Теорема. Если в оптимальном решении прямой задачи i-е ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю.
Смысл этой теоремы состоит в следующем. Если некоторый ресурс bi имеется в избытке и i-е ограничение при оптимальном решении выполняется как строгое неравенство, то оно становится несущественным, и оптимальная цена соответствующего ресурса равна 0.
Теорема. Если в оптимальном решении двойственной задачи ограничение j выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю.
Экономическая интерпретация этой теоремы: поскольку величины yj представляют собой цены соответствующих ресурсов, то <shape id="_x0000_i1055" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image060.wmz» o:><img width=«69» height=«58» src=«dopb174730.zip» v:shapes="_x0000_i1055"> — это затраты на i-й технологический процесс, величина сi — прибыль от реализации на единицу изделия. Поэтому с экономической точки зрения теорема означает следующее: если i-й технологический процесс оказывается строго невыгодным с точки зрения оптимальных цен ресурсов уопт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса хi должна быть равна 0.
Таким образом, теорема выражает принцип рентабельности оптимального организованного производства.
Теорема (теорема существования). Прямая и двойственная задачи имеют оптимальные решения тогда и только тогда, когда обе они имеют допустимые решения.
Теорема (теорема двойственности). Допустимый вектор x0 оптимален тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение уо, что
<shape id="_x0000_i1056" type="#_x0000_t75" o:ole=""><imagedata src=«37054.files/image062.wmz» o:><img width=«107» height=«33» src=«dopb174731.zip» v:shapes="_x0000_i1056">.

Методы решения целочисленных ЗЛП.
Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения. Задача называется полностью целочисленной, если условие целочисленности наложено на все переменные; когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной. Если при этом целевая функция и функции, входящие в ограничения, линейные, то задача является задачей линейного программирования.
Методы решения задач целочисленного программирования можно классифицировать как методы отсечений (1) и комбинаторные методы (2).
Исходной задачей для методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требования целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется до тех пор, пока координаты допустимого решения не станут целочисленными. Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами,
В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений, разумеется, на первый план здесь выдвигается проблема разработки тестовых процедур, позволяющих непосредственно рассматривать лишь относительно небольшую часть указанных решений, а остальные допустимые решения учитывать некоторым косвенным образом. Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задач с ослабленными ограничениями. При таком подходе из рассматриваемой задачи получаются две подзадачи путем специального «разбиения» пространства допустимых решений и отбрасывания областей, не содержащих допустимых целочисленных решений.
В случае, когда целочисленные переменные являются булевыми, применяются комбинированные методы. Булевы свойства переменных существенно упрощают поиск решения.
Алгоритм метода отсечений для решения полностью целочисленной задачи.
Необходимым условием применения данного алгоритма является целочисленность всех коэффициентов и правых частей ограничений исходной задачи. Любое ограничение с рациональными коэффициентами легко приводится к требуемому виду путем умножения ограничения на наименьший общий знаменатель входящих в него коэффициентов.
    продолжение
--PAGE_BREAK--