Прикладная математика. Лекция 1. Геометрический метод решения задачи линейного программирования

Вентцель Е.С. Исследование операций: задачи, принципы, методология / Е.С. Вентцель. – М.: 1972 г. – 552 с.
Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ, 2003. – 407 с.
Таха, Хэмди А. Введение в исследование операций, 6-е издание.: Пер. с англ. – М.: Издательский дом "Вильямс", 2001.
Лубенец Ю.В. Экономико-математические методы и модели. Учебное пособие – Липецк: Изд-во ЛГТУ, 2013.
Рекомендуемая литература

Линейное программирование
Каждый человек ежедневно, не всегда осознавая это решает проблему: как получить наибольший эффект, обладая ограниченными средствами.
Наши средства и ресурсы всегда ограничены. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий.
Раньше план в таких случаях составлялся «на глазок». В середине же XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах (линейное программирование, динамическое программирование и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование».

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.
Линейное программирование – это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.
Линейное программирование

Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений.
Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений.
Линейное программирование представляет собой наиболее часто используемый метод оптимизации.
Линейное программирование

К числу задач линейного программирования можно отнести задачи:
рационального использования сырья и материалов;
задачи оптимального раскроя;
оптимизации производственной программы предприятий;
оптимального размещения и концентрации производства;
составления оптимального плана перевозок, работы транспорта (транспортные задачи);
управления производственными запасами;
и многие другие, принадлежащие сфере оптимального планирования.
Линейное программирование

Постановка задачи линейного программирования
Линейной функцией n переменных x1 ,x2 ,…, xn называется функция вида
Задача линейного программирования может быть поставлена в виде:
где – система ограничений,
– условия неотрицательности.
Здесь функция L называется целевой функцией.

Постановка задачи линейного программирования
Другие постановки задачи линейного программирования могут быть сведены к данной:
1) если , то можно рассмотреть . Те значения переменных, при которых – L максимальна, дают значения , при которых L минимальна. При этом
2) если имеются ограничения вида то можно умножить его на −1 и рассмотреть ограничение
3) если имеется ограничение вида то возмож-ны 2 способа перехода к неравенствам. Первый способ – заменить равенство на 2 неравенства:
и
Второй способ – выразить переменную для которой че-рез остальные переменные и подставить в целевую функцию и ограничения.

Геометрический метод решения задачи линейного программирования
Графическое решение задачи линейного программирования с двумя переменными и системой ограничений в виде линейных неравенств состоит из двух этапов:
1) построение на плоскости множества решений системы линейных неравенств, являющегося выпуклым многогранным множеством,
2) выбор в построенном множестве точки, доставляющей целевой функции требуемое (минимальное или максимальное) значение.
Рассмотрим следующую задачу линейного программирования:

Геометрический метод решения задачи линейного программирования
На плоскости строим прямые для
Далее определяем полуплоскости, удовлетворяющие неравенствам . Для этого берем точку, не лежащую на прямой и подставляем ее координаты в неравенство. Если неравенство верно, то берется полуплоскость, в которой лежит эта точка. Если неравенство не верно, то берется другая полуплоскость. Затем берем пересечение всех полуплоскостей, лежащее в первой координатной четверти. Полученное множество является областью допустимых решений (ОДР).
Область допустимых решений (ОДР) - множество всех наборов значений переменных, удовлетворяющее всем ограничениям и условиям неотрицательности.

Геометрический метод решения задачи линейного программирования
Далее строим вектор нормали . После этого через начало вектора проводим перпендикулярную к нему прямую, которая называется линией уровня.
Затем перемещаем линию уровня в направлении, которое указывает вектор нормали, до последних точек пересечения с ОДР.

Геометрический метод решения задачи линейного программирования
Рассмотрим пример решения задачи линейного программирования геометрическим способом.
Задача о ресурсах. Предприятие выпускает два вида продукции A1 и A2, для которых используется три вида ресурсов B1, B2 и B3.
Для выпуска единицы продукции A1 требуется 1 единица ресурса B1, 1 ед. рес. B2 и 3 ед. рес. B3, а для выпуска 1 ед. прод. A2 − 4 ед. рес. B1, 1 ед. рес. B2 и 1 ед. рес. B3 . Запасы ресурсов составляют: 24 ед. рес. B1, 9 ед. рес. B2, 21 ед. рес. B3. Производство единицы продукции A1 дает прибыль 1 ед., а ед. A2 − 2 единицы. Требуется найти план производства, дающий максимальную прибыль.

Геометрический метод решения задачи линейного программирования
Обозначим x1 – количество выпускаемой продукции A1, x2 – количество выпускаемой продукции A2.
Тогда математическая формализация задачи приводит к модели:

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

Геометрический метод решения задачи линейного программирования
ОДР – пятиугольник OABCD. Координаты вектора нормали соответствуют коэффициентам перед переменными в целевой функции
Перемещая линию уровня, получаем решение в точке B.
Для нахождения координат точки B используем тот факт, что она является точкой пересечения прямых и
Решаем систему уравнений:
Решение системы дает координаты точки B(4,5).
Ответ:

Геометрический метод решения задачи линейного программирования
Замечание. Если в условиях рассмотренной задачи
то Получаем решение на отрезке BC. Находим координаты точки С:
Ответ:

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

Геометрический метод решения задачи линейного программирования
Рассмотрим различные случаи при решении задач линейного программирования геометрическим способом.
1. ОДР ограничена, решение единственно

Геометрический метод решения задачи линейного программирования
2. ОДР ограничена, решений бесконечно много

Геометрический метод решения задачи линейного программирования
3. ОДР неограничена, решение единственно

Геометрический метод решения задачи линейного программирования
4. ОДР неограничена, решений бесконечно много

Геометрический метод решения задачи линейного программирования
5. ОДР неограничена, решений нет

Геометрический метод решения задачи линейного программирования
6. ОДР пуста, решений нет

Задания для самоконтроля
1. Какие из следующих функция являются линейными?
1)
2)
3)
4)

Задания для самоконтроля
2. Область допустимых решений – это
1) множество всех наборов значений переменных целевой функции,
2) множество всех наборов значений переменных, удовлетворяющее всем ограничениям,
3) множество всех наборов значений переменных, удовлетворяющее всем условиям неотрицательности,
4) множество всех наборов значений переменных, удовлетворяющее всем ограничениям и условиям неотрицательности.

Задания для самоконтроля
3. Найдите значение целевой функции в задаче линейного программирования.
1) 763,
2) 835,
3) 801,
4) 726.