Поиск области допустимых решений (ОДР) задачи линейного программирования

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

Область допустимых решений в задаче линейного программирования задана системой неравенств. Построение ее геометрического аналога проводится в декартовой системе координат с двумя координатными осями и (на плоскости). Каждая точка на плоскости представляет собой план (программу) выпуска продукции обоих видов. Координаты этой точки определяют конкретные объемы выпуска 1-го и 2-го видов (см. рис. 8.2.1).

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

1) Находится множество точек, удовлетворяющих первому неравенству .

Строится график подобласти решений, удовлетворяющей равенству .

На графике 1 это прямая I.

Задается пробная точка, явно принадлежащая одной из полуплоскостей, расположенной по одну сторону от прямой. По этой точке определяются все точки полуплоскости, являющиеся решением первого неравенства (см. рис. 8.2.1).

Формального доказательства этого утверждения мы здесь не приводим. Однако для понимания ситуации призываем мобилизовать интуицию и воображение. Рекомендуем представить (можно нарисовать) серию прямых , задавая как больше 8-ми (например, 9, 10, 11), так и меньше (7, 6, 5). Этого рисунка будет достаточно, чтобы понять, что прямая является границей, разделяющей область (полуплоскость) допустимых решений для неравенства и недопустимых (где неравенство не выполняется). Здесь легко сделать обобщение на многомерный случай: задает границу (плоскость), разделяющую область (полупространство) допустимых решений для неравенства и недопустимых (где неравенство не выполняется). Аналогично можно представить ситуацию для неравенства в -мерном случае.

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

Рис. 8.2.1. Решение единственно (точка А)

2) На этом же графике находится область решений для второго неравенства: .

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

3) Для третьего неравенства графически определяется решение. Это все планы , которые лежат выше прямой III.

4) Условия неотрицательности переменных и задачи линейного программирования определяют 1 квадрант, точки которого удовлетворяют этим ограничениям

5) На рис. 8.2.1 выделим область, являющуюся пересечением всех выделенных полуплоскостей. Эта область называется областью допустимых решений (ОДР). Координаты точек области допустимых решений будут удовлетворять всем ограничениям задачи