Методы принятия упр. ...

3.1 Поиск области допустимых решений

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

Этапы поиска области допустимых решений следующие:

1. Записываются уравнения граничных прямых  по ограничениям задачи
   

2. Строятся графики граничных прямых на плоскости;

3. Выделяется область решения каждого из неравенств системы уравнений;

4. Строится многоугольник решений, который и представляет собой область допустимых решений (ОДР).
   

Проиллюстрируем этапы поиска ОДР на примере задачи об использовании ресурсов, рассмотренной в теме 2.

Задача об использовании ресурсов (задача планирования производства).

Этап 1 . Записываются  уравнения граничных прямых.

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

В рассматриваемом примере граничных прямых будет 6:

первая: х₁+3х₂=18                           четвертая: 3х₁=21

вторая: 2х₁+х₂=16                            пятая:  х₁=0

третья: х₂=5                                      шестая: х₂=0

Этап 2.  Строятся графики граничных прямых на плоскости

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

Этап 3.  Поиск области решения каждого линейного неравенства

Для нахождения области решения каждого неравенства используют метод контрольной точки. Если в качестве контрольной взять точку А(0;0) и подставить ее координаты в соответствующее неравенство, то, когда это неравенство выполняется, следует брать полуплоскость, включающую в себя точ­ку А; если неравенство не выполняется — противоположную полу­плоскость.

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

Этап 4.  Выделение области решений системы ограничений задачи

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

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

Область решения для второй задачи составления рациона (задача о диете, задача о смесях)

выглядит следующим образом: