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

Рассмотрим геометрическую интерпретацию задачи (1.9-1.11), для случая двух переменных.

В этом случае:

X= ; C= ; A= ; B=

Тогда КЗЛП (1.9-1.10) может быть записана в виде:

(1.12)

и F = c₁ x₁ + c₂ x₂ extr.

Для геометрической интерпретации, поскольку , берем правую верхнюю четверть плоской прямоугольной системы координат Х₂OХ₁, т.е. 1-й - квадрант.

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

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

F = c₁ x₁ + c₂ x₂ = A. (1.13)

Функция F линейна и представляет собой некоторую прямую с постоянными угловыми коэффициентами c₁ и c₂. При изменении прямая уровня (1.13) функции F будет перемещаться по плоскости параллельно самой себе в направлении возрастания значений F. При таком перемещении первая точка встречи прямой с ОДР соответствует min F, а точка выхода прямой уровня из ОДР - max F (рис. 1.4).

Рис. 1.4

Для получения прямой F= c₁ x₁ + c₂ x₂ = 0 построим градиент функции F grad N (∂F/∂x₁ ,∂F/∂x₂ ) с координатами (c₁ ,c₂), указывающий направление возрастания F, и через точку О проводим прямую, перпендикулярную этому вектору. Далее, построенную прямую F=0 перемещаем параллельно самой себе в направлении вектора N. На рис. 1.4 видно, что опорной по отношению к ОДР эта прямая становится в точке D. В этой точке F принимает max. Проецируя точку D, на оси ОХ₁ и ОХ₂ находим оптимальные значения Х₁* и Х₂* . Подставляя Х₁* и Х₂* в F находим max F, т.е. F*.

Возможны случаи, когда max F не существует (max F=+ ) рис. 1.6, либо когда оптимальное решение не единственно (min F или max F) и достигается не в одной точке, т.е. линии уровня проходят по стороне многоугольника (рис. 1.5).

Таким образом, возможны следующие варианты:

1. Целевая функция F принимает максимальное значение в любой точке отрезка АВ, т.е. оптимальное решение не единственно. В этом случае линии уровня проходят по стороне многоугольника (рис. 1.5).

2. Целевая функция не ограничена сверху множеством допустимых значений, т.е. F max =+ (рис. 1.6).

3. Целевая функция не существует, поскольку система ограничений задачи несовместна.

Рис. 1.5

Заметим, что отыскание min F для данной системы ограничений отличается от нахождения max F при тех же ограничениях лишь тем, что линия уровня c₁ x₁ + c₂ x₂ =F передвигается не в направлении (c₁ ,c₂), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при определении max F, имеют место и при нахождении min F. Графическое решение задачи ЛП включает следующие этапы:

1. Строят прямые, уравнения которых получают в результате замены системы неравенств на систему точных равенств.

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

3. Находят ОДР.

4. Строят вектор (c₁ ,c₂) с координатами (∂F/∂x₁ ,∂F/∂x₂ ).

5. Строят прямую c₁ x₁ + c₂ x₂ = 0, проходящую через точку О.

6. Перемещают прямую c₁ x₁ + c₂ x₂ = 0 в сторону, совпадающую с направлением вектора , в результате находят точку (точки), в которой (которых) целевая функция F принимает max, либо устанавливают неограниченность сверху функции на множестве планов.

7. Определяют координаты точки D (X₁*, X₂*) и вычисляют значение целевой функции F в этой точке. Для определения координат точки D можно решить систему уравнений тех прямых, на пересечении которых лежит точка D (Рис. 1.4.)

Пример. Определить оптимальное число скорых и пассажирских поездов, при котором число перевозимых пассажиров достигает максимума для двух случаев:

а) без ограничения пропускной способности направления;

б) с ограничением по пропускной способности направления.

Исходными данными для задачи являются: наличный (рабочий) парк вагонов, схема состава (количество вагонов разных типов, обязательно включаемых в состав скорого и пассажирского поездов) и вместимость вагонов разного типа.

Пусть наличный парк вагонов, схема составов и вместимость вагонов разного типа представлены в табл. 1.5 и 1.6.

Таблица 1.5

	Вагоны
	Багажные	Почтовые	Плацкартные	Купейные	Мягкие
Парк вагонов	14	10	120	70	28
Состав скорого поезда	1	---	10	7	4
Состав пассажир-ского поезда	1	1	8	5	2

Для составления математической модели перевозочного процесса введем обозначение: X₁ - число скорых поездов, Х₂ - число пассажирских поездов. Тогда, ограничивающие неравенства, вытекающие из табл. 1.5 будут иметь вид:

X ₁ + X₂ 14,ограничение по багажным вагонам

X

(1.14)

₂ 10, ,ограничение по почтовым вагонам

10 X₁ + 8 X₂ 120, ,ограничение по плацкартным вагонам

7X₁ + 5 X₂ 70, ,ограничение по купейным вагонам

4

(1.15)

X₁ + 2X₂ 28, ,ограничение по мягким вагонам

.

Таблица 1.6

	Вагоны
	Багажный	Почтовый	Плацкартный	Купейный	Мягкий
Число перевозимых пассажиров	---	---	56	36	24

Обозначим целевую функцию через F. Основные принципы определения целевой функции изложены в [1, 2]. В нашей задаче целевая функция определяет число перевозимых пассажиров и, учитывая данные табл. 1.6, получим

F=(56·10+36·7+24·4)X₁+ (56·8+36·5+24·2)X₂ =

= 908X₁ + 676X₂ max . (1.16)

Целевая функция составлена корректно, поскольку она отвечает принципам однозначности (стремится к max), соответствия, управляемости (целевая функция выражена через параметры управления Х₁, Х₂). Далее поступаем согласно алгоритму, изложенному выше. Строим ОДР в системе координат Х₂OХ₁, для этого построим граничные прямые:

X₁ + X₂ = 14,

X₂ = 10,

10 X₁ + 8 X₂ = 120,

7X₁ + 5 X₂ = 70,

4X₁ + 2X₂ = 28,

 X  0.

Эти прямые изображены на рис. 1.7. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой - нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют неравенству, то искомой является полуплоскость, которой принадлежит эта точка, в противном случае - другая полуплоскость. Найдем, например, полуплоскость, определяемую неравенством

X₁ + X₂ 14. Для этого, построив прямую Х₁ +Х₂ =14 (на рис. 1.7 это прямая I), возьмем какую-нибудь точку, принадлежащую одной из двух полученных полуплоскостей, например точку О(0,0). Координаты этой точки удовлетворяют неравенству 0+0<14; отсюда следует, что полуплоскость, которой принадлежит точка О(0,0), определяется неравенством X₁ + X₂ 14. Это и показано стрелками на рис. 1.7. Пересечение полученных полуплоскостей и определяет ОДР исходной задачи.

Как видно из рис. 1.7, ОДР - это многоугольник OАВС.

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

Рис. 1.7

Чтобы найти указанную точку, можно воспользоваться двумя способами:

1. Построим вектор ( 908, 676)=100(9,08; 6,76), указывающий направление возрастания F, и через начало координат проводим прямую, перпендикулярную нашему вектору.

2. Либо полагаем, что X₁ равняется какому-либо числу (например

X₁ = 10) и, подставив это значение в уравнение F: 908 X₁ + 676 X₂ =0 (9080+676X₂ =0), решаем его: X₂ = - 13,43; проводим прямую через начало координат и точку L (10, - 13,43), это и будет искомая прямая F.

Перемещая построенную прямую любым из перечисленных выше способов в направлении вектора , видим, что последней общей точкой ее с ОДР служит точка В. Координаты этой точки и определяют число

скорых и пассажирских поездов, которые перевезут максимальное число пассажиров.

Точка В лежит на пересечении прямых Х₂=10 (II) и 4Х₁+2Х₂=28 (V). Для определения ее координат решим систему уравнений:

Х₂=10,

4Х₁+2Х₂=28.

Получим Х₁*=2; X₂*=10; X₁*, X₂* - оптимальные решения.

Подставим значения Х₁* и Х₂* в функцию цели, получим F max=908·2+676·10=8576 пассажиров.

Из рис. 1.7 видно, что прямые 7Х₁+5Х₂=70 и 10Х₁+8Х₂=120 находятся вне ОДР и практически не вносят ограничений в задачу. С математической точки зрения эти условия являются лишними, а с точки зрения планирования - это резерв по этим типам вагонов, который может быть использован для других целей.

Следовательно, при назначении 2 скорых и 10 пассажирских поездов max число перевозимых пассажиров составит 8576.

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

Пример. Найти max F=2X₁+3X₂ при следующих ограничениях:

2 X₁ + X₂ 10,

- 2X₁ +3X₂ 6,

2X₁ + 4X₂ 8,

 X  0.

Строим граничные прямые:

2X₁ + X₂ = 10,

- 2X₁ + 3X₂ = 6,

2X₁ + 4 X₂ = 8.

Эти прямые изображены на рис. 1.8.

Для построения прямой F=2X₁+3X₂=0 можно воспользоваться любым из способов: либо строим радиус-вектор N(2,3), указывающий направление возрастания F, и через точку О проводим прямую, перпендикулярную ему, либо, положив X₁ = -3, найдем X₂, решив уравнение

- 6 + 3X₂ = 0. Отсюда следует, что X₂ = 2, строим F через точки O(0,0) и K(-3,2).

Построенную прямую F=0 перемещаем параллельно самой себе в направлении вектора N. Из рис. 1.8 видно, что опорной по отношению к

ОДР эта прямая становится в точке С, где F достигает max. В точке С пересекаются две прямые I и II, имеющие следующие уравнения:

2Х₁ + Х₂ = 10 и - 2Х₁ + 3Х₂ = 6.

Решая систему указанных уравнений, находим Х₁* =3; X₂* =4,

откуда F = 2•3+3•4 = 18. Следовательно, при плане

Х* =(Х₁*, Х₂*) = (3,4) значение целевой функции составит F max = 18.

Рис. 1.8