|
Симплексный метод решения задачи линейного программированияТрудность решения задачи линейного программирования заключается в том, что не все модели задач можно свести к равносильным моделям с двумя переменными, а с большим количеством ― практически невозможно решить. Наиболее распространенным методом решения задач линейного программирования является так называемый симплекс-метод. Из геометрической интерпретации задача линейной оптимизации видно, что экстремум функции достигается в крайней (угловой) точке выпуклого многогранника, т.е. в области допустимых решений. Поэтому в основу симплекс-метода положена идея рассмотрения только крайних точек (вершин) многогранника, а не все бесконечное множество его точек. Симплексный метод это метод последовательного улучшения планов, который является универсальным методом решения задач линейного программирования. Суть этого метода заключается в том, что вначале получают допустимый план, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение), оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача. Результат каждой итерации (включая данные задачи) удобно записывать в виде симплексной таблицы (вид которой представлен при решении задачи примера 4). Направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи. Симплекс-метод основан на следующих свойствах ЗЛП: 1. Множество всех планов задачи линейного программирования выпукло. 2. Не существует локального экстремума, отличного от глобального. Другими словами, если целевая функция принимает экстремальное значение, то данное значение будет единственным. 3. Целевая функция задачи линейного программирования достигает своего максимального (минимального) значения в крайней точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек. 4. Каждой угловой точке многогранника решений отвечает опорный план задача линейной оптимизации. Предположим, что в симплексной таблице содержится некоторый опорный план (см. пример 4). Через конечное число шагов либо будет найден оптимальный план задачи, либо будет установлено неразрешимость задачи. Перебор опорных планов осуществляется в процессе перехода от одного базиса системы переменных к другому базису. При этом приходится определять переменные, участвующие в преобразовании базиса. Переменная, включаемая в базис в задаче максимизации определяется по отрицательному коэффициенту в строке целевой функции симплексной таблицы. Если таких коэффициентов несколько, то выбирают максимальный по модулю. Такую переменную называют разрешающей, а столбец коэффициентов при ней разрешающим. Для выбора переменной исключаемой из базиса составляют симплексные отношения: это отношение свободного коэффициента к элементу такого же знака разрешающего столбца. Наименьшее из них и указывает уравнение (разрешающее), в котором содержится исключаемая переменная. После выбора разрешающего столбца и разрешающей строки определяется на их пересечении разрешающий элемент и осуществляется преобразование модели задачи к новому базису. Симплексное преобразование после выбора разрешающего элемента при табличных записях выполняется по следующим правилам: 1) Разрешающий элемент (ark) заменяют обратной величиной (т.е. 1/аrk); 2) Остальные элементы разрешающей строки делятся на разрешающий элемент (а'rj = , j = ); 3) Остальные элементы разрешающего столбца делятся на разрешающий элемент и знак меняется на противоположный (a'ik = - , i = ); 4) Остальные элементы таблицы преобразовываются по правилу прямоугольника: искомый элемент равен разности произведений элементов главной и побочной диагоналей, деленной на разрешающий элемент (по воображаемому прямоугольнику пересчета) (a'ij = , i = , j = , i r, j k). Таким образом, получаем новый опорный план задачи в следующей симплексной таблице. А для того, чтобы определить является ли новый опорный план оптимальным, необходимо знать следующие признаки: Признак оптимальности задачи максимизации: Если все оценки индексной строки (строки целевой функции) не отрицательны, то соответствующий план является оптимальным в задаче максимизации. Признак оптимальности задачи минимизации: Если все оценки индексной строки (строки целевой функции) не положительны, то соответствующий план является оптимальным в задаче минимизации. В тех случаях когда затруднительно найти первоначальный опорный план канонической формы задачи линейного программирования применяется метод искусственного базиса (М – метод). Решим симплексным методом следующую задачу. Пример 4. Предприятие выпускает четыре вида продукции П1, П2, П3 и П4. Для производства продукции оно располагает тремя ресурсами, запасы которых ограничены величинами 35, 30 и 40 единиц. Удельные затраты на единицу продукции и цена единицы готовой продукции заданы в виде таблицы: Таблица 2
Требуется определить производственную программу предприятия, обеспечивающую максимальный доход. Решение: Составим математическую модель задачи. Пусть х1, х2, х3 и х4 ― искомые объемы производства продукции, а через f ― доход предприятия от производства и реализации всей продукции, который с учетом введенных обозначений определяется следующей функцией: f = 14х1+ 10х2+ 14х3+ 11х4 max. (4.1.) Ограничения по используемым ресурсам примут вид: 4х1+ 2х2+ 2х3+ 3х4 35, х1+ х2 + 2х3+ 3х4 30, (4.2.) 3х1+ х2+ 2х3+ х4 40. По смыслу задачи объемы производства продукции не могут быть отрицательными, поэтому хj 0, (j= . (4.3.) Введем в рассмотрение возможные остатки ресурсов: х5, х6, х7, или приведем модель задачи к каноническому виду и получим: f = 14х1+ 10х2+ 14х3+ 11х4 max 4х1+ 2х2+ 2х3+ 3х4 + х5 = 35, х1+ х2 + 2х3+ 3х4 + х6 =30, (4.4.) 3х1+ х2+ 2х3+ х4 + х7 = 40. хj 0, (j=
Нам необходимо выделить начальный базис системы, т.е. выделить базисные переменные. Базисных переменных должно быть столько, сколько ограничений системы линейных уравнений, т.е. в нашем случае их должно быть три. Наши дополнительные переменные х5, х6, х7 и будут базисными, так как им соответствуют единичные векторы, которые образуют базис в трехмерном пространстве. Выразим эти переменные и получим: х5 = 35 - (4х1+ 2х2+ 2х3+ 3х4), х6 = 30 - (х1+ х2 + 2х3+ 3х4), (4.5.) х7 = 40 – (3х1+ х2+ 2х3+ х4). Итак у нас х5, х6, х7 базисные переменные, а х1, х2, х3 и х4 будут свободными переменными. Приравнивая свободные переменные нулю мы получим х5 =35, х6 =30, х7 =40. Имеем некоторый допустимый план задачи = (0; 0; 0; 0; 35; 30; 40). Этот план удовлетворяет одновременно всем ограничениям задачи и следовательно является опорным планом. Занесем условия задачи в симплексную таблицу (таблица 3). Первый столбец ─ столбец базисных переменных (БП ─ х5, х6, х7); второй столбец ─ столбец свободных коэффициентов (1); далее идут столбцы свободных переменных (СП) ─ таких переменных в нашей задаче четыре (х1, х2, х3 и х4), они всегда записываются в (СП) со знаком "-". Чтобы правильно вписать коэффициенты в таблицу данного вида, надо придерживаться следующего правила: в соответствующей строке записываем числа так, чтобы при умножении их на соответствующее значение в "шапочке" таблицы мы получили бы выражения вида (4.5.) и (4.1.) Таблица 3
При решении задачи максимизации в строке целевой функции в столбцах свободных переменных не должно быть отрицательных коэффициентов. Мы видим, что в нашем случае, в столбцах свободных переменных в индексной строке присутствуют отрицательные коэффициенты, поэтому данный опорный план не является оптимальным. Будем улучшать его, переходя от одного базиса системы к другому. Выберем разрешающий столбец, как столбец, соответствующий наибольшей по модулю отрицательной оценке, т.е. max {│-14│; │-10│; │-14│; │-11│} = 14. Из двух одинаковых оценок выберем одну, например, столбец соответствующий свободной переменной х1, он и будет разрешающим столбцом. Затем находим разрешающую строку по наименьшему симплексному отношению: min { } = . На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент, выделяем его (мы выделили ячейку, в которой находится разрешающий элемент, равный 4). Строим следующую симплексную таблицу, меняя две переменные х1 и х5 местами и пересчитываем элементы по правилам симплексных преобразований. Таблица 4
Анализируя полученные результаты, мы видим, что пока ещё не получен оптимальный план, так как не все оценки строки целевой функции принимают неотрицательные значения. Повторим наши преобразования, выбрав разрешающий элемент, равный 6/4. В результате получим следующую таблицу. Таблица 5
Еще раз проводя преобразования с элементами данной таблицы, мы получим оптимальный план, который находится в таблице 6. Итак, в индексной строке последней таблицы нет ни одного отрицательного элемента, следовательно, содержащийся в ней план является оптимальным. Выпишем его, зная, что значения базисных переменных находится в столбце свободных коэффициентов, а все свободные переменные равны нулю: х2=5; х3=12,5; х7=10; х5=0; х1=0; х6=0; х4=0 или план =(0;5;12,5;0;0;0;10). Значение целевой функции равно 225. Таблица 6
Но наша задача с экономическим содержанием, поэтому проанализируем данные результаты. Предприятию по оптимальному плану следует производить 5 единиц продукции вида П2, 12,5 единиц продукции вида П3, продукции П1 и П4 выпускать не следует, при этом ресурсы Р1 и Р2 будут израсходованы полностью, а ресурс Р3 останется в количестве 10 единиц. Выручка предприятия при этом составит 225 ден.ед. ■ Теория двойственности в анализе оптимальных решений экономических задач линейного программирования Не менее важным этапом, чем получение оптимального решения по модели задачи, является анализ модели и полученных результатов. В некоторых случаях анализ дает больше информации для принятия решения, чем само решение. Анализ позволяет ответить на вопросы, связанные с повышением рентабельности предприятия, с распределением ограниченных (дефицитных) ресурсов между звеньями производства, с увеличением выпуска продукции путем рациональной расшивки узких мест производства, определения цен на взаимозаменяемую новую технику и др. Анализ на чувствительность дает возможность определить поведение модели в окрестности экстремума, а также пределы изменения исходных параметров, не изменяющих положение экстремума. Это позволяет сформулировать требования к точности исходных данных, а также упростить и уточнить модель, отрубив параметры, незначительно влияющие на конечный результат и уточнив параметры, находящиеся в области высокой чувствительности. И в этом нам поможет понятие двойственности. Рассмотрим основные понятия и выводы специального раздела линейного программирования ─ теорию двойственности на примере задачи планирования производством. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Вспомним задачу об оптимальном планировании производства из примера 4 темы 4. Модель задачи была построена ранее. f = 14х1+ 10х2+ 14х3+ 11х4 max. (5.1.) 4х1+ 2х2+ 2х3+ 3х4 35, х1+ х2 + 2х3+ 3х4 30, (5.2.) 3х1+ х2+ 2х3+ х4 40. хj 0, (j= . (5.3.) Предположим, что некоторая организация может закупить все ресурсы, которыми располагает предприятие. Необходимо определить оптимальные оценки на эти ресурсы, исходя из естественного условия,что покупающая организация стремится минимизировать общую оценку ресурсов. Нужно, однако, учитывать и тот факт, что за ресурсы покупающая организациядолжна уплатить сумму, не меньшую той, которую может, выручить предприятие при организации собственного производства продукции. Итак, предположим, что оставаясь в рамках производства в задаче необходимо установить оценки используемых в производстве ресурсов с учетом их влияния на конечный результат производства. Обозначим эти оценки за единицу каждого вида ресурса соответственно через y1; y 2 и y 3 (Р1, Р2, Р3). Эти оценки для упрощения иногда называют внутренними ценами на ресурсы в условиях данного производства (теневыми ценами). Т.е. они представляют объективно необходимые затраты на производство продукции в данных условиях. Понятно, что при их определении следует руководствоваться следующими соображениями: 1. Оценка ресурсов, затрачиваемых на выпуск единицы готовой продукции должна быть не меньше оценки единицы готовой продукции, т.е. П1: 4у1 + у2 + 3у3 14 П2: 2у1 + у2 + у3 10 (5.4.) П3: 2у1 + 2у2 + 2у3 14 П1: 3у1 + 3у2 + у3 11 2. Оценки по их смыслу должны выражаться не отрицательными числами, т.е. уi 0, i = (5.5.) 3. Для объективной оценки ресурсов необходимо требовать, чтобы общая стоимость всех ресурсов, находящихся в распоряжении предприятия, была возможно меньше, т.е. φ = 35 у1 + 30 у2 + 40 у3 min (5.6.) Итак, получили модель задачи: φ = 35 у1 + 30 у2 + 40 у3 min 4у1 + у2 + 3у3 14 2у1 + у2 + у3 10 (5.7.) 2у1 + 2у2 + 2у3 14 3у1 + 3у2 + у3 11 уi 0, i = Таким образом, проблема правильной оценки ресурсов находится в распоряжении предприятия и сводится к решению стандартной ЗЛП. Задача (5.7.) называется двойственной к задаче (5.1.) — (5.3). Эти две задачи представляют собой числовой пример пары симметричных двойственных задач. С экономической точки зрения в прямой задаче шла речь о нахождении оптимального плана выпуска продукции при ограничениях ресурсов из условия максимизации выручки. В двойственной задаче речь идет о нахождении системы внутренних цен на используемые в производстве ресурсы, из условия минимизации стоимости всех запасов имеющихся на предприятии. Система двойственных оценок (уi) тесно связана с конкретными условиями данного производства. С изменением этих условий меняется и система этих оценок. В общем виде модели симметричных двойственных задач имеют следующий вид:
Пусть нам дана задача линейной оптимизации в общем виде, тогда двойственная к ней примет вид:
Свойство двойственности является взаимным, т.е. если к задачам (I`) и (II`) записать двойственные, то они совпадут с задачами (I) и (II) соответственно. Любую задачу внутри двойственной пары можно назвать прямой или исходной, тогда другая будет двойственной к ней. Анализируя модели задач двойственной пары, можно сделать следующие выводы о связях, существующих между элементами модели задач двойственной пары: 1. Коэффициентами целевой функции двойственной задачи, являются свободные члены ограничений прямой задачи, а свободными членами ограничений двойственной задачи - коэффициенты целевой функции прямой задачи. В двойственной задаче будет столько переменных, сколько ограничений в прямой и столько ограничений, сколько переменных в прямой задаче. Таким образом, каждому ограничению задачи отвечает соответствующая переменная двойственной задачи и наоборот. 2. Матрицы коэффициентов при переменных в двойственных задачах взаимно транспортированы. 3. Каждому ограничению ─ неравенству в двойственной задаче отвечает неотрицательная переменная, а каждому ограничению равенству ─ переменная произвольного знака и наоборот: каждой неотрицательной переменной ─ ограничение неравенство, а каждой переменной произвольного знака ─ ограничение равенство. При этом в задаче максимизации ограничения-неравенства имеют смысл«», ав задаче минимизации ─ « ». 4. Если в прямой задаче функция целевая максимизируется, то в двойственной минимизируется и наоборот. Итак, согласно теории линейного программирования каждой оптимизационной задаче линейного программирования соответствует двойственная ей задача. Основные утверждения о взаимодвойственных задачах содержатся в следующих теоремах, называемых теоремами двойственности. Теорема 1 (основная).
Рассмотрим экономическое приложение этой теоремы. В действительности связь между двойственными задачами гораздо глубже, нежели об этом говорится в теореме. Оказывается, подвергая симплексному преобразованию модель одной из задач, мы тем самым преобразуем и модель двойственной задачи, а поэтому решая одну из задач двойственной пары симплексным методом, мы одновременно решаем и двойственную задачу, так что получив оптимальный план решаемой задачи, мы вместе с этим находим и компоненты оптимального плана двойственной задачи. Компоненты оптимального плана двойственной задачи находятся в строке целевой функции последней симплексной таблицы решенной задачи. Чтобы правильно выписать компоненты оптимального плана двойственной задачи необходимо учесть соответствие между переменными двойственных задач, устанавливаемое для канонических форм, в котором базисным переменным одной задачи отвечают свободные переменные другой и наоборот. Рассмотрим наш пример.
Так как исходная задача разрешима, то и двойственная будет иметь оптимальный план, который находится в последней симплексной таблице решенной задачи. Запишем соответствие между переменными задач:
Используя данное соответствие из таблицы 6 находим значения двойственных переменных, которые находятся в строке целевой функции под свободными переменными (это у1 ~ х5, у4 ~ х1, у7 ~ х4, у2 ~ х6), а все остальные переменные двойственной задачи будут равны нулю: у1 ~ х5 у = 3; у2 ~ х6 у = 4; у3 ~ х7 у = 0; у4 ~ х1 у = 2; у5 ~ х2 у = 0; у6 ~ х3 у = 0; у7 ~ х4 у = 10. Таким образом можно записать оптимальный план двойственной задачи: = (3; 4; 0; 2; 0; 0; 10), φmin = 225. С экономической точки зрения теорема 1 означает, что по оптимальному плану выпуска продукции все затраты внутри производства совпадают с оценкой готовой продукции, произведенной по этому плану, т.е. при оптимальном плане вся стоимость затрат внутри производства поглощается в стоимости готовой продукции. Т.е. затраты равны 35*3+30*4+40*0=225. Стоимость готовой продукции 14*0+10*5+14*12,5+11*0=225. Отсюда вытекает первое свойство двойственных оценок: двойственные оценки уi (i = ), — являются инструментом балансирования затрат и результатов. Рассмотрим следствие, вытекающее из первой теоремы, которое представлено в виде второй теоремы двойственности. Теорема 2 (о дополняющей нежесткости).
Условия (5.8.) и (5.9.) называются условиями дополняющей нежесткости. Из них следует, что если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство. В условиях нашего экономического примера это означает, что если ресурс получил положительную оценку (у1 = 3; у2 = 4), то этот ресурс считается дефицитным и весь будет израсходован при реализации оптимального плана. Если же ресурс израсходован не полностью, то его называют избыточным и он получит нулевую оценку (у3 = 0). Отсюда следует вывод или второе свойство двойственных оценок: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку. Причем, чем больше положительное значение двойственной переменной, тем дефицитнее ресурс. В нашем примере наиболее дефицитным ресурсом является ресурс Р2. Еще можно рассмотреть и другой случай: х = 5 > 0 2у +у +у = 2*3+4+1*0=10 = 10 т.е. выпуск по этому виду продукции оправдан. х = 0 4у +у +3у = 4*3+4+3*0 =16 > 14 следовательно, затраты выше, чем стоимость готовой продукции и данный вид продукции не выгодно производить. В условиях нашего экономического примера данные рассуждения интерпретируется так: в оптимальный план войдут только те виды продукции, затраты на которые внутри производства совпадут со стоимостью готовой продукции, и не войдут те виды, затраты на которые превышают стоимость готовой продукции. Таким образом, оценки позволяют оценить целесообразность выпуска тех или иных видов продукции, т.е. являются мерой убыточности при производстве не выгодных видов продукции (это третье свойство двойственных оценок). Пример 5. Проверить целесообразность выпуска продукции П5, если удельные затраты ресурсов составляют соответственно 5; 4; 6 условных единиц. Стоимость единицы продукции составляет 25 ден.ед. Решение. Найдем затраты на производство единицы продукции П5 5у +4у +6у = 5*3+4*4+6*0 = 31 ден.ед. Сравним со стоимостью готовой продукции: 31 > 25. Следовательно производство продукта П5 по такой цене не целесообразно. ■ Теорема 3 (об оценках).
Оценки показывают как изменяется экстремальное значение функции в зависимости от изменения правых частей ограничений задачи. На практике теорема чаще всего используется на языке конечных приращений: у (i= ) (5.11.) В такой записи применительно к нашей экономической задаче оценки показывают, на сколько изменится максимальная выручка предприятия, если запас дефицитного ресурса изменится на единицу. Таким образом, оценки являются мерой влияния ограничений задачи на экстремальное значение целевой функции (четвертое свойство двойственных оценок). Однако, как это свойство, так и все предыдущие остаются справедливыми до тех пор, пока, правые части ограничений задачи меняются в определенных пределах (пределах чувствительности). В нашем примере видно, что перспективными ресурсами являются ресурсы Р1 и Р2, т.к. вводя единицу ресурса Р1 в производство дополнительно, мы увеличиваем выручку на 4 денежные единицы. Пример 6. Предположим, что из производства исключается 2 единицы дефицитного ресурса Р2. Понятно, что выручка снизится. Какое количество взаимозаменяемого ресурса Р1 следует ввести в производство с тем, чтобы возместить уменьшение выручки. Решение: Выручка (по третьей теореме двойственности) уменьшится на 2*у =2*4=8 ден.ед. Эту же величину необходимо возместить за счет введения первого ресурса, т.е. 8=Δb1*у . Отсюда легко находим значение Δb1. Получаем Δb1=8/3. 8/3 единиц первого ресурса заменят недостаток второго. ■ Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|