Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 3 стр.

                                                     Линейное программирование


       в) найти пересечение полученных полуплоскостей и прямых.
       2. Решение задачи путем анализа допустимого множества и поведения
целевой функции на этом множестве.
       а) Пусть допустимое множество оказалось пустым. Делается вывод:
задача решений не имеет, поскольку нет ни одной допустимой точки.
       б) Пусть допустимое множество оказалось не пустым. Выбрать два
произвольных числа d1 и d2 , d1 >d2 . Нарисовать линии уровня целевой
функции, соответствующие выбранным константам, т.е. прямые вида
c1x 1 +c2 x 2 =d1 и c1x 1 +c2 x 2 =d2 (это параллельные прямые, все точки кото-
рых обеспечивают значения целевой функции, равные соответственно d1 и
d2 ). Зафиксировать направление увеличения значений целевой функции от
прямой с правой частью, равной d2 , к прямой с правой частью, равной d1 .
Передвигать прямую c1 x 1 +c2 x 2 =d параллельно самой себе по допустимо-
му множеству в обозначенном направлении (в противоположном направле-
нии) до получения максимального значения d * (минимального значения
d * ), при котором прямая c1x 1 +c2 x 2 =d пересекает допустимое множество.
Зафиксировать на графике точки допустимого множества, обеспечивающие
максимальное (минимальное) значение целевой функции или убедиться, что
таких точек нет. Если допустимое множество ограничено (является много-
угольником), то возможны два различных ответа: решение единственно или
решений бесчисленное множество. При единственном решении на графике
зафиксирована единственная точка (вершина многоугольника), являющаяся
пересечением некоторых прямых. Необходимо выписать соответствующие
уравнения прямых и, решив систему полученных уравнений, найти точку -
решение задачи. В случае бесчисленного множества решений получен отре-
зок прямой, все точки которого обеспечивают максимальное значение целе-
вой функции. Среди этих точек есть вершины многоугольника. Координаты
вершин отыскиваются так, как указано в предыдущем случае. Если допус-
тимое множество не ограничено, то возможны те же две ситуации, что и в
случае ограниченного множества, и, кроме того, возможен случай отсутст-
вия решений из-за неограниченности значений целевой функции на допусти-
мом множестве.
       Из анализа графического метода решения можно сделать выводы, ко-
                                                     n
торые являются справедливыми и для задач из R .
       1. Допустимое множество задачи линейного программирования, если
оно не пусто, является многогранным ограниченным или неограниченным
выпуклым множеством.
       2. Если в задаче есть решение (оптимальная точка), то среди вершин
допустимого множества также есть решение. Часть оптимальных точек
можно искать, перебирая только вершины допустимого множества.
       Проиллюстрируем рассмотренный графический метод на примерах.

                                     5