Алгоритмы решения задач линейного программирования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Волгоградский государственный технический университет Кафедра «ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ и системы» И. А. Коптелова АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Методические указания к практическим занятиям по курсу «Методы оптимизации» Волгоград 2010 УДК Рецензент: канд. техн. наук, доцент кафедры «Электротехника» А. В.Емельянов Издается по решению редакционно-издательского совета Волгоградского государственного технического университета Алгоритмы решения задач линейного программирования: метод. указания / сост. И. А. Коптелова / ВолгГТУ. – Волгоград, 2010. – 25 с. В методических указаниях содержатся сведения, необходимые для изучения студентами методов линейного программирования, используемых для решения задач оптимизации технических систем. Методические указания предназначены для студентов, обучающихся по направлению «Информатика и вычислительная техника» и специальности «Вычислительные машины, комплексы, системы и сети» всех форм обучения. © Волгоградский государственный технический университет, 2010 1. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТАНДАРТНОЙ ФОРМЕ Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид: Максимизировать или минимизировать при ограничениях , , , , . Задачи ЛП в стандартной форме можно записать в компактных матричных обозначениях следующим образом: максимизировать или минимизировать при ограничениях , , , где A – матрица размерности , x – вектор-столбец размерности , b – вектор столбец размерности , а c – вектор строка размерности . Обычно A называется матрицей коэффициентов, x – вектором переменных, b – вектором ресурсов, c – вектором оценок задачи ЛП. При решении задач ЛП симплекс-методом требуется, чтобы задача была представлена в стандартной форме. Однако не все задачи ЛП имеют стандартную форму. Часто ограничения имеют вид не равенств, а неравенств. В некоторых задачах не все переменные можно считать неотрицательными. Таким образом, первый этап решения задачи ЛП состоит в приведении ее к стандартной форме. 1.1 Преобразование неравенств Ограничения в виде неравенств можно преобразовать в равенства при помощи введения так называемых остаточных или избыточных переменных. Например, неравенство вида (1) можно представить в равенство при помощи введения остаточной переменной S1: . Переменная S1 неотрицательна и соответствует разности правой и левой частей в неравенстве (1). Аналогично неравенство вида можно преобразовать в равенство путем введения избыточной переменной S2: . Дополнительные переменные так же необходимы, как и исходные переменные задачи. Дополнительные переменные могут принимать положительные значения, а их значения в оптимальном решении позволяют судить о том, являются ли ограничения в виде неравенств активными. 1.2 Преобразование неограниченных по знаку переменных В некоторых случаях возникает необходимость рассмотрения переменных, принимающих как положительные, так и отрицательные значения. Поскольку переменные задачи ЛП в стандартной форме предполагаются неотрицательными, неограниченные переменные следует заменить разность двух неотрицательных. Например, если s1 – неограниченная переменная, то используется следующая замена переменных: , , . Значение s1 может быть положительным или отрицательным в зависимости от соотношения величин и . Для иллюстрации рассмотрим следующую задачу ЛП, записанную в нестандартной форме. Пример 1. Максимизировать при ограничениях (2) (3) (4) где – переменная, не ограниченная по знаку. Преобразуем эту задачу к стандартной форме. 1. Заменим на , где . 2. Умножим обе части уравнения (4) на –1. 3. Введем дополнительные переменные и в ограничения (2) и (3) соответственно. 4. Припишем нулевой коэффициент переменным и , целевая функция при этом не меняется. Таким образом, рассматриваемая задача сводится к следующей задаче ЛП в стандартной форме: максимизировать при ограничениях . Используя стандартную форму задачи ЛП в матричных обозначениях: максимизировать при ограничениях , , можно сформулировать основные определения следующим образом. 1. Допустимое решение представляет собой неотрицательный вектор x, для которого выполняются ограничения . 2. Допустимая область, обозначаемая через S, состоит из всех допустимых решений. Формально это определение можно записать в следующем виде: . Если допустимая область S пуста, задача ЛП называется противоречивой. 3. Оптимальным решением называется такой допустимый вектор x0, для которого соответствующее ему значение целевой функции (cx0) больше, чем для любого другого допустимого решения. Таким образом, вектор x0 является оптимальным решением задачи тогда и только тогда, когда и для всех . 4. Оптимальное значение задачи ЛП представляет значение целевой функции, соответствующее оптимальному решению. Если Z0 – оптимальное значение, то . 5. Неединственность оптимального решения. В том случае, когда задача ЛП имеет более одного оптимального решения, говорят, что у нее имеются различные оптимальные решения. При этом существует более одного допустимого решения со значениями целевой функции, равными оптимальному (Z0). 6. Единственность оптимума. Говорят, что оптимальное решение задачи ЛП единственно, если не существует других оптимальных решений. 7. Неограниченный оптимум. В том случае, когда задача ЛП не обладает конечным оптимумом (т.е. или ), говорят, что задача имеет неограниченный оптимум. 2. ОСНОВЫ СИМПЛЕКС-МЕТОДА Рассмотрим общую задачу ЛП с m ограничениями и n переменными, записанную в стандартной форме: максимизировать при ограничениях , , , . Как правило, число уравнений задачи меньше числа переменных (т. е. m0. Однако правило минимального отношения оказывается неприменимым, поскольку в столбце, расположенном под переменной х1, нет положительных элементов. Это означает, что с увеличением х1 базисные переменные х2 и х3 также растут. Следовательно, переменная х1 может неограниченно увеличиваться.. Рассматриваемая задача ЛП имеет неограниченный оптимум. При возрастании х1 на единицу значение Z возрастает на 11 единиц, поэтому Z может неограниченно увеличиваться. Наличие неограниченного максимума при решении практических задач свидетельствует об ошибках при разработке модели ЛП, в частности о пропуске некоторых существенных для задачи ограничений. 3.3 Вырожденность и зацикливание Допустимое базисное решение, в котором одна или более базисных переменных равны нулю, называется вырожденным допусти­мым базисным решением. Допустимое базисное решение, в котором все базисные переменные положительны, называется невырожден­ным. Вырожденность может присутствовать в первоначальной фор­мулировке задачи (если некоторые правые части равны нулю); она может также возникать при симплексных вычислениях. Послед­нее происходит, когда, по крайней мере, две строки имеют одинаковые значения минимального отношения, вычисляемого по пра­вилу (10). При вырожденности допустимого базисного решения минималь­ное отношение может оказаться нулевым. В этом случае изменение базиса не влияет на значение целевой функций, В действительности встречаются задачи, в которых несколько итераций симплекс-ме­тода не приводят к улучшению значения Z. Это означает, что вы­полняются трудоемкие вычисления с симплексными таблицами, не дающие реального эффекта. Естественно, что при таких условиях вычислительная эффективность симплекс-метода снижается. Еще более важен вопрос, возможно ли выполнение неограниченного числа итераций симплекс-методом без продвижения к оптимуму. Имеются примеры, показывающие, что теоретически такая ситуа­ция возможна. В этом случае вычисления по симплекс-алгоритму зацикливаются и не приводят к оптимальному решению. Это явле­ние носит название классического зацикливания или просто зацикли­вания. В практических задачах зацикливания не происходит, не­смотря на вырожденность некоторых промежуточных решений. 4. Метод искусственных переменных Наличие начального допустимого базисного решения канони­ческой системы равнений представляет собой необходимое условие применимости симплекс-метода. Без этого невозможно построить начальную симплексную таблицу. Для получения системы в кано­ническом виде, обладающей допустимым базисным решением, существует специальный метод. Сначала задача ЛП приводится к стандартной форме, в которой все переменные неотрицательные, ограничения имеют вид равенств, правые части неотрицательные. Затем для каждого ограничения проверяется существование соответствующей базисной переменной; Если ее нет, вводится новая переменная, играющая роль базисной для данного ограничения. После проверки всех ограничений получается система в каноническом виде, поскольку каждому ограничению соответствует своя базисная переменная и появляется возможность заполнить началь­ную симплексную таблицу. Вводимые таким образом переменные не имеют отношения к задаче ЛП в исходной постановке, а служат лишь для приведения системы ограничений к каноническому виду, который необходим при использовании симплекс-алгоритма. Такие переменные называются искусственными в отличие от управляемых переменных задачи. В оптимальном решении искусственные пере­менные должны обращаться в нуль, поскольку в противном случае ограничения задачи будут нарушены. Проиллюстрируем способ использования искусственных переменных на следующем примере. Пример 4. Минимизировать , При ограничениях , , , Сначала задача преобразуется к стандартной форме: Минимизировать При ограничениях , , В первом уравнении дополнительная переменная x4 - базисная. Поскольку в других уравнениях нет базисных переменных, вводятся искусственные переменные x6 и x7, являющиеся базисными для второго и третьего урав­нений соответственно. Для сохранения стандартной формы задачи переменные x6 и x7 предполагаются неотрицатель­ными. Тогда получается следующая вспомогательная система: . Вспомогательная система имеет следующее допустимое базисное решение: Это решение недопустимо для первоначальной задачи, поскольку искусственные переменные x6 и x7 положительные. С другой стороны, любое допустимое базисное решение вспомогательной системы, в котором x6 и x7 равны нулю, допустимо для исходной задачи. Таким образом, необходимо добиться обращения в нуль искусственных переменных. Этого можно достигнуть при помощи двухэтапного симплекс метода. Двухэтапный симплекс-метод. В случае введения искусственных переменных применяется двухэтапный симплекс-метод, т. е. задача ЛП решается в два этапа. Этап 1. На этом этапе находится начальное допустимое базисное решение первоначальной задачи. Другими словами, производится исключение искусственных переменных. С этой целью рассматривается искусственная целевая функция, равная сумме искусственных переменных, которая минимизируется при помощи симплекс-метода. Задача ЛП, рассматриваемая на первом этапе, при применении двухэтапного симплекс-метода к задаче примера 4 формулируется следующим образом (через W обозначена вспомогательная целевая функция). Задача этапа 1 Минимизировать При ограничениях . Исходная целевая функция на этапе 1 не рассматривается. Если минимальное значение вспомогательной задачи равно нулю, то все искусственные переменные обращаются в нуль, и получается допустимое базисное решение начальной задачи. (Примечание: если сумма неотрицательных переменных равна нулю, то каждая переменная также тождественно равна нулю). Далее реализуется этап 2. Если минимальное значение вспомогательной задачи положительное, то, по крайней мере, одна из искусственных переменных также положительная, что свидетельствует о противоречивости начальной задачи, и вычисления прекращаются. Этап 2. На этом этапе допустимое базисное решение, найденное на этапе 1, улучшается в соответствии с целевой функцией исходной задачи ЛП. Другими словами, оптимальная таблица этапа 1 превращается в начальную таблицу этапа 2; кроме того, изменяется целевая функция. Для поиска оптимального решения применяется симплекс метод. 5. Проблема двойственности в линейном программировании Рассмотрим прямую и двойственную задачи линейного программирования и те экономические понятия, которые с этим связаны. Прямая задача. Требуется, чтобы был достигнут максимум (12) при соблюдении ограничений (13) где - уровень деятельности ; - коэффициент оценки деятельности (например, прибыль на единицу продукции); -объем фактора производства (например, число рабочих, мощность машин, сводная площадь для культур и т. д.); - производственное потребление фактора деятельностью на уровне единицы (например, число рабочих на тонну товара при деятельности ). Двойственная задача. Требуется минимизировать (14) при соблюдении ограничений , (15) где , и - постоянные; - переменные, значения которых прояснятся далее: . Запишем обе задачи в матричных обозначениях. Прямая задача: (16) при соблюдении ограничений (17) Двойственная задача: (18) ограничения (19) где - матрица технических коэффициентов ; и - векторы-столбцы; - транспонированная матрица и т. д. Между прямой и двойственной задачами может быть связь, известная как теорема двойственности, согласно которой: если существует решение для прямой задачи (для которой во всяком случае необходимо, чтобы было ), то имеется и для двойственной и при этом , т. е. максимум функции цели прямой задачи равен минимуму функции цели двойственной. Существует способы (например, алгоритм симплекс-метода), с помощью которых можно вычислить требуемый максимум (или минимум) при данных условиях. Процесс вычисления нам известен, представляет интерес его результат. В случае прямой задачи величины , полученные при решении, представляют собой уровни деятельности, т. е. объемы производства в различного рода деятельностях. Но что такое величины , полученные при решении двойственной задачи? Ограничения (15) задачи, двойственной к (12) и (13), таковы: (20) Очевидно, что между переменными в левой части неравенств и константами должно быть качественное соответствие: они должны иметь сходное значение. Если константы показывают прибыль, тогда и должен иметь подобный смысл, если - цена, то и должен показывать цену и т. д. На первый взгляд кажется, что с экономической точки зрения эти рассуждения сугубо искусственны, однако они имеют особое теоретическое и практическое значение. И тем более потому, что с того момента, как коэффициенты получают точное материальное определение, единственными элементами, которые с экономической точки зрения могут иметь содержание, аналогичное коэффициентам в правой части неравенств, являются . В качестве примера можно привести программу максимизации прибыли (проблема прибыли рассматривается только как пример, для других проблем двойственная программа может интерпретировать аналогично). В прямой задаче процесс на единицу имеет прибыль и технические коэффициенты составляют ограничения двойственной задачи: . Имея в виду тот факт, что это ограничение (вместе с другими ограничениями) определяет минимальную величину выражения , в котором каждое является ресурсом (производственная мощность, сырья и т. д.), каждый может рассматриваться как критерий оценки соответствующего ресурса. Речь, разумеется, идет не о “величине” этого ресурса, а об его относительном вкладе в изменение величины и соответственно . Из теоремы двойственности вытекает, что любой прирост (или снижение) на единицу ведет к приросту (или к сокращению) на величину значений или . Предположим, что в линейной программе ограничение возрастает на , при этом все другие ресурсов остаются неизменными. В этом случае изменение программы можно записать следующим образом: (21) Целевая функция задачи, двойственной к этой, изменится следующим образом: . (22) Таким образом, соответствует увеличению на одну единицу величины ресурса с номером . В этом случае величины из решения двойственной задачи становятся показателем влияния изменения величины каждого ресурса на величину целевой функции. Они сами не являются непосредственно “величинами”, т. е. ценой, прибылью, стоимостью, поступлением и т. д., а представляют собой их отражение или “тени”, в связи с чем их называют часто теневыми ценами. Факторы появились в качестве переменных величин, а “теневые цены” стали постоянными. В этом случае результат (или ) производственной деятельности являются результатом комбинации факторов: (23) или точнее (24) По существу, (23) и (24) – производственные функции, и, следовательно, Это означает в анализируемом случае, что “теневая цена” идентична предельной эффективности фактора, к которому она относится. ЗАДАЧИ И КОНТРОЛЬНЫЕ ВОПРОСЫ ДЛЯ ПРОВЕРКИ 1. В чем состоит различие между симплекс-методом и методом полного перебора вершин области, задаваемой ограничениями? 2. Какова роль правила минимального отношения в симплекс-методе? 3. Как при помощи симплекс-метода определить, что задача ЛП имеет неограниченный оптимум? 4. Какова роль правила скалярного произведения в симплекс-методе? 5. Что такое «искусственные» переменные и для чего они служат? В чем их отличие от «остаточных» (избыточных) переменных? 6. Что такое анализ чувствительности и для чего он применяется? 7. Преобразуйте следующую задачу ЛП к стандартной форме: минимизировать Z=-3x1+4x2-2x3+5x4 при ограничениях 4x1-x2+2x3-x4=-2, x1+x2+3x3-x4≤14, -2x1+3x2-x3+2x4≥2, x1≥0, x2≥0, x3≤0, x4 не ограничена по знаку. 8. Рассмотрите следующую задачу ЛП: максимизировать Z=2x1-x2+x3+x4 при ограничениях –x1+x2+x3+x5=1, x1+x2+x4=2, 2x1+x2+x3+x6=6, x1,…, x6≥0. а) Запишите начальное допустимое базисное решение. б) Найдите допустимое решение, в котором небазисная переменная x1 обратится в единицу (а переменные x2 и x3 останутся нулевыми). Каково результирующее изменение значения целевой функции? в) Насколько может возрасти переменная x1, не нарушая ограничения? 9. Решите следующую задачу при помощи симплекс-метода: Максимизировать Z=x1+3x2 При ограничениях x1≤5, x1+2x2≤10, x2≤4, x1, x2≥0. Изобразите допустимую область в координатах (x1, x2). Проследите за движением от одного допустимого базисного решения к другому на графике, в соответствии с последовательностью шагов симплекс-метода. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Партыка, Т. Л. Математические методы: учебник [Текст] / Т. Л. Партыка, И. И. Попов. – М. : ФОРУМ: ИНФРА-М, 2005. – 464 с. 2. Реклейтис, Г. Оптимизация в технике [Текст]: в 2 т. / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел; перевод с англ. - М. : Мир, 1986. – 670 с. 3. Таха, Х. Введение в исследование операций [Текст]: в 2 т. / Х. Таха. – М. : Мир, 1985. Ирина Александровна Коптелова АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Методические указания к практическим занятиям по курсу «Методы оптимизации» Темплан … г. Поз. № … Подписано в печать … . Формат 60×84 1/16. Бумага газетная. Гарнитура Times. Печать офсетная. Усл. печ. л. Тираж … экз. Заказ Волгоградский государственный технический университет 400131, г. Волгоград, пр. Ленина, 28. Отпечатано в типографии ВолгГТУ 400131, г. Волгоград, ул. Советская, 35.