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

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

Математическая модель задачи о формировании штата отдела технического контроля имеет вид:

при ограничениях

, .

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

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

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

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

Определение 2.4. Лучшее в смысле заданной целевой функции допустимое решение задачи линейного программирования называется оптимальным. Значение целевой функции, соответствующее оптимальному решению называется оптимальным значением задачи линейного программирования.

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

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

(1) – все допустимые решения располагаются по одну сторону от прямой . Проще всего построить данную прямую по точкам ее пересечения с осями координат. Точка пересечения с осью определяетсяусловиями: (принадлежит оси ) и (принадлежит данной прямой). Из этих условий . Аналогично находим точку пересечения с осью : . Нужную полуплоскость найдем, подставив начало координат в левую часть рассматриваемого ограничения. Поскольку неравенство не выполняется (), то областью решений ограничения (1) является правая верхняя полуплоскость.

Ограничения

(2) и

(3)

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

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

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

Рассмотрим линии уровня, соответствующие различным значениям , и имеющие с допустимой областью хотя бы одну общую точку. Например, прямая, проходящая через точку B(8,10) будет соответствовать значению . Для построения данной прямой достаточно определить еще одну точку, например, точку пересечения этой прямой с осью . Это значит, что координаты второй точки находятся из условий: (пересечение с осью) и (точка принадлежит данной прямой). Из этих условий находим . При приближении к началу координат значения уменьшаются, поскольку, подставив начало координат получим значение .

Из рисунка видно, что все линии уровня функции , имеющие с допустимой областью - треугольником АВС - хотя бы одну общую точку, находятся между прямой, проходящей через точку В (максимальное значение ) и прямой, проходящей через точку А(8;5/3), которой соответствует минимальное значение . Следовательно, , – оптимальное решение и – оптимальное значение рассматриваемой задачи линейного программирования. Следовательно, при оптимальном режиме работы ОТК нужно использовать 8 контролеров I разряда и 1.(6) контролеров II разряда. Реализовать дробное значение можно, например, взяв одного из контролеров II разряда на неполный рабочий день.

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

Единственность оптимального решения. В данном примере точка ; является единственной допустимой точкой с минимальным значением , то есть, все остальные значения , соответствующие другим допустимым решениям больше 676. Следовательно, (8; 1.(6)) – единственное оптимальное решение.

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

Пример 2.1. Рассмотрим задачу ЛП:

при ограничениях:

(1)

(2)

(3)

, .

На рис.2.2 пунктирной линией проведены линии уровня - прямые, соответствующие значениям равным 2 и 6. Оптимальное значение функции равно 10. Причем, линия уровня совпадает с прямой , являющейся границей условия (1) и содержит отрезок BC, ограничивающий допустимую область ABCDE. То есть, все точки отрезка BC являются оптимальным решением.

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

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

В примере 2.1 имеются различные оптимальные решения, к которым относятся, в частности, и вершины допустимой области B и C. Вообще говоря, в силу выпуклости многогранника, который представляет собой допустимая область, и выпуклости линейной целевой функции, задачи ЛП обладают очень важным свойством.

Свойство задач ЛП. Если в задаче линейного программирования существует оптимальное решение, то оно достигается, по крайней мере, в одной из вершин допустимой области.

Симплекс-метод решения задачи линейного программирования основывается на этом фундаментальном свойстве. Допустимая область задачи линейного программирования обычно состоит из бесконечного числа точек, однако оптимальное решение всегда можно найти перебором конечного числа ее вершин.

Так, в примере 2.1. допустимая область имеет следующие вершины: A(1; 0), B (10; 0), C (2; 4), D (0; 4), E (0; 1). В этих точках целевая функция имеет следующие значения: , откуда, с учетом свойства задач ЛП, также видно, что B и C – оптимальные решения.

Задача линейного программирования в стандартной форме