Оптимальное решение задачи линейного программирования не изменится, если целевую функцию помножить на любое положительное число, либо прибавить к целевой функции любое число.
Доказательство этого утверждения можно провести самостоятельно, используя графический метод решения задачи линейного программирования.
Рассмотрим общую задачу линейного программирования:
Вектор α0 является оптимальным решением задачи (1) – (4) на максимум тогда и только тогда, когда α0 является оптимальным решением задачи (1’)–(4’) на минимум.
▲ Необходимость. Пусть W есть множество допустимых решений задачи (1)–(4) и задачи (1’)–(4’), а вектор α0 является оптимальным решением задачи (1)–(4) на максимум. Тогда, по определению глобального максимума, выполняется неравенство f(α0) ≥ f(α) для любого вектора α W. Умножив последнее неравенство на минус единицу, получим новое неравенство –f(α0) ≤ –f(α) и с учетом обозначения целевой функции задачи (1’)–(4’) имеем f1(α0) ≤ 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 неравенствами, а также с ограничениями на знак переменных;
- найденные свободные переменные подставить в общее решение, вычислить значения разрешенных переменных и записать оптимальное решение исходной задачи.