Графический метод решения задачи линейного программирования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА имени адмирала С.О. МАКАРОВА ИНСТИТУТ ВОДНОГО ТРАНСПОРТА КАФЕДРАМАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И ПРИКЛАДНОЙ ИНФОРМАТИКИ УТВЕРЖДАЮ Заведующий кафедрой д.т.н., доцент 31. августа 2020г. С.В. Колесниченко Л Е К Ц И Я №3 ТЕМА: ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НАПРАВЛЕНИЕ ПОДГОТОВКИ: 09.03.03. ПРИКЛАДНАЯ ИНФОРМАТИКА УЧЕБНАЯ ДИСЦИПЛИНА: Б1.О.21 ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ ОПТИМИЗАЦИИ Обсуждена на заседании кафедры Протокол № 01 от 31 августа 2020 Разработал: Профессор кафедры, к.в.н., доцент А.А. БУРЫКИН Санкт-Петербург  2020 УДК 519.876.3 ББК 22.18 Рецензент: Земсков А.В. доктор технических наук, профессор ГУМРФ имени адмирала С.О. Макарова Бурыкин А.А., Графический метод решения задачи линейного программирования: Фондовая лекция по дисциплине «Исследование операций и методы оптимизации». СПб: ГУМРФ имени адмирала С.О. Макарова, 2020.11с. УДК ББК 519.876.3 22.18  Бурыкин А.А., 2020.  ГУМРФ имени адмирала С.О. Макарова, 2020. 2 ВВЕДЕНИЕ Вводная часть Лекция №3 является частью раздела I «Методы оптимизации». На изучение данной темы лекции отведено  2 часа лекционных занятий и 1 час самостоятельной работы. Актуальность темы Геометрическая интерпретация экономических задач даёт возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. Конкретная цель Тема лекции направлена на ознакомление студентов с решением задачи линейного программирования графическим методом. Пояснение плана лекции В лекции рассматриваются следующие основные вопросы: 1. Сущность и особенности решения ЗЛП графическим методом. 2. Построение области допустимых решений. 3. Нахождение оптимального решения. 1. СУЩНОСТЬ И ОСОБЕННОСТИ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ Графический метод решения задачи линейного программирования основан на её геометрической интерпретации и применяется при решении задач двумерного пространства. Графически могут решаться задачи, с числом свободных переменных 𝑛−𝑚 2 (1) где n  количество переменных; m  количество ограничений. Задача линейного программирования ставиться следующим образом: Найти точку многогранника решений, в которой целевая функция у = const в зависимости от условий решения задачи достигает экстремального значения. Для геометрической интерпретации ЗЛП на плоскости необходимо произвести выбор координатных переменных. Если в ЗЛП число неизвестных переменных равняется двум, то данные переменные являются координатными. Если в ЗЛП число переменных больше трёх, то необходимо выбрать две линейно-независимые неизвестные переменные, которые будем называть координатными переменными. Неизвестные переменные считаются линейно-независимыми, когда определители, составленный из коэффициентов при них отличны от нуля. Далее, используя элементарные методы преобразования, осуществляется представление целевой функции и ограничений через координатные переменные. После преобразования ЗЛП через координатные переменные можно приступить к решению задачи. Графический метод решения ЗЛП состоит из двух этапов: 1. Первый этап построение области допустимых решений (выпуклого многогранника решений). 2. Второй этап нахождение оптимального решения среди всех точек области допустимых решений. 3 2. ПОСТРОЕНИЕ ОБЛАСТИ ДОПУСТИМЫХ РЕШЕНИЙ По двум точкам осуществляется построение преобразованных линейных ограничений на плоскости. Все построенные ограничения нумеруются в той последовательности, как они записаны в ЗЛП. Из свойств ЗЛП Вы знаете, что каждое ограничение, выраженное через координатные переменные, определяет на плоскости некоторую полуплоскость. Для нахождения полуплоскостей, в которых выполняется условие решения задачи, выбирается пробная точка. Для этого в любой полуплоскости ограничения необходимо взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить удовлетворяет ли пробная точка данному ограничению. Если удовлетворяет, то данное ограничение выполняется в соответствующей полуплоскости. В противном случае выбирается полуплоскость, не содержащая пробной точки. Полуплоскости, в которых не выполняются условия ограничений, показывают штриховкой. Так как система линейных ограничений совместна, то прямые, соответствующие ограничениям, пересекаясь, образуют замкнутую область (выпуклый многогранник), который является областью допустимых решений (см. рис. 1.). Рисунок 1. – Построение ОДР, представляющее выпуклый многогранник Кроме выпуклого многогранника ОДР может представлять собой неограниченную выпуклую область как сверху, так и снизу (см. рис. 2.), быть пустым множеством (см. рис. 3.), а также точкой (см. рис. 4.). Рисунок 2. – ОДР не ограниченная сверху Рисунок 3. – ОДР, представляющее пустое множество 4 Рисунок 4. – ОДР, представляющее точку Для построения ОДР ограничения лучше переписать в отрезках. Например: 3х1 + 2х2 ≤ 27 → х1 9 + х2 13.5 ≤1 (2) Как известно, числа, стоящие в знаменателе, показывают, сколько отсекает прямая, соответствующая данному ограничению на той или иной координатной оси. Например: Для выражения (1) на оси 0Х1 9 единиц, на оси 0Х2 13,5 единиц. 3. НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ Поскольку оптимальное значение целевой функции достигается на границе, то решение задачи линейного программирования фактически сводится к поиску вершины многогранника решений, в которой целевая функция имеет оптимальное (наибольшее в задачах на max или наименьшее в задачах на min) значение. Т.е. используя метод перебора можно найти оптимальное решение ЗЛП. Однако, при большой размерности задачи (при большом количестве ограничений и переменных) перебор вершин представляется слишком трудоёмким процессом. Поэтому задача состоит в том, чтобы избежать перебора вершин, а сделать нахождение оптимального решения целенаправленным. Уравнение целевой функции при фиксированном значении определяется на плоскости прямой линией. При у = 0, получаем целевую функцию нулевого уровня. При изменении значения целевой функции получим семейство параллельных прямых, называемых  линиями уровня. При целенаправленном решении оптимизационной задачи вначале строят линию уровня, приравнивая ЦФ к некоторому малому значению у = Z. Далее вычисляют координаты двух точек удовлетворяющие данному уравнению, и через эти две точки проводят пунктирной линией (или другим цветом) начальную прямую ЦФ, представляющую линию уровня у = Z. Для определения направления перемещения начальной прямой к оптимальной точки строят вектор-градиент , координаты которого являются частными производными преобразованной целевой функции:  f  f     k  с1 ,  с (3) 2 k  x  x 2  1  Чтобы построить данный вектор нужно соединить точку (c1, c2) с началом координат. Осуществляя параллельный сдвиг начальной прямой, перпендикулярной вектору-градиенту по направлению данного вектора до крайней угловой точки многогранника решений до тех пор, пока начальная прямая не покинет пределов многоугольной области (до касания с ОДР), в результате находят точку (см. рис. 5), в которой ЦФ принимает максимальное значение. 5 Осуществляя параллельный сдвиг начальной прямой в противоположном направлении вектора-градиента до крайней угловой точки многогранника решений, в результате находят точку, в которой ЦФ принимает минимальное значение. Определив координаты оптимальной точки, вычисляют значение ЦФ и оставшиеся неизвестные переменные (см. рис. 5.). В данном случае ЗЛП разрешима, и мы имеем единственное решение. Рисунок 5. – Нахождение оптимальной точки ЗЛП может иметь и бесконечное множество решений – альтернативный оптимум. В этом случае прямая, соответствующая целевой функции, параллельна грани многоугольника, соответствующая одному из активных ограничений ЗЛП (см. рис. 6.). Рисунок 6. – ЗЛП имеет множество решений Ограничения называются активными (связывающими), если прямая, его представляющая проходит через оптимальную точку, в противном случае соответствующие ограничения не являются связывающими. Если ОДР представляет собой неограниченную выпуклую область, то в зависимости от условий ЗЛП может и не иметь решения (см. рис. 7, 8) 6 Рисунок 7. – ЗЛП имеет единственное решение точку-минимум Рисунок 8. – ЗЛП не имеет решения Если ОДР представляет собой пустое множество, то ЗЛП не разрешима. Если ОДР представляет собой точку, то говорить об оптимальности не имеет смысла. Пример: 1. Постановка задачи Для перевозки изделий, состоящих из двух контейнеров А и В, у компании «Транзит» имеются три транспортных средства разных типов, возможности которых приведены в таблице № 1. Необходимо разработать план перевозок, обеспечивающий доставку максимального числа изделий в комплекте в течение 24 часов, при условии, что: - простои и обратные перевозки не допускаются; - перевозка двух различных контейнеров на одном транспортном средстве не допускается техническими условиями. Таблица № 1 – Исходные данные задачи Тип транспортных средств Производительность (ед./ч) Контейнер А Контейнер В 5 6 5 5 2 3 Т1 Т2 Т3 2. Уяснение экономико-математической постановки задачи Цель действий: Максимальная перевозка числа изделий в комплекте за сутки. Цель математического моделирования: Определение эффективного плана перевозок. Показатель эффективности определим из цели действия – ежедневное число перевезённых изделий в комплекте. 7 3. Разработка математической модели По условию задачи нам неизвестно время перевозки транспортными средствами соответствующего типа контейнеров А и В. Обозначим это время как неизвестные переменные модели: х1 – перевозка контейнера А транспортным средством первого типа; х2 - перевозка контейнера А транспортным средством второго типа; х3 - перевозка контейнера А транспортным средством третьего типа; х4 – перевозка контейнера В транспортным средством первого тип; х5 - перевозка контейнера В транспортное средство второго типа; х6 - перевозка контейнера В транспортным средством третьего тип. Доход, получаемый от перевозки изделий, является условной стоимостью. Обозначим его как с j. По условию задачи с1 = 5, с2 = 6, с3 = 5, с4 = 5, с5 = 2, с6 = 3. Тогда общий доход, получаемый от ежедневного числа перевезённых изделий можно представить в виде целевой функции: y  5 x1  6 x 2  5 х3 Условие комплектности изделий является ограничивающим фактором на их перевозку и предполагает, что за 24 часа транспортные средства перевезут равное число контейнеров А и В. Это условие можно записать следующим образом: 5 х1  6 х2  5 х3  5 х4  2 х5  3х6 Ещё одним ограничивающим фактором являются требования отсутствия простоев и обратных перевозок. Требование отсутствия простоев, т.е. непрерывного использования всех транспортных средств в течение суток, можно записать следующим образом: x1  х4  24 х2  х5  24 х3  х6  24 Требование отсутствия обратных перевозок можно представить в виде общих ограничений: х j  0 , при j  1,6 Так как ПЭ и ограничения линейны, то данную задачу можно решить методом линейного программирования. Таким образом, задача нахождения эффективного плана перевозок, обеспечивающего максимум перевозимых изделий в комплекте может быть сформулирована следующим образом: Найти неотрицательные значения неизвестных переменных х1, х2, х3, х4, х5, х6обращающих ЦФ в максимум: y  5 x1  6 x2  5 х3  max , при x j  X удовлетворяющих системе линейных ограничений: уравнений, задающих условия решения задачи x1  х4  24 x 2  х5  24 x3  х6  24 5 х1  6 х2  5 х3  5 х4  2 х5  3х6  0 ограничений на переменные х j  0 , при j  1,6 4. Производство расчётов графическим методом Ввиду того, что неизвестное число переменных не превосходит число линейных уравнений-ограничений системы на два (6 – 4 = 2), то данная простейшая ЗЛП может быть решена графическим способом. 4.1 Построение области допустимых решений 8 Т.к. ЗЛП уже представлена в смешанной форме, то сразу перейдём к определению координатных переменных. Неизвестные переменные х1и х2 линейно-независимы, т.к. определитель, составленный из коэффициентов при них, отличен от нуля 1 1  11  0  0  1  0 поэтому их можно использовать в качестве координатных переменных. Выразим все неизвестные переменные и целевую функцию через координатные переменные, условно обозначив ограничения: y  1.25 x1  x 2  150  max x3  1.25 х1  х2  30 х4  24  х1 х5  24  х2 х6  1.25 х1  х2  6 Из условия не отрицательности всех неизвестных находим следующие выражения, соответствующие линейным ограничениям: x3  1.25 х1  х2  30  0 х4  24  х1  0 х5  24  х2  0 х6  1.25 х1  х2  6  0 Эти выражения позволяют все ограничения выразить через координатные переменные, условно обозначив их как: х1  0 х2  0 1.25 х1  х2  30 (1) х1  24 (2) х2  24 (3) 1.25 х1  х2  6 (4) Приравняв левые и правые части неравенств и нанеся прямые на график, определим область допустимых решений (см. рис. 9.). Х2 32 28 1 2 24 3 20 4 16 12 О Д Р 8 4 4 8 12 16 20 24 Х1 Рисунок 9. – Определение ОДР Нахождение оптимального решения Для определения направления возрастания ЦФ построим вектор-градиент с координатами (-1.25,1). Далее построим начальную прямую и перемещая по направлению вектора-градиента определим оптимальную граничную экстремальную точку ОДР (см. рис. 10.). 4.2 9 Х2 1 32 28 2 24 3 20 4 16 12 О Д Р 8 4 4 8 12 16 20 24 Х1 У=0 Рисунок 10. – Нахождение оптимального решения Определив координаты оптимальной точки (0, 24), подставив их в уравнение ЦФ и в уравнения линейных ограничений, получим, что: у = 174, х3  6 , х4  24 , х5  0 , х6  18 5. Анализ полученных результатов Таким образом при заданных условиях для компании «Транзит» оптимальным решением перевозок числа изделий в комплекте будет являться: первое транспортное средство должно быть выделено на перевозку контейнеров «В» в течении 24 часов, второе транспортное средство должно быть выделено на перевозку контейнеров «А» в течении 24 часов и третье транспортное средство должно быть выделено на перевозку контейнеров «А» и «В» в течении 6 и 18 часов соответственно. При таком плане перевозок компания «Транзит» перевезёт максимальное количество изделий в комплекте 174 един. ЗАКЛЮЧЕНИЕ Таким образом, в процессе изучения лекции Вы практически ознакомились с применением графического метода для решения задачи линейного программирования. ЛИТЕРАТУРА Основная: 1. Экономико-математические методы и модели в управлении водным транспортом: Линейное программирование: Учебное пособие / под редакцией профессора В.А. Бабурина. СПБ.: СПГУВК, 2012. 206 с. 2. Кремер Н.Ш., Исследование операций в экономике: Учебное пособие. М.: Юрайт, 2010. 432с. 3. Есипов Б.А., Методы исследования операций: Учебник для Вузов. М.: Лань, 2010. 256с. б) Дополнительная: 4. Кремер Н.Ш, Путко Б.А., Фридман М.Н., Исследование операций в экономике: Учебное пособие. М.: ЮНИТИ, 2006. 5. Хэмди А. Таха, Введение в исследование операций. М.: ВИЛЬЯМС, 2001. 6. Бережная Е.В, Бережной В.И., Математические методы моделирования экономических систем: Учебное пособие. М.: Финансы и кредит, 2001. а) 10 7. Вентцель Е.С., Исследование операций: Учебное пособие. М.: Советское радио, 1972. Профессор кафедры математического моделирования и прикладной информатики, к.в.н., доцент 31 август 2020г. 11 А.А. БУРЫКИН