Задача 1 (п.4.2).
Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком “плюс”, так как все неравенства имеют вид «≤».
Получим систему ограничений в виде:
,
,
,
.
Для нахождения первоначального базисного решения разобьем переменные на две группы - основные и неосновные. так как определитель, составленный из коэффициентов при дополнительных переменных х3, х4, х5,х6, отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи. При выборе основных переменных на первом шаге не обязательно составлять определитель из их коэффициентов и проверять, равен ли он нулю. Достаточно воспользоваться следующим правилом: в качестве основных переменных на первом шаге следует выбрать (если возможно) такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений, при этом нет таких уравнений системы, в которые не ходит ни одна из этих переменных.
|
|
Дополнительные переменные удовлетворяют этому правилу. Если выбранные по этому правилу переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях уравнений, то полученное таким образом базисное решение будет допустимым. В данном случае так и получилось.
i шаг. Основные переменные: х3, х4, х5, х6. неосновные переменные: х1, х2. Выразим основные переменные через неосновные:
, (7)
Положив неосновные переменные равными нулю, т.е. х1 =0, х2 = 0, получим базисное решение х1= (0; 0; 18; 16; 5; 21), которое является допустимым и соответствует вершине О (0;0) многогранника ОАВСDЕ на рис. 2.
Рис. 2
Поскольку это решение допустимое, нельзя отбросить возможность того, что оно оптимально. выразим линейную функцию через неосновные переменные: .
При решении х1 значение функции равно . Легко понять, что функцию f можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для f с положительным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная будет неосновной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функций “лучше” (по крайней мере “не хуже”). В данном примере для увеличения f можно переводить в основные либо х1, либо х2, так как обе эти переменные входят в выражение дня f со знаком “плюс”. Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент, т.е. в данном случае х2 (такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки).
|
|
Система (1) накладывает ограничения на рост переменной х2. поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х1 = 0 как неосновная переменная):
откуда
Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение - границу роста переменной х2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х2 при условии, что эти числа имеют разные знаки. Последнее уравнение системы не ограничивает рост переменной х2, так как данная переменная в него не входит (или формально входит с нулевым коэффициентом). В этом случае условимся обозначать границу символом ∞. Такой же символ будем использовать, когда свободный член и коэффициент при переменной в уравнении имеют одинаковые знаки, так как и в этом случае нет ограничений на рост переменной.
Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом ∞. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение). Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х2 определяется как х2 =min (18/3; 16/1; 5/1; ∞} =5. при х2 =5 переменная х5 обращается в нуль и переходит в неосновные.
Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна), называется разрешающим. В данном случае - это третье уравнение. разрешающее уравнение будем выделять рамкой в системе ограничений.
ii шаг. Основные переменные: х2, х3,х4, х6. неосновные переменные: х1, х5.
Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х2):
или
(8)
Второе базисное решение является допустимым и соответствует вершине а (0;5) на рис. 2. Геометрическая интерпретация перехода от х1 к х2 — переход от вершины о к соседней вершине а на многоугольнике решений ОАBCDЕ.
Выразив линейную функцию через неосновные переменные на этом шаге, получаем:
Значение линейной функции f2 = f (х2) =15. изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной функции; в данном случае
Однако значение f2 не является максимальным, так как повторяя рассуждения 1 шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной х1, входящей в выражение для f с положительным коэффициентом. Система уравнений (8) определяет наибольшее возможное значение для х1: х1 = min{∞;3/1;11/2; ∞} = 3. второе уравнение является разрешающим, переменная х3 переходит в неосновные, при этом
|
|
iii шаг. Основные переменные: х1, х2, х4, х6. неосновные переменные х3, х5.
Как и на ii шаге, выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для хi). после преобразований получаем:
,
,
, (9)
.
Базисное решение х3 = (3; 5; 0; 5; 0; 12) соответствует вершине в (3;5). выражаем линейную функцию через неосновные переменные . Проверяем: Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х5 в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х5 в основную переменную. при определении наибольшего возможного значения для х5 следует обратить внимание на первое уравнение в системе (9), которое не дает ограничений на рост х5, так как свободный член и коэффициент при х5 имеют одинаковые знаки. Поэтому . Третье уравнение является разрешающим, и переменная х4 переходит в неосновные; .
iv шаг. Основные переменные: х1, х2, х5, х6. неосновные переменные: х3, х4.
После преобразований получим:
,
,
,
.
Базисное решение соответствует вершине с (6; 4) на рис. 2.
Линейная функция, выраженная через неосновные переменные, имеет вид: .это выражение не содержит положительных коэффициентов при неосновных переменных, поэтому значение максимальное. Функцию f невозможно еще увеличить, переходя к другому допустимому базисному решению, т.е. решение х4 оптимальное. Вспоминая экономический смысл всех переменных, можно сделать следующие выводы.
Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции и 4 единиц продукции Дополнительные переменные х3, х4, х5, х6 показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптимальном плане производства , т.е. остатки ресурсов s1 и s2 равны нулю, а остатки, ресурсов s3 и s4 равны соответственно 1 и 3 единицам.