Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Критерий оптимальности решения поиска максимума целевой функции. ⇐ ПредыдущаяСтр 2 из 2
Если в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты при СП для задачи поиска максимума, то решение является оптимальным. Если решение является оптимальным, то наша целевая функция достигла своего максимума и на этом решение задачи закончено, а если нет, то переходим к шагу . В примере 1 – неоптимальное, т.к. все коэффициенты положителены.
Шаг . Определить свободную переменную, преходящую в базис и базисную, становящуюся свободной. Правило: В базис переходит одна из свободных переменных, имеющая положительный коэффициент в целевой функции. x 1 → БП Условие неотрицательности переменных в системе (8) при равной нулю свободной переменной x 2=0: Выпишем значения, до которых может возрастать x 1: и выберем наименьшее: Уравнение системы (8), в котором базисная переменная обращается в нуль, называется разрешающим: Соответствующая базисная переменная становится свободной. x 4 → СП. Повторяем шаги алгоритма. Шаг . БП: x 1, x 3, x 5; СП: x 2, x 4. Шаг Упрощаем: Шаг 2 = (2; 0; 6; 0; 1) Шаг f( 2) = 8. Шаг Так как коэффициент при x 2 остался положительным, то решение не оптимально. Шаг x 2 → БП При x 4=0 x 2 может возрастать до . Разрешающее уравнение: x5 → СП. Шаг . БП: x 1, x 2, x 3; СП: x 4, x 5. Шаг Упрощаем: Шаг 3 = (1; 2; 3; 0; 0) Шаг f( 3) = 10. Шаг
Так как в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты, найденное решение является оптимальным. опт = (1; 2; 3; 0; 0) fопт= 10. Замечание: Случай минимизации целевой функции: Способ 1. Рассматривать Задача сводится к рассмотренной. Способ 2. Изменить критерий оптимальности.
|