Общая постановка задачи линейного программирования

Алгоритм оптимизации целевой функции задачи линейного программирования графическим способом

Мы рассмотрим реализацию графического метода решения задачи линейного программирования для случая максимизиции целевой функции.

Мы используем модель, построенную для компании "Краски", чтобы показать метод графического решения задачи ЛП.

Этап 1. Построение пространства допустимых решений.

Сначала проведем оси: на горизонтальной будут указываться  значения переменной , а на вертикальной — .

Далее рассмотрим условие  неотрицательности переменных: и .

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

Чтобы учесть оставшиеся ограничения заменим неравенства  на равенства, в результате чего получим  уравнения прямых, а затем на плоскости  проведем эти прямые.

Теперь рассмотрим, как  графически интерпретируются неравенства.

Каждое неравенство  делит плоскость ( , ) на два полупространства, которые располагаются по обе стороны прямой, которая соответствует данному неравенству.

Точки плоскости, расположенные  по одну сторону прямой, удовлетворяют  неравенству (допустимое полупространство), а точки, лежащие по другую сторону, — нет.

"Тестовой" точкой, проверяющей,  точки какого полупространства  удовлетворяют неравенству, а какого — нет, может служить точка (0, 0).

Например, эта точка удовлетворяет первому неравенству (здесь ).

Это означает, что точки  полупространства, содержащего начальную  точку (0,0), удовлетворяют этому неравенству.

На рисунке допустимые полупространства показаны стрелочками.

В том случае, когда  точка (0,0) не удовлетворяет неравенству, допустимым полупространством будет то, которое не содержит эту точку.

Если же прямая проходит через эту точку, следует в  качестве "тестовой" взять какую-либо другую точку.

Этап 2. Нахождение оптимального решения.

Точки пространства допустимых решений, показанного на рисунке, удовлетворяют одновременно всем ограничениям.

Это пространство ограничено отрезками прямых, которые соединяются  в угловых точках , , , , и .

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

Поскольку пространство допустимых решений содержит бесконечное число  точек, необходима некая процедура  поиска оптимального решения.

Нахождение оптимального решения требует определения  направления возрастания целевой функции .

Мы можем приравнять к нескольким возрастающим значениям, например 10 и 15.

Эти значения, подставленные  вместо в выражение целевой функции, порождают уравнения прямых; для значений 10 и 15 получаем уравнения прямых и .

На рисунке эти прямые показаны штриховыми линиями, а направление возрастания целевой функции — толстой стрелкой.

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

На рисунке видно, что оптимальное решение соответствует точке .

Эта точка является местом пересечения прямых (1) и (2), поэтому  ее координаты и находятся как решение системы уравнений, задающих эти прямые:

, .

Решением этой системы  будет  и , при этом значение целевой функции равно .

Полученное решение  означает, что для компании "Краски" оптимальным выбором будет ежедневное производство 3 т краски для наружных работ и 1.5 т — для внутренних работ с ежедневным доходом в 21000.

Не случайно, что оптимальное  решение расположено в угловой  точке пространства допустимых решений, где пересекаются две прямые.

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

Мы рассмотрим применение метода графического решения задач  линейного программирования для случая минимизации целевой функции.

Задача "диеты".

Фармацевтическая фирма  ежедневно производит не менее 800 кг некой пищевой добавки, которая состоит из смеси кукурузной и соевой муки, состав которой представлен в следующей таблице.

Диетологи требуют, чтобы  в пищевой добавке было не менее  белка и не более клетчатки.

Фирма хочет определить рецептуру смеси наименьшей стоимости  с учетом требований диетологов.

Поскольку пищевая добавка  состоит только из кукурузной и соевой муки, переменными для этой задачи, очевидно, будут — количество (в кг) кукурузной муки, используемой в дневном производстве пищевой добавки; — количество (в кг) соевой муки, используемой в дневном производстве пищевой добавки.

Целевая функция равна  обшей стоимости пищевой добавки, производимой за один день, и должна быть минимальной. В данном случае это  можно записать следующим образом:

Минимизировать .

Ограничения модели должны отражать производственные требования и рекомендации диетологов.

Фирма должна выпускать  не менее 800 кг смеси в день.

Соответствующее ограничение будет записано следующим образом: .

Рассмотрим ограничение, связанное с количеством белка  в пищевой добавке.

Общее количество белка  в смеси, состоящей из кг кукурузной муки и кг соевой муки, равно (кг).

 Это количество должно  составлять не менее  от общего объема смеси .

Отсюда получаем следующее  неравенство .

Аналогично строится ограничение  для клетчатки: .

В последних двух неравенствах переменные и надо перенести из правых частей неравенств в левые.

Окончательно модель примет следующий вид:

Минимизировать  при ограничениях

,

,

,

.

На рисунке показано графическое решение этой задачи.

Поскольку в данной модели следует минимизировать целевую  функцию, поэтому нужно идти в направлении уменьшения ее значений (это направление на рисунке показано стрелкой).

Оптимальное решение находится  на пересечении прямых и , откуда получаем (кг) и (кг).

При этих значениях переменных минимальная стоимость производимой ежедневно пищевой добавки составляет руб.

Виды областей решений с геометрической

точки зрения