Критерий оптимальности решения поиска максимума целевой функции.

Если в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты при СП для задачи поиска максимума, то решение является оптимальным.

Если решение является оптимальным, то наша целевая функция достигла своего максимума и на этом решение задачи закончено, а если нет, то переходим к шагу .

В примере 1 – неоптимальное, т.к. все коэффициенты положителены.

 

Шаг . Определить свободную переменную, преходящую в базис и базисную, становящуюся свободной.

Правило: В базис переходит одна из свободных переменных, имеющая положительный коэффициент в целевой функции.

x1 → БП

Условие неотрицательности переменных в системе (8)

при равной нулю свободной переменной x2=0:

Выпишем значения, до которых может возрастать x1:

и выберем наименьшее:

Уравнение системы (8), в котором базисная переменная обращается в нуль, называется разрешающим:

Соответствующая базисная переменная становится свободной.

x4 → СП.

Повторяем шаги алгоритма.

Шаг .

БП: x1, x3, x5;

СП: x2, x4.

Шаг

Упрощаем:

Шаг

2 = (2; 0; 6; 0; 1)

Шаг

f( 2) = 8.

Шаг

Так как коэффициент при x2 остался положительным, то решение не оптимально.

Шаг

x2 → БП

При x4=0

x2 может возрастать до

.

Разрешающее уравнение:

x5 → СП.

Шаг .

БП: x1, x2, x3;

СП: x4, x5.

Шаг

Упрощаем:

Шаг

3 = (1; 2; 3; 0; 0)

Шаг

f( 3) = 10.

Шаг

 

Так как в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты, найденное решение является оптимальным.

опт = (1; 2; 3; 0; 0)

fопт= 10.

Замечание:

Случай минимизации целевой функции:

Способ 1.

Рассматривать

Задача сводится к рассмотренной.

Способ 2.

Изменить критерий оптимальности.

 








Дата добавления: 2015-11-06; просмотров: 1029;


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

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.