Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Какие действия с целевой функцией не влияют на результат решения задачи линейного программирования?



Оптимальное решение задачи линейного программирования не изменится, если целевую функцию помножить на любое положительное число, либо прибавить к целевой функции любое число.

Доказательство этого утверждения можно провести самостоятельно, используя графический метод решения задачи линейного программирования.

Рассмотрим общую задачу линейного программирования:

Вектор α0 является оптимальным решением задачи (1) – (4) на максимум тогда и только тогда, когда α0 является оптимальным решением задачи (1)–(4) на минимум.

Необходимость. Пусть W есть множество допустимых решений задачи (1)–(4) и задачи (1)–(4), а вектор α0 является оптимальным решением задачи (1)–(4) на максимум. Тогда, по определению глобального максимума, выполняется неравенство f(α0) ≥ f(α) для любого вектора α W. Умножив последнее неравенство на минус единицу, получим новое неравенство –f(α0) ≤ –f(α) и с учетом обозначения целевой функции задачи (1)–(4) имеем f10) ≤ f1(α) для любого вектора α W. Откуда, по определению глобального минимума функции f1(X), вектор α0 является оптимальным решением задачи (1)–(4) на минимум. Таким образом, необходимость доказана. Для доказательства достаточности следует провести рассуждения в обратной последовательности.■

Замечание. В дальнейшем будем рассматривать решение задач линейного программированиятолькона минимум, так как задача на максимум может быть сведена к соответствующей задаче на минимум.

13.Опишите последовательность решения канонической задачи линейного программирования с n переменными m линейных уравнений, если
1 n – m 2.

Графическим методом можно решать задачу линейного программирования, если число переменных – n и число уравнений – m в системе ограничений этой задачи удовлетворяют соотношению 1 n – m 2.

Для этого необходимо:

- найти методом Гаусса общее решение системы линейных уравнений, которая является системой ограничений исходной задачи линейного программирования;

- исключив разрешенные переменные из полученного общего решения, получить систему из m неравенств с (n–m) переменными;

- из полученного общего решения выразить разрешенные переменные через свободные переменные и подставить их в целевую функцию, которая станет функцией (n–m) свободных переменных;

- решить графическим методом полученную задачу линейного программирования с (n–m) свободными переменными, с ограничениями в виде m неравенствами, а также с ограничениями на знак переменных;

- найденные свободные переменные подставить в общее решение, вычислить значения разрешенных переменных и записать оптимальное решение исходной задачи.

 

 




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

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.