Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Выражение целевой функции через свободные переменныеОценки свободных переменных.
Рассмотрим каноническую ЗЛП, для которой система ограничений приведена к стандартному виду. F (Х) = → max (min), ≥ 0, j = 1, 2, …, n. Выразим базисные переменные через свободные и подставим выражения (3) в целевую функцию. F (Х) = = () + + () + … + () + = - + + … + + + + … + = = . Таким образом, получим F (Х) = , (7) где + + … + ; ; ………….. . Числа называют оценками свободных переменных хm+ 1, х m+ 2, …, хn. Кратко выражение для оценки можно записать так: = , (8) где = (, , …, ) - вектор коэффициентов целевой функции при базисных переменных. В общем случае первая компонента этого вектора равна коэффициенту целевой функции при базисной переменной 1-го уравнения, 2-я компонента вектора - коэффициент целевой функции при базисной переменной 2-го уравнения, и т.д., последняя, m -я компонента вектора - коэффициент целевой функции при базисной переменной m -го уравнения. Вектор = - это вектор коэффициентов при переменной хj в системе (5.9). Число - это скалярное произведение векторов и : ∙ , (9) где координаты вектора = (, , …, ) – правые части системы (2). Число - это коэффициент при свободной переменной хj в целевой функции. Заметим, что выражение (7) можно представить в виде = F + (10) и рассматривать как ещё одно линейное уравнение, добавленное к системе (2). Оно ничем не отличается от остальных уравнений (2); его базисной переменной всегда является переменная F. Новые значения оценок свободных переменных и число можно пересчитывать по формулам: , (11) где - коэффициент при переменной хj в l -м уравнении, который умножается на число (- dis) для исключения из i -го уравнения переменной хs; j = 0, 1, 2, …, n.
Пример 4. Дана ЗЛП: F (Х) = → max, ≥ 0, i = 1, 2, 3, 4. Выразить целевую функцию через свободные переменные х 2, х 4. Решение. Воспользуемся формулой (5.14) для записи целевой функции через свободные переменные х 2, х 4: F (Х) = . Расчёты оценок и представим в табл. 12. Такие таблицы называются симплексными (симплекс-таблицы).
Таблица 2
В первой строке табл. 2 над неизвестными х 1, х 2, х 3, х 4 записаны соответствующие коэффициенты целевой функции. Во 2-м столбце записаны коэффициенты целевой функции при базисных переменных х 1, х 3. Число + = 2∙1 + (- 3)∙2 = - 4 записано в последней строке последнего столбца табл. 12. = , = . Числа , записаны в последней строке табл. 2 в столбцах, соответствующих свободным переменным х 2, х 4. Оценки базисных переменных х 1, х 3 равны нулю, т.к. эти переменные исключаются из целевой функции. Таким образом, целевая функция F (Х) = может быть записана через свободные переменные х 2, х 4 следующим образом: F (Х) = = . Исследуем полученную целевую функцию. Для этого представим заданную ЗЛП в виде, когда целевая функция и базисные переменные выражены через свободные переменные х 2, х 4: F (Х) = → max, ≥ 0, i = 1, 2, 3, 4. Свободные переменные могут принимать любые значения, кроме тех, которые нарушают условие неотрицательности. Пусть х 2 = х 4 = 0, тогда х 1 = 1 > 0, х 3 = 2 > 0, F (Х) = - 4 < 0, т.е. на опорном решении (1, 0, 2, 0) целевая функция отрицательна. Исходя из условия ЗЛП F (Х) → max, появляется закономерный вопрос: «Каким образом можно увеличить значение целевой функции?». Это можно сделать, если одну из свободных переменных оставить равной нулю (например, х 2 = 0), а другую взять положительной (например, х 4 > 0), тогда значение целевой функции F (Х) = , т.е. увеличилось. Отметим, что увеличивать х 4 беспредельно нельзя, поскольку при этом может нарушаться условие неотрицательности для переменных х 1, х 3. Если х 2 = 0, х 4 ≠ 0, то базисные переменные можно представить так: что равносильно ограничению для х 4: . Откуда наибольшее возможное значение х 4 = 12/7. Тогда Следовательно, целевая функция F (Х) = на ОР (11/7, 0, 0, 12/7), где х 1, х 4 – базисные переменные, х 2, х 3 - свободные. Преобразования сведены в табл. 3. Во 2-й строке первой части табл. 3 базисная переменная х 3 заменяется на х 4. Опорный элемент таблицы - dlS = d24 = 7/6 (выделен полужирным курсивом).
Таблица 3
Теперь целевая функция и базисные переменные х 1, х 4 выражаются через свободные переменные х 2, х 3 так: F (Х) = , Можно ли дальше увеличивать значение целевой функции F (Х)? Ответ дают следующие признаки.
|