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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА имени адмирала С.О. МАКАРОВА КАФЕДРА МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И ПРИКЛАДНОЙ ИНФОРМАТИКИ УТВЕРЖДАЮ Заведующий кафедрой д.т.н., доцент С.В. Колесниченко 31. августа 2020г. ЛЕКЦИЯ№3 ТЕМА: ЛИНЕЙНОЕ ПРОГРАМИРОВАНИЕ НАПРАВЛЕНИЕ ПОДГОТОВКИ: УЧЕБНАЯ ДИСЦИПЛИНА: 09.03.03. ПРИКЛАДНАЯ ИНФОРМАТИКА Б1.В.ОД.6 ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ ОПТИМИЗАЦИИ Обсуждена на заседании кафедры Протокол № 01 от 31 августа 2020 Разработал: Профессор кафедры, к.в.н., доцент А.А. БУРЫКИН Санкт-Петербург  2020 УДК 519.876.3 ББК 22.18 Рецензент: Земсков А.В. доктор технических наук, профессор ГУМРФ имени адмирала С.О. Макарова Бурыкин А.А., Линейное программирование: фондовая лекция по дисциплине «Исследование операций и методы оптимизации» СПб: ГУМРФ имени адмирала С.О. Макарова, 2020. 11с. УДК ББК 519.876.3 22.18  Бурыкин А.А., 2020.  ГУМРФ имени адмирала С.О. Макарова, 2020. 2 ВВЕДЕНИЕ Вводная часть На изучение данной темы лекции отведено  2 часа лекционных занятий и 1 час самостоятельной работы. Актуальность темы Начало исследованиям задач линейного программирования в 1820 году положил французский математик и физик Жан Батист Фурье, который опубликовал ряд работ, посвященных изучению задач поиска экстремума функций при наличии ограничений типа неравенств. В 1939 году советский академик Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой в общей форме заложил основы линейного программирования, сформулировав новый класс экстремальных задач с ограничениями и разработав эффективный метод их решения. Концепции Л.В. Канторовича вскоре после войны были переоткрыты на западе. Одним из основоположников линейного программирования, считается и американский математик Джордж Бернард Данциг, который в 1947 году разработал алгоритм решения задач линейного программирования, названный «симплекс метод» и ввел термин «математическое программирование». Несмотря на то, что Данциг сделал свое открытие намного позже, советского коллеги, к своим результатам исследования он пришел самостоятельно. Предтечей же «симплекс-метода» можно считать метод разрешающих множителей, описанный в 1797-1801 году Жозефом Луи Лагранжем и работы венгерских математиков Эйгена Эгервари и Денеша Кёнига в 1931 году разрешивших задачу, называемую проблемой выбора. А также труд американского ученого Г.У. Куй, обобщившего этот метод, после чего он получил название венгерского метода. Американский экономист Т. Купманс в течении многих лет занимался задачами о нахождении экстремумов линейных функций, задаваемых линейными неравенствами. По его предложению этот раздел математики получил название линейного программирования. Широкое использование этого метода подкрепляется высокоэффективными компьютерными алгоритмами, реализующие аналитические и численные методы решения задач линейного программирования. Конкретная цель Тема лекции направлена на ознакомление студентов с постановкой, свойствами и особенностями решения задач линейного программирования. Пояснение плана лекции В лекции рассматриваются следующие основные вопросы: 1. Постановка задачи линейного программирования. 2. Свойства задачи линейного программирования. 3. Особенности решения задачи линейного программирования. 3 1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАМИРОВАНИЯ Линейное программирование (ЛП) – это раздел математического программирования, изучающий задачи условной оптимизации, когда целевая функция и функции ограничения выражены в линейной форме. Чтобы обеспечить линейность модели экономического процесса необходимо принять некоторые допущения (аксиомы линейности):  Делимость. Для каждого экономического процесса суммарное количество каждого из потребляемых ресурсов и соответствующая прибыль строго пропорциональны объёму выпускаемой продукции, т.е. все показатели экономического процесса, могут быть увеличены или уменьшены при сохранении их взаимной пропорциональности.  Аддитивность. Если значение каждой из управляемых переменных определено, то полное количество каждого из потребных ресурсов равняется сумме одноименных ресурсов, затраченных при реализации применяемых экономических процессов, а полная прибыль равняется сумме прибылей, получаемой в результате реализации этих процессов. Постулирование свойств делимости и аддитивности эквивалентно утверждению о том, что соответствующая математическая модель может быть представлена в виде линейных соотношений. В более определённой интерпретации в экономике сформулированные выше аксиомы означают, что доходы строго пропорциональны затраченным ресурсам, а непропорциональный эффект оказывается невозможным. В реальных ситуациях сформулированные выше постулаты, позволяющие использовать линейные модели, могут оказаться справедливыми или приближённо, или с достаточной степенью точности, но результаты их анализа позволяют выявить определённые закономерности и дать исчерпывающую информацию, необходимую лицу принимающее решение для нахождения эффективного решения. К настоящему времени разработано пять видов задач линейного программирования (далее – ЗЛП) (см. рис. 1.): Линейное программирование Детерминированное Целочисленное Стохастическое Параметрическое Целевое Рисунок 1. – Классификация задач линейного программирования  если в ЗЛП все неизвестные переменные имеют однозначность, то имеем задачу детерминированного линейного программирования;  если в ЗЛП все или некоторые неизвестные переменные должны принимать целочисленные значения, то имеем задачу целочисленного линейного программирования;  если в ЗЛП все или некоторые неизвестные переменные теряет однозначность и становиться случайными, то имеем задачу стохастического линейного программирования;  Параметрическое линейное программирование – применяется для расширения техники анализа чувствительности. Анализ чувствительности оптимального решения ЗЛП используется для нахождения нового оптимального решения для некоторого критического параметра 4 tr при котором новое оптимальное решение для любых значений t > t r остаётся неизменным либо решения не существует;  Целевое линейное программирование – применяется для нахождения оптимального компромиссного решения, учитывающего важность каждой конфликтующей целевой функции. Различные процедуры и алгоритмы реализации ЗЛП разработаны применительно к определённой форме математической записи. ЗЛП записывается в стандартной или канонической форме, предполагая выполнение следующих требований:  все линейные ограничения преобразуются с неотрицательной правой частью;  все переменные неотрицательны;  целевую функцию следует минимизировать или максимизировать. Общая (смешанная) форма записи ЗЛП. Выполняя эти требования задача линейного программирования ставиться следующим образом: Найти неотрицательные значения неизвестных переменных х1, х2, х3, … , хn обращающих линейную форму ЦФ в максимум (минимум) y( x)   c j  x j  max (min), при xj  X (1) j удовлетворяющих системе линейных ограничений: неравенств, задающих условия решения задачи a ij  x j  ()bi j и ограничений на переменные xj  0 где аij – заданные постоянные величины; bi – численные значения ограничений; cj – условная стоимость; i  1, m ; j  1, n . Стандартная форма записи ЗЛП. Выполняя эти требования задача линейного программирования ставиться следующим образом: Найти неотрицательные значения неизвестных переменных х1, х2, х3, … , хn обращающих линейную форму ЦФ в максимум y( x)   c j  x j  max , при xj  X j удовлетворяющих системе линейных ограничений: неравенств, задающих условия решения задачи a ij  x j  bi j и ограничений на переменные xj  0 5 (2) где аij – заданные постоянные величины; bi – численные значения ограничений; cj – условная стоимость; i  1, m ; j  1, n . Пример: Примером такой задачи может служить задача максимизации прибыли предприятия. Для изготовления каждого из n видов продукции употребляется m видов сырья, при чем расход i  ого вида сырья на единицу j  ого вида продукции составляет aij единиц. Прибыль на единицу продукции j  ого вида составляет C j   рублей. Определить, сколько единиц x j j  1, n продукции каждого вида следует изготовить предприятию при   условии получения максимальной прибыли, если в его распоряжении имеется bi i  1, m единиц сырья каждого вида. Векторный вид записи ЗЛП: n у  x    c j x j  max (3) j 1 n P x j 1 где j j  P0 , Pj   a1 j ,..., amj  – векторы-столбцы из коэффициентов ограничений; T P0   b1...bm  – вектор-столбец из правых частей ограничений. T Часто удобнее использовать векторно-матричное обозначение, тогда стандартную форму ЗЛП можно представить в следующем виде: y  с  х  max (4) А х  b x0 где А – матрица порядка m  n; b – m-мерный вектор-столбец; c – n-мерная вектор-строка. Каноническая форма записи ЗЛП. Выполняя эти требования задача линейного программирования ставиться следующим образом: Найти неотрицательные значения неизвестных переменных х1, х2, х3, … , хn обращающих линейную форму ЦФ в минимум y   c j  x j  min, при x j  X (5) j удовлетворяющих системе линейных ограничений: уравнений, задающих условия решения задачи a ij  x j  bi i и ограничений на переменные xj  0 К такой канонической форме записи можно свести любую стандартную форму задачи линейного программирования и обратно. 6 Преобразование задачи максимизации в задачу минимизации. Если в ЗЛП требуется найти не минимум, а максимум ЦФ, то сведение ЗЛП к канонической форме записи состоит в замене ЦФ величиной с обратным знаком: y *   y   c j  x j   c j  x j  min * (6) В этом случае max y  min y , т.е. задача максимизации функции у эквивалентна задачи минимизации функции у*, поскольку при решении обеих задач предоставляется один и тот же набор значений переменных. Преобразование неравенств в равенства. Если по условиям задачи линейные ограничения j j * выражаются в виде неравенств (,), то сведение ЗЛП к канонической форме записи заключается во введении дополнительных неизвестных. В первом случае они вычитаются из первой части неравенства, а во втором случае прибавляются. Добавляемая переменная называется остаточной переменной, а вычитаемая переменная – избыточной. Так, например, неравенства типа a ij  x j  bi (7) i a ij  x j  bi i заменяются соответственно на уравнения  aij  x j  xnk  bi i a ij (8)  x j  x n  k  bi i где k  1, m Правую часть неравенства всегда можно сделать неотрицательной путём умножения всего неравенства на (-1). Пример Неравенство - 2 > - 4 после умножения на (-1) становиться неравенством 2 < 4. ЗЛП, представленную в канонической форме, всегда можно свести к стандартной форме, осуществляя преобразование задачи минимизации в задачу максимизации1 и используя эквивалентность системы неравенств в системе равенств. Преобразование равенств в неравенства. Данное преобразование осуществляется с помощью одного дополнительного ограничения. Система линейных уравнений-ограничений (8) в этом случае записывается в виде системы неравенств-ограничений: a ij  x j  bi (9) i   aij   x j   bi i 1 j i Данное преобразование осуществляется так же, как и в первом случае 7 Таким образом, путём простых преобразований любую ЗЛП можно свести к той или иной форме записи и применить процедуру (метод) её решения. 2. СВОЙСТВА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Свойства ЗЛП связаны со свойством выпуклых множеств2: 1. Ограничения в ЗЛП записываются в виде уравнений или в виде нестрогих неравенств. Поэтому допустимое множество решений замкнутое. Если система линейных ограничений совместна, то данное допустимое множество решений ЗЛП выпукло, так как оно является пересечением выпуклых множеств переменных, задаваемых отдельно взятыми линейными ограничениями. Т.е. данное множество образует выпуклый многогранник решений. 2. Целевая функция линейна, поэтому её можно считать, как выпуклой, так и вогнутой функцией. Таким образом, можно утверждать, что оптимум в ЗЛП всегда является глобальным и достигается в граничной экстремальной точке замкнутого выпуклого допустимого множества решений. Т.е. целевая функция ЗЛП принимает максимальное значение в одной из вершин многогранника решений при условии, что функция ограничена сверху на множестве решений. Другими словами, не существует локального экстремума, отличного от глобального, и он единственный. 3. Число граничных точек всегда конечно, поэтому ЗЛП всегда может быть решена за конечное число шагов простой оценкой ЦФ в каждой точке и выбором из них оптимальной. Если ЦФ принимает своё оптимальное значение более чем в одной граничной точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек. 4. Каждой граничной точке многоугольника решений отвечает начальное решение. Перечисленные свойства ЗЛП проиллюстрируем на примере (см. рис.2): Пример: Рисунок 2 – Ограничения задачи, пересечение которых определяет ОДР На рис. 2 представлены три ограничения, заданные прямыми С1, С2, С3. Знаки неравенств выбраны таким образом, чтобы определяемые ими множества переменных лежали по ту же сторону от границы, что и начало координат. Учитывая неотрицательность переменных, получим допустимое множество решений ОЕ 1Е2Е3Е4. Точки О, Е1, Е2, Е3, Е4 являются граничными экстремальными точками. Множество называется выпуклым, если для любых точек х1 и х2 множеству принадлежит отрезок õ1  (1   ) õ2 при всех 0   1, т.е. отрезок, соединяющий любые две точки этой области, лежит всеми своими точками внутри данной области. 2 8 Легко увидеть, что никакая из этих точек не лежит на прямой, соединяющей две другие экстремальные точки множества. В то же время любая другая граничная точка лежит на прямой, соединяющей экстремальные точки, и любая внутренняя точка принадлежит прямой, соединяющей граничные точки. А поэтому задача может быть решена простой оценкой ЦФ в каждой экстремальной точке и выбором оптимальной. Структура задачи линейного программирования существенно зависит от ранга системы ограничений. Ранг системы (r) – это общий ранг матрицы системы и её расширенной матрицы, в том случае, когда система линейных ограничений совместна. Т.е. ранг системы представляет собой не что иное, как число линейно-независимых ограничений задачи. Очевидно, что ранг системы не может быть больше общего числа линейных ограничений r  m , и не может быть больше общего числа переменных r  n . Если число неизвестных переменных меньше числа линейных ограничений n  m , то задача вообще не имеет решения, т.к. в этом случае нельзя найти неизвестные хj удовлетворяющие всем ограничениям, а значит ЗЛП неразрешима. При числе неизвестных переменных равном числу линейных ограничений ЗЛП может иметь только одно решение при условии, что определитель матрицы системы отличен от нуля. Наличие же единственного решения исключает необходимость оптимизации, и этот тривиальный случай не может нас интересовать. Если по условию задачи целевая функция или система линейных ограничений нелинейные, то для их линеаризации используется один из следующих способов:  применение формализованного метода линеаризации (методы логарифмирования, разложения в ряд и т.д.);  включение допущений при постановке задачи, позволяющих исключить нелинейные зависимости;  комбинирование двух вышеописанных способов. Таким образом, можно сделать следующие выводы: 1. Оптимум ЗЛП может достигаться либо в одной экстремальной точке, либо на множестве экстремальных точек. 2. Задача оптимизации имеет смысл, когда ЗЛП имеет множество решений удовлетворяющих системе ограничений при m < n. Из вышеизложенного следует, что экономико-математическая постановка задачи (далее − ЭМПЗ) должна обеспечить применение метода линейного программирования, а это возможно только в том случае, когда менеджер (руководитель) понимает сущность ЗЛП и знает особенности методов её решения. 3. ОСОБЕННОСТИ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Возможность применения того или иного метода решения ЗЛП решающим образом зависит от вида целевой функции и ограничений задачи. Все многообразие методов можно свести в три большие группы (см. рис. 3.): 9 Методы решения ЗЛП Графический Аналитические Численные Точные Приближенные Рисунок 3. – Классификация методов решения ЗЛП 1. Графический метод – характеризуется тем, что позволяет наглядно показать основные свойства решений ЗЛП и применяется в простейшем случае, когда число неизвестных превосходит число ограничений не более чем на две единицы ( n  m  2 ). 2. Аналитические методы – характеризуются тем, что используют классический аппарат дифференциального и вариационного исчисления. 3. Численные методы – характеризуются тем, что учитывают предшествующую информацию для построения улучшенных решений задачи при помощи итерационных процедур. Численные методы делятся на две подгруппы: a. Точные методы – характеризуются тем, что в результате итерационных процедур мы получаем строго оптимальное решение (наиболее известные из них: симплекс-метод, венгерский метод, метод сокращения невязок, метод уточнения оценок.) b. Приближенные методы – характеризуются тем, что в результате итерационных процедур мы получаем приближение (не строго) к оптимальному решению (наиболее известные из них: индексный метод, метод простейших аппроксимаций). ЗАКЛЮЧЕНИЕ Таким образом, в процессе изучения лекции Вы выяснили сущность ЗЛП, выявили свойства ЗЛП и определили особенности её решения различными методами. ЛИТЕРАТУРА а) Основная: 1. Экономико-математические методы и модели в управлении водным транспортом: Линейное программирование: Учебное пособие. / под редакцией профессора В.А. Бабурина. СПБ.: СПГУВК, 2012. 206с. 2. Кремер Н.Ш., Исследование операций в экономике: Учебное пособие. М.: Юрайт, 2010. 432с. 3. Есипов Б.А., Методы исследования операций: Учебник для Вузов. М.: Лань, 2010. 256с. б) Дополнительная: 4. КРЕМЕР Н.Ш, ПУТКО Б.А., ФРИДМАН М.Н., Исследование операций в экономике: учебное пособие. – Москва: ЮНИТИ, 2006. 10 5. ХЭМДИ А. ТАХА, Введение в исследование операций. - Москва: ВИЛЬЯМС, 2001г. 6. БЕРЕЖНАЯ Е.В, БЕРЕЖНОЙ В.И., Математические методы моделирования экономических систем: учебное пособие. - Москва: Финансы и кредит, 2001. 7. ВЕНТЦЕЛЬ Е.С., Исследование операций: учебное пособие. М.: Советское радио, 1972. Профессор кафедры математического моделирования и прикладной информатики, к.в.н., доцент 31 августа 2020г. 11 А.А. БУРЫКИН