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

 

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

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

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

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

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

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

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

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

Шаг 4. Если область допустимых решений – не пустое множество, то построить целевую прямую, т.е. любую из линий уровня , где F – произвольное число.

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

Шаг 6. При поиске максимума целевой функции необходимо передвигать целевую прямую в направлении вектора , при поиске минимума целевой функции – против направления вектора . Последняя по ходу движения вершина области допустимых решений будет точкой max или min целевой функции. Если такой точки (точек) не существует, то целевая функция не ограничена на множестве планов сверху (при поиске max) или снизу (при поиске min).

Шаг 7. Определить координаты точки max (min) целевой функции и вычислить значение самой целевой функции F(X^*). Для вычисления координат оптимальной точки X^* необходимо решить систему уравнений прямых, на пересечении которых находится X^*.

 

Пример решения задачи ЛП с двумя переменными

Графическим методом

Пример №2.1.

Найти оптимальное решение примера №1.2 о производстве мыла, математическая модель которой имеет вид

Решение.

Для построения прямых ограничений необходимо вычислить координаты точек пересечения этих прямых с осями координат (рис.2.2).

(1) – (2) –

(3) –

Прямая (4) проходит через точку x₂ =2 параллельно оси x₁.

Рис. 2.2. Графическое решение

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

Целевую прямую можно построить по уравнению

,

Вектор строится из точки (0; 0) и направляется в точку (3; 2). Точка Е – это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому Е – это точка максимума целевой функции. Координаты точки Е определяются из системы уравнений прямых ограничений (1) и (2)

, ,

Е( ) [т/сутки].

Максимальное значение целевой функции равно

[тыс. руб./сутки].

Ответ.

Наилучшим режимом работы фабрики является ежесуточное производство хозяйственного мыла в объеме т и туалетного мыла в объеме т.

Доход от продажи мыла составит тыс. руб. в сутки.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача ЛП сформулирована как задача минимизации или максимизации линейной формы, переменные которой связаны некоторой системой линейных уравнений и должны быть неотрицательными.

Для решения такой задачи применяется симплексный метод линейного программирования.

Для того чтобы решать задачу ЛП симплексным методом необходимо уметь преобразовывать задачу к каноническому виду.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Алгоритм процесса кибернетического моделирования.
3. II. Предполагаемые союзники и их задачи
4. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
5. Алгоритм 1.1. Расчет описательных статистик
6. Алгоритм 2.1. Расчет внутригрупповых дисперсий результативного признака
7. Алгоритм 3. Снятие заливки области построения
8. Алгоритм Data Encryption Stantart (DES).
9. Алгоритм «сдвиг-свертка» для грамматики операторного предшествования
10. АЛГОРИТМ АВАРИЙНОЙ И ЭКСТРЕННОЙ ОСТАНОВКИ 1 И 2 СТУПЕНИ КОМПРИМИРОВАНИЯ ДКС, БПТПиИГ
11. Алгоритм анализа переключательной схемы
12. Алгоритм банкира для несколько видов ресурсов