Разное по педагогике » Методика преподавания курса "Матричные игры" » Графическое решение задачи линейного программирования

Графическое решение задачи линейного программирования

Страница 2

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

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

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

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

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

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

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

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

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

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

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

Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

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

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

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

Страницы: 1 2 3 4 5

Это интересно

Историческое развитие понятия милосердие
Само милосердие возникло задолго до того, как люди придумали синтетическое понятие. В Древнем Риме, в Афинах богатые горожане старались помочь людям, которые нуждались в пище, одежде. В обычае было устраивать общественные трапезы, раздавать согражданам деньги, одежду, пищу. По мнению Гусейнова, это ...

Эмпирическое исследование взаимосвязи уровня развития свойств внимания и характеристик тревожности
Настоящее исследование посвящено изучению взаимосвязи уровня развития свойств внимания и характеристик тревожности. Цель данного исследования заключается в выявлении зависимости между уровневыми характеристиками внимания и тревожностью. Предметом данного исследования являлась взаимосвязь уровневых ...

Экранное представление тестовых вопросов
Обратимся к способам представления тестовых вопросов на экране компьютера, а точнее, к экранным элементам тестовых вопросов и управлению ими. Сначала перечислим эти элементы: - поле вопроса; -поле иллюстрации; - поле ответа; -информационное поле; -поле пояснения правильного ответа; -скрытое поле ка ...

Графическое решение задачи линейного программирования

Навигация по сайту