ПРОГРАММИРОВАНИЯ

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

Пример 6. Определить наименьшее или наибольшее значение функции

(7)

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

(8)

Решение находят в следующей последовательности:

1) строят многоугольник решений, систему неравенств (8), который является пересечением полуплоскостей, которые описываются отдельно каждым неравенством этой системы;

2) находят оптимальную точку, которая по основным свойствам задачи линейного программирования расположена в вершине многоугольника решений неравенств (8). Для нахождения оптимальной точки используют вектор нормали , построенный по целевой функции. Он перпендикулярен к линии уровня, которая задается уравнением . Следует помнить, что линией уровня функции z=z(x₁, x₂) называют прямую z=z(x₁, x₂)=c=const. Если z=z(x₁, x₂) – линейная функция x₁, x₂, то линия уровня есть прямая и для разных значений постоянной c они параллельны. Если f(x₁, x₂)=0 – линия на плоскости, то вектор – перпендикулярен этой линии в каждой ее точке. При параллельном переносе линии уровня в направлении вектора нормали N значение целевой функции возрастает. Находим вершину многоугольника, в которой достигается наибольшее значение функции z. Для нахождения точки минимума линию уровня необходимо перемещать в направлении, противоположном N. Линии уровня, которые проходят через оптимальные вершины многоугольников решений, называют опорными (оптимальными). С помощью нормали N на одном рисунке можно одновременно найти точки min и max, т.е. решить одновременно две задачи;

3) вычислить оптимальные значения. Для этого находят координаты вершин min и max как общее решение уравнений соответствующих граничных прямых, которые пересекаются в оптимальных вершинах. Найденные координаты подставляют в формулу (7) и вычисляют z_max и z_{min .}

Пример 7. Найти наибольшее и наименьшее значения функции z=-3+2x₁+x₂ при ограничениях .

Решение.

1. Строим многоугольник решений, который состоит из пересечения четырех полуплоскостей решений. На рисунке проведены граничные прямые всех четырех полуплоскостей решений. Граничные прямые полуплоскостей решений проходят через точки:

I. x₁+x₂=7, A₁(0; 7), A₂(7; 0);

II. -2x₁+3x₂=-4, B₁(2; 0), B₂(0; -4/3);

III. x₂=1, - прямая, параллельная оси 0x₁;

IV. x₁=0, - ось координат 0x₂.

Чтобы определить, с какого бока от гра­ничной прямой лежит полуплоскость решений, достаточно взять любую точку вне прямой I и подставить ее ко­ординаты в неравенство. Если неравен­ство удовлетворяется, то полуплоскость решений расположена со стороны вы­бранной точки, если нет – то с противо­положной. За точку сравнения, целесо­образно, если это возможно, взять на­чало системы координат. Итак, решения первой и второй полуплоскости распо­ложены с той же стороны, что и начало координат, а решения третьей – с про­тивоположной. Многоугольник реше­ний на рисунке заштриховано.

2. Находим оптимальную точку. Строим вектор нормали, начало которого лежит в точке (0; 0), конец – в точке (2; 1). Перемещая линию уровня (-3+2x₁+x₂=0) в направлении N, находим, что z_min достигается в точке А, z_max – в точке В.

3. Вычислим оптимальные значения. Точка В – точка пересечения граничных прямых I и II:

Из рисунка видно, что x₁=5, x₂=2, B(5; 2);

Точка А есть точка пересечения граничных прямых III и IV: x₁=0, x₂=1, A(0; 1);

Ответ:

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

Пример 8. Вычислить наибольшее и наименьшее значения функции при ограничениях:

Решение.

1. Граничные прямые проходят через точки:

I. x₁+2x₂=4, A₁(0; 2), A₂(4; 0);

II. 2x₁+x₂=4, B₁(0; 4), B₂(2; 0);

III. – ось 0 x₁: x₁=0;

IV. – ось 0 x₂: x₂=0.

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

2. Многоугольник решений неограничен, вектор N показывает, что z_max не существует, а z_min достигается на отрезке AA₂.

3. z_min =4 (и оно достигается во всех точках отрезка A₂A).

Пример 9. Определить наибольшее и наименьшее значения функции при ограничениях

Решение.

Построим многоугольник решений этой задачи. Он показывает, что при перемещении линии уровня в направлении нормали N (-2, 1) и при перемещении линии уровня в направлении нормали – N. Таким образом, это пример задачи, в которой нет ни максимума, ни минимума.