Лабораторная работа №1. Графический (геометрический) способ определения оптимального плана

Графический (геометрический) способ определения оптимального плана

Если функция Z(X) содержит только две неизвестных Х₁ и Х₂, то линейные неравенства ограничений (2) будут представлять выпуклый многоугольник, в пределах которого находятся все возможные планы, удовлетворяющие основной задаче. Так как функция доходности является линейной, то она не имеет экстремумов внутри многоугольника, а наибольшее и наименьшее значения принимает на его границах, в частности – его вершинах. Очень редко задача допускает множество решений, лежащих в произвольных точках одной из сторон (вырожденный план).

В общем случае, когда вершин многоугольника решений большое количество, для нахождения нужной вершины находим вектор градиента grad Z(X)= с₁ + с₂ (направление наибольшего роста). Линия, перпендикулярная градиенту, представляет изолинию Z(X) = Const. Двигая прямую изолинию от т.(0,0) (очевидно, что при этом Z(X) = 0) в направлении градиента, отмечаем первую вершину многоугольника решений (минимум) и последнюю (максимум). Таким образом, решение задачи МЛП графическим способом включает следующие этапы:

1) на плоскости строят систему координат Х₁0Х₂ и проводят прямые, уравнения которых получают в результате замены в ограничениях (2) знаков неравенств на знаки точных равенств,

2) находят полуплоскости, определяемые каждым из ограничений, и строят выпуклый многоугольник решений,

3) строят вектор градиента целевой функции grad Z(X) = с₁ + с₂ ,

4) строят начальную прямую целевой функции с₁ Х₁ + с₂ Х₂ = 0, и затем параллельно передвигают ее в направлении градиента grad Z(X). В результате находят вершины многоугольника, где целевая функция Z(X) принимает наименьшее и наибольшее значения. Определяют координаты этих точек,

5) по координатам выделенных вершин многоугольника решений определяют оптимальные значения целевой функции Z(X).

Пример№1.

Цех по производству комбикорма и травяной муки, которые поступают в продажу по цене 2 тыс. руб. и 3 тыс. руб. за тонну, использует два вида сырья сенаж и зерно, суточный запас которых составляет 3т и 4т соответственно. Расход сырья на производство 1т готовой продукции приведен в Таблице:

Коммерческий отдел, анализируя рынок сбыта, установил, что спрос на травяную муку не превышает 2т в сутки, при этом он не может превосходить спрос на комбикорм более, чем на 1,5т. Какое количество продукции ежедневно должен производить цех, чтобы его доходы от реализации были максимальны, если минимальный выпуск комбикорма и муки ежедневно не ниже, чем 0,25т и 0,5т соответственно.

Целевая функция (доход от продажи продукции) Z(X) = 2 Х₁ + 3 Х₂, где Х₁ –количество выпускаемого комбикорма, Х₂ –количество травяной муки. Ограничение запасов сырья, и особенности спроса запишем в виде неравенств (2):

0,5 X₁ + 1 X₂ ≤ 3_,

1 X₁ + 0,5 X₂ ≤ 4_,

X₂ - X₁ ≤ 1,5_,

Х₂ ≤ 2_,

X₁≥0,25, X₂≥0,5

Построим на плоскости Х₁0Х₂ многоугольник решений, для этого в неравенствах системы ограничений знаки неравенств заменим знаками точных равенств:

0,5 X₁ + 1 X₂ = 3 (1),

1 X₁ + 0,5 X₂ = 4 (2),

1 X₂ - 1 X₁ = 1,5 (3)_,

X₂ =2 (4)_,

X₁= 0,25(5), X₂= 0,5(6).

Построив полученные граничные прямые (1)-(6), найдем соответствующие полуплоскости допустимых значений переменных и их пересечения. Полученное пространство решений есть многоугольник с вершинами ABCDEF (рис.1).

Рис.1. Построение области допустимых решений.

Для нахождения минимума и максимума целевой функции строим начальную прямую 2Х₁ +3Х₂ =0 и вектор grad Z(X) =2 +3 . Затем (рис.2) построим ряд прямых, параллельных начальной 2 Х₁ + 3 Х₂ =0 в направлении градиента (возрастания целевой функции).

Рис.2.Определение минимального и максимального значений целевой функции.

Первая вершина многоугольника т. А (0,25, 0,5) соответствует минимальному значению Z(X)=2*0,25+3*0,5=2. Максимальное значение Z(X) получается в т. Е на пересечении прямых 0,5 X₁ + 1X₂ = 3 и 1X₁ + 0,5 X₂ =4_, имеющей координаты (10/3, 4/3), и равна примерно 10,67 (10 2/3).

Таким образом, суточный объем производства комбикорма должен быть равен10/3 т, а травяной муки – 4/3т. Доход от продажи в этом случае будет максимальным – 10,67 (10 2/3) тыс.руб.

Графический способ позволяет решать лишь простейшие задачи. При увеличении переменных в целевой функции до 3-х множеством планов становится многогранник в трехмерном пространстве (Х₁Х₂Х₃), для нахождения которого потребуется построение плоскостей а ₁₁ X₁ +а₁₂ X₂ + а₁₃ X₃ = b₁, что делает задачу трудной для практического решения.

Варианты заданий лабораторной работы №1.

Графическим методом определить наименьшее и наибольшее значение целевой функции Z(X):

1.1. 2X₁ + 5X₂ -10 ≤ 0; 1.2. X₁ + 3X₂ ≥ 9;

2X₁ + X₂ – 6 ≤ 0; -2X₁ + X₂ ≤ 5;

X₁ + 2X₂ – 2 0; 2X₁ – 3X₂ ≤ 0;

X₁ ≥ 0, X₂ ≥ 0 0 ≤ X₁ ≤ 5, X₂ ≥ 0

Для Z(X) = 3X₁ – X₂ +6. Для Z(X) = -5X₁ + 9X₂.

1.3. X₁ + X₂ -4 ≤ 0 1.4. X₁ + X₂ ≥ 4

6X₁ + 2X₂ – 8 ≥ 0 8X₁ - 4X₂ +16 ≥ 0

X₁ + 5X₂ – 4 ≥ 0 0 ≤ X₂ ≤ 9

0≤ X₁ ≤ 3, 0≤ X₂ ≤ 3 2 ≤ X₁ ≤ 8

Для Z(X) = 2X₁ + 3X₂. Для Z(X) = 2X₁ + X₂ +4.

1.5. 9X₁ + 7X₂ -79 ≤ 0 1.6. 2X₁ - X₂ ≥ 3

2X₁ - 5X₂ – 11 ≤ 0 X₁ - X₂ ≤ 3

2X₁ + X₂ – 4 ≥ 0 X₁ – 3X₂ ≤ 1

X₁ ≥ 0, X₂ ≥ 0 X₁ ≥ 0, X₂ ≥ 0

Для Z(X) = -X₁ + 2X₂ . Для Z(X) = X₁ - 3X₂.

1.7. 6X₁ + X₂ ≤ 42 1.8. 7X₁ + 5X₂ ≥ 32

2X₁ - 3X₂ – 6 ≤ 0 2X₁ + 7X₂ ≥ 14

X₁ + X₂ ≥ 4 -X₁ + 6X₂ ≥ 0

X₁ ≥ 0, X₂ ≥ 0 0 ≤ X₁ ≤ 8, 0 ≤ X₂ ≤ 5

Для Z(X) = X₁ + 3X₂ . Для Z(X) = 2X₁ - 4X₂.

1.9. 0 ≤ X₁ + X₂ ≤ 3 1.10. -1 ≤ -X₁ + X₂ ≤ 1

-1 ≤ X₁ - X₂ X₁ + X₂ +1 ≥ 0

0≤ X₁ ≤ 1, 0≤ X₂ ≤ 2 -X₁ + 2X₂≤ 2

2X₁ - X₂≤ 2,

X₁ ≥ 0, X₂ ≥ 0

Для Z(X) = X₁ + X₂. Для Z(X) = X₁ + X₂.

1.11. 2X₁ + 3X₂ ≤ 24 1.12. 5X₁ + 4X₂ ≤ 20

-8X₁ + 3X₂ ≤ 24 X₁ - X₂ ≥ 0

2X₁ - 3X₂ ≤12, X₂ ≤ 2,

4X₁ + 3X₂ ≥ -12 3X₁ + X₂ ≥3

Для Z(X) = -X₁ + 4X₂ . Для Z(X) = 3X₁ + 5X₂.

Поиск по сайту: