Целевая функция

Решим задачу аналитически:

1. От стандартной формы задания перейдем к каноническому виду, введя дополнительные переменные х₃ и х₄.

r (A) = 3, значит в системе три базисные переменные – (х₁, х₂, х₃), а х₄ – свободная.

1 шаг. Выразим х₁, х₂, х₃ и Z через х₄:

Итак,

Самое маленькое значение, которое может принимать х₄=0.

Значит, х₁=4, х₂=8, х₃=6, х₄=0.

Х₁=(4;8;6;0) – первое допустимое базисное решение. Z=52.

Это соответствует вершине В (4;8) многоугольника решений.

Т.к. переменная х₄ входит в Z со знаком «+», то ее увеличение увеличит и формулу Z, но увеличивать х₄ можно до тех пор, пока базисные переменные х₁, х₂, х₃ остаются положительными. Очевидно, что сохранение не отрицательности всех переменных возможно, если не нарушается ни одна из полученных во всех уравнениях границ:

→ х₄ ≤ 3

3 8 х

Значит х₄ следует вводить в базис, а х₃ – в свободные

2 шаг .(х₁, х₂, х₄) – базисные, х₃ – свободная

Выразим х₄ через х₃:

, т.е. получим систему:

Аналогично рассуждениям первого шага, анализируем формулу функции Z: т.к. х₃ входит в функцию Z со знаком «-», то увеличение х₃ приведет к уменьшению Z, значит х₃ необходимо оставить равным нулю, тогда:

- новое допустимое базисное решение

Но, т.к. х₃ увеличивать нельзя, то оно является оптимальным решением: Z_max=55.

2. Задача на минимум.

Дана система уравнений:

Среди допустимых решений найти то, которое обращает в min целевую функцию .

Замечания: При определении минимума линейной функции Z возможны два пути:

1) отыскание максимума функции F, полагая, что F = - Z и учитывая, что Z_min= - F_max;

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

Рассмотрим второй случай.

1 шаг.

r(A)=2 → базисных переменных две

х₁, х₂ – базисные

х₃, х₄ – свободные

Разрешим систему относительно х₁ и х₂.

Дата добавления: 2014-11-08