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

Рассмотрим задачу линейного программирования, заданную в стандартной форме. Найти

(10.19)

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

(10.20)

(10.21)

Рассмотрим случай n =2 (n = 3). Напомним, что неравенству соответствует полуплоскость с граничной прямой , координаты каждой точки которой удовлетворяют этому неравенству.

Пусть дана система m ограничений с двумя переменными, т. е.

(10.22)

(10.23)

Если множество значений , удовлетворяющих условиям (10.22) и (10.23), ограничено, то оно представляет собой выпуклый многоугольник (при n = 3 – выпуклый многогранник). Линейная форма достигает экстремума в вершине многоугольника. Если максимум (или минимум) достигается одновременно в двух вершинах, то он достигается на всей стороне многоугольника, соединяющей эти вершины, причем стороны многоугольника – это отрезки прямых, уравнения которых могут быть получены, если в (10.22) и (10.23) заменить неравенства на уравнения. Область изменения линейной формы представляет собой многоугольник, изображенный на рис. 10.3.

Рисунок 10.3

Прямые, образующие многоугольник ОАВСЕF на плоскости соответствуют условиям (10.22) и (10.23), в которых неравенства заменены уравнениями. Штриховка указывает на ту сторону прямой, по которую располагаются точки плоскости, удовлетворяющие неравенствам (10.22) и (10.23). Направление прямой определяется вектором ; это вектор перпендикулярен . Коэффициенты и указывает также направление, в котором увеличивается линейная форма

( ).

Задача линейного программирования – вычисление координат точки, дающей экстремум линейной форме

(10.19’)

при условиях (10.22) и (10.23), может быть (при n = 2), геометрически истолкована следующим образом.

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

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

1. Графически могут решаться:

– задачи, заданные в стандартной форме, содержащие не более двух переменных;

– задачи, заданные в канонической форме с числом свободных переменных (r – ранг матрицы системы ограничений);

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

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

3. Решение задачи первого типа выполняется в два этапа: построение области допустимых решений и нахождение в этой области оптимального решения.

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

I – пустая область;

II – выпуклый многоугольник;

III – неограниченная выпуклая многоугольная область.

В случае I задача не имеет решения; в случае II задача всегда имеет оптимальное решение; в случае III, в зависимости от направления вектора (коэффициентов линейной формы F), задача может иметь или не иметь решения. Последнее связано с неограниченным возрастанием () или убыванием () функции в области допустимых решений.

5. Задача может иметь единственное оптимальное решение, совпадающее с одной из вершин области, и бесчисленное множество решений (альтернативный оптимум).

6. В случае альтернативного оптимума и ограниченной области оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины области (рис. 10.4). В случае неограниченной области может оказаться, что среди множества оптимальных решений только одно совпадает с вершиной области (т. на рис. 10.5). Тогда на «оптимальной» граничной прямой находят еще одно оптимальное решение и общее оптимальное решение , .

, ,

. .

Рисунок 10.4 Рисунок 10.5

Дата добавления: 2015-04-29