Теория информации. Статистический подход (стр. 2 из 2)

Суть графического метода заключается в следующем. По направлению (против направления) вектора

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

Рисунок 1. Геометрическая интерпретация ограничений и ЦФ задачи.

Методика решения задач ЛП графическим методом

В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0; 0)], и проверить истинность полученного неравенства.

Если неравенство истинное,

то надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку

и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.

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

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

Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня

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

Построить вектор

, который начинается в точке (0; 0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора

, при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

Определить координаты точки max (min) ЦФ

и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

Задача. Правоохранительные органы разработали 10 программ по борьбе с преступлениями в сфере экономики, причем среди этих программ есть одинаковые: 5 одинаковы по одним свойствам, 3 программы по другим свойствам и 2 программы одинаковы по третьим свойствам. Сколькими способами эти программы могут быть переставлены?

Ответ.5*3*2 =30

Список используемой литературы

1. Аветисян Р.Д., Аветисян Д.В. Теоретические основы информатики. - М.: РГГУ, 1997.

2. Гришкин И.И. Понятие информации. Логико-методологический аспект. - М.: Наука, 1973.

3. Дмитриев В.И. Прикладная теория информации. - М., 1989.

4. Седов Е.А. Эволюция и информация. - М.: Наука, 1976.

5. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов.

6. Кононов В.А. - Исследование операций. Для продвинутых математиков.

7. Чернавский Д.С. Синергетика и информация. - М.: Знание, 1990.