Теория информации. Статистический подход
Методика решения задач ЛП графическим методом
В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0; 0)], и проверить истинность полученного неравенства.
Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
Построить вектор , который начинается в точке (0; 0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .
Задача. Правоохранительные органы разработали 10 программ по борьбе с преступлениями в сфере экономики, причем среди этих программ есть одинаковые: 5 одинаковы по одним свойствам, 3 программы по другим свойствам и 2 программы одинаковы по третьим свойствам. Сколькими способами эти программы могут быть переставлены?
Ответ.5*3*2 =30