Лекция МПС №4 от 30.10.2012

Линейное программирование

Метод искусственного базиса
\Если начальный опорный план задачи находится методом искусственного базиса, то сначала надо решить симплекс-методом вспомогательную w-задачу. При этом необходимо в начальную симплексную таблицу включить и z-строку, соответствующую целевой функции исходной задачи. Для составления симплекс-таблицы из функции z исключают базисные переменные, а из функции w – искусственные базисные переменные.
Возможны следующие случаи:
В оптимальном решении w-задачи хотя бы одна из искусственных переменных отлична от нуля (т.е. не вышла из базиса). Тогда исходная z-задача не имеет допустимых планов (т.е. ее система ограничений не совместна).
В оптимальном решении новой w-задачи все искусственные переменные раны нулю (т.е. вышли из базиса), а, значит, и искусственная целевая функция равна нулю. Тогда значения оставшихся координат плана дадут начальный опорный план исходной задачи, которую можно решить симплекс-методом.
Пример 5.
Хлебозавод может выпекать хлеб в любой из трех видов печей П1, П2, П3. Трудоемкость и себестоимость выпечки 1 центнера хлеба представлены в таблице. Сколько необходимо выпечь в каждой печи, чтобы его суммарная себестоимость была минимальной при условии, что трудовые ресурсы ограничены н/ч, а общее количество горячего хлеба должно быть не менее 60 ц?

Вид печи
П1
П2
П3

Трудоемкость, н/ч
1
0,9
1,2

Себестоимость, ден.ед.
21
19
22


Двойственность в линейном программировании
С любой задачей ЛП тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется прямой (или исходной). Пара симметричных двойственных задач имеет вид
Прямая задача
13 EMBED Equation.3 141513 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Двойственная задача
13 EMBED Equation.3 141513 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.

Экономически пара взаимно двойственных задач может быть интерпретирована, например, так.
Прямая задача. Сколько и какой продукции 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 надо произвести, чтобы при заданных стоимостях единицы продукции 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и объемах имеющихся ресурсов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и нормах расходов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 максимизировать выпуск продукции в стоимостном выражении?

Двойственная задача. Какова должна быть оценка единицы каждого из ресурсов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, чтобы при заданных количествах ресурсов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 величина стоимости единицы продукции 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и нормах расходов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 минимизировать общую оценку затрат на все ресурсы?
Переменные 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 называют оценками или учетными (неявными, теневыми) ценами.
Правила построения двойственной задачи к исходной задаче ЛП в общем виде
Прямая задача
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 - произвольные, 13 EMBED Equation.3 1415
Двойственная задача
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415

13 EMBED Equation.3 1415 - произвольные, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415

Упорядочивается запись исходной задачи: если целевая функция задачи исследуется на max, то ограничения должны иметь знак 13 EMBED Equation.3 1415 или =, а если на min, то ограничения должны иметь знак 13 EMBED Equation.3 1415 или =.
Каждому ограничению исходной задачи ставится в соответствие двойственная переменная 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, и, наоборот, т.е. число переменных двойственной задачи равно числу ограничений прямой задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.
Если целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи используется на min, и наоборот.
Коэффициенты целевой функции прямой задачи становятся свободными членами системы ограничений двойственной задачи.
Свободные члены системы ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи.
Матрицы коэффициентов систем ограничений прямой и двойственной задач являются транспонированными друг к другу.
Если на переменную 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 прямой задачи наложено ограничение на знак, то j-е ограничение двойственной задачи записывается в виде неравенства и наоборот.
Если переменная 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 исходной задачи произвольная, то j-е огарничение двойственной задачи имеет знак равенства.
Если в прямой задаче имеются ограничения-равенства, то на соответствующие переменные двойственной задачи не налагаются условия неотрицательности.
Пример 6.
Составить к следующей задаче ЛП двойственную
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Решение.
упорядочим запись задачи, умножив первое ограничение на (1-):
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415;
каждому ограничению поставим в соответствие двойственную переменную 13 EMBED Equation.3 1415,13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
число переменных исходной задачи равно числу ограничений двойственной;
так как целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи будет исследоваться на min:
13 EMBED Equation.3 1415
свободные члены системы ограничений прямой задачи 12,4,14 станут коэффициентами целевой функции двойственной, т.е.
13 EMBED Equation.3 1415
коэффициенты целевой функции прямой задачи 3,2,1 станут свободными членами системы ограничений двойственной задачи;
матрицы коэффициентов систем ограничений прямой и двойственной задач являются транспонированными друг к другу, т.е.
13 EMBED Equation.3 1415
получим следующую систему ограничений двойственной задачи:
13 EMBED Equation.3 1415
так как все переменные 13 EMBED Equation.3 1415,13 EMBED Equation.3 1415, то вместо знака везде будут неравенства, вид которых выбирается по целевой функции и, поскольку F исследуется на min, то неравенства должны быть со знаком 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415
двойственная задача имеет вид
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Двойственность в линейном программировании
Пусть имеется симметричная пара взаимно двойственных задач
Прямая задача
13 EMBED Equation.3 141513 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Двойственная задача
13 EMBED Equation.3 141513 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.

Основное неравенство теории двойственности. Для любых допустимых планов 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 прямой и двойственной задач всегда справедливо неравенство
13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415.
Экономическое содержание неравенства означает, что для любых допустимых планов X и Y общая стоимость не превосходит суммарной оценка ресурсов.
Достаточный признак оптимальности. Если для некоторых допустимых планов 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 пары двойственных задач выполняется неравенство 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 оптимальными планами соответствующих задач.
Экономический смысл теоремы состоит в том, что план 13 EMBED Equation.3 1415 и вектор оценки ресурсов 13 EMBED Equation.3 1415 являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.
Принцип двойственности. Если одна из двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, притом для оптимальных планов 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415выполняется равенство 13 EMBED Equation.3 1415. Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых планов, то система ограничений другой задачи противоречива.
Следствие (теорема существования оптимальных планов). Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой.
Экономическая интерпретация принципа двойственности состоит в том, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции равна суммарной оценке ресурсов, т.е. оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки обладают тем свойством, что гарантируют рентабельность оптимального плана (т.е. равенство оценки продуктов и ресурсов) и обуславливают убыточность всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты решения.
Теорема о дополняющей нежесткости. Для оптимальности допустимых планов 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 прямой и двойственной задач необходимо и достаточно, чтобы выполнялись соотношения
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 (2.53)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.54)
Условия (2.53), (2.54) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.
Пример 7. Дана пара взаимно двойственных задач
Прямая задача
13 EMBED Equation.3 141513 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Двойственная задача
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

Зная оптимальное решение прямой задачи, выписать ответ двойственной задачи. Дать экономическую интерпретацию двойственных оценок.
Решение.
Базисным переменным прямой задачи 13 EMBED Equation.3 1415 поставим в соответствие свободные переменные двойственной задачи 13 EMBED Equation.3 1415 в 1-й и последней симплекс-таблице примера 4:


Решение двойственной задачи найдем по последней z-строке и прибавим к ним соответствующие коэффициенты целевой функции прямой задачи:
13 EMBED Equation.3 1415 (так как в целевой функции прямой задачи коэффициент при 13 EMBED Equation.3 1415 равен 1);
13 EMBED Equation.3 1415 (потому что в целевую функцию прямой задачи 13 EMBED Equation.3 1415 не входит);
13 EMBED Equation.3 1415 (потому что в целевую функцию прямой задачи 13 EMBED Equation.3 1415 не входит).
Следовательно, 13 EMBED Equation.3 1415.
Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное 13 EMBED Equation.3 1415, совпадает с максимальным значением целевой функции 13 EMBED Equation.3 1415 исходной задачи.
Дадим экономическую интерпретацию двойственных оценок. Переменные 13 EMBED Equation.3 1415и 13 EMBED Equation.3 1415 обозначают оценки единицы заготовок соответственно 2-го и 3-го видов соответственно. Эти оценки отличны от нуля, что означает, что заготовки 2-го и 3-го видов полностью используются при оптимальном плане производства обуви. 13 EMBED Equation.3 1415 и это означает, что заготовки 1-го вида используются не полностью при оптимальном плане производства обуви. Таким образом, двойственные оценки определяют дефицитность используемых фабрикой заготовок, т.е. заготовки 2-го и 3-го вида являются дефицитными, а заготовки 1-го вида – недефицитными.
Величина оценки из двойственного плана показывает, на сколько возрастет максимальное значение целевой функции прямой задачи при увеличении количества заготовок соответствующего вида на 1 штуку.
Увеличение количества заготовок 2-го вида на 1 штуку приведет к тому, что появится возможность найти оптимальный план производства обуви, при котором общая стоимость изготовляемой обуви возрастет на 13 EMBED Equation.3 1415ден.ед. и станет 18+1=19 ден.ед.
Аналогично, увеличение количества заготовок 3-го вида на 1 штуку приведет к тому, что появится возможность найти оптимальный план производства обуви, при котором общая стоимость изготовляемой обуви возрастет на 13 EMBED Equation.3 1415ден.ед. и станет 18+1=19 ден.ед.
Двойственный симплекс-метод
Симплекс-метод применяется для решения задач с неотрицательными свободными членами 13 EMBED Equation.3 1415 произвольными по знаку приведенными коэффициентами целевой функции 13 EMBED Equation.3 1415. Иногда бывает легче найти базис, удовлетворяющий признаку оптимальности (все 13 EMBED Equation.3 1415), но не удовлетворяющий критерию допустимости (не все 13 EMBED Equation.3 1415). Вариант симплекс-метода, применяемый для решения таких задач, называется двойственным симплекс-методом.
13 EMBED Equation.3 1415 (2.55)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 (2.56)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.57)
где система ограничений имеет предпочтительный вид и все приведенные коэффициенты целевой функции 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. При этом условие 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 не требуется. Определенную таким образом задачу будем называть задачей в двойственной базисной форме. Оно имеет базисное, но не опорное решение.
Двойственный симплекс-метод, применяемый к задаче в двойственной базисной форме, приводит к последовательности задач с возрастающим значением целевой функции, неотрицательными коэффициентами 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и значениями 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 любого знака. Двойственный симплекс-метод называют методом последовательного улучшения оценок. Преобразования продолжаются до тех пор, пока не будет установлено, что исходная задача не имеет допустимого решения или будет получена задача с допустимым базисным планом (все 13 EMBED Equation.3 1415), который одновременно будет и оптимальным.
Этапы решения задач ЛП двойственным симплекс-методом
Привести исходную задачу к каноническому виду.
Исключить базисные переменные из целевой функции z.
Проверить приведенные коэффициенты целевой функции: если все приведенные коэффициенты 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, а среди значений 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 есть отрицательные, то задача решается симплекс методом. Если среди приведенных коэффициентов 13 EMBED Equation.3 1415 есть положительные, то в системе ограничений следует преобразовать свободные члены в неотрицательные, умножив на (-1) строки, содержащие 13 EMBED Equation.3 1415 и решить задачу прямым симплекс-методом.
Этапы решения задач ЛП двойственным симплекс-методом
Составить исходную таблицу Гаусса, записывая приведенные коэффициенты целевой функции в z-строку с противоположными знаками, а константу z0 со своим знаком.
Выяснить, имеется ли хотя бы одно отрицательное число в столбце свободных значений свободных членов. Если все 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, то полученное базисное решение и значение целевой функции, записанное в столбце свободных членов, дают оптимальное решение исходной задачи (так как по предположению 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415).
Среди отрицательных коэффициентов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 выбрать минимальный. Пусть это 13 EMBED Equation.3 1415. Следовательно, строка с номером l – ведущая и переменную 13 EMBED Equation.3 1415исключают из базиса.
В ведущей строке проверить знаки всех коэффициентов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, то исходная задача неразрешима в силу несовместности системы ограничений.
Среди отрицательных коэффициентов 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 ведущей строки выбрать минимальное двойственное отношение (отношение элементов z-строки, взятых со знаком «-», к соответствующим отрицательным элементам ведущей строки): 13 EMBED Equation.3 1415. Следовательно, столбец с номером k-ведущий, а элемент 13 EMBED Equation.3 1415 - разрешающий. Переменную 13 EMBED Equation.3 1415 включить в базис.
Пересчитать таблицу методом Жордана-Гаусса с ведущим элементом 13 EMBED Equation.3 1415 и перейти к пункту 2.
Пример 7. Решить задачу двойственным симплекс-методом (см. пример 5)
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Решение.
приведем задачу к каноническому виду, причем все элементы столбца свободных членов неотрицательны
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415;
для приведения задачи к предпочтительному виду умножим второе ограничение на «-1»
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
и получим базисное (но не опорное) решение – «псевдоплан»:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415;
так как все приведенные коэффициенты целевой функции неотрицательны:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, а среди значений свободных членов есть отрицательные (13 EMBED Equation.3 1415), задачу нужно решать двойственным симплекс-методом;
составим исходную двойственную симплекс-таблицу, определяем ведущую строку и ведущий столбец и выполняем шаг метода Жордана-Гаусса



поскольку в столбце значений свободных членов все элементы 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, то найден оптимальный план:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415






Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native(Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 8981824
    Размер файла: 474 kB Загрузок: 0

Добавить комментарий