double arrow

Решение.. Чтобы вид системы ограничений был упорядоченным, надо умножить первые 3 ограничения на -1

Чтобы вид системы ограничений был упорядоченным, надо умножить первые 3 ограничения на -1.

БП СЧ CO
-5 -2 5/2
-3 4 -2 -
-6 -3 2
F -4 -1  
БП СЧ
-1 -2/3 5/3 -2/3
-11 4/3 11/3 10/3
-1/3 -2/3 -4/3
1/3 5/3 7/3
F -4/3 -11/3 -13/3

Ответ: система ограничений несовместна и задача не имеет решения.

Вырожденные задачи линейной оптимизации

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

Вырожденность может иметь место при нахождении опорного решения и оптимального. Способы ликвидации вырожденности в обоих случаях одни и те же.

Опасность вырожденности.

Если мы находим опорное решение, то в соответствии с алгоритмом за разрешающий столбец принимаем тот, который содержит отрицательный элемент в строке с отрицательным свободным членом. Разрешающей строкой в этом случае будет та, в которой базисная неизвестная равна нулю, т.к. наименьшее симплексное отношение будет равно нулю. Это значит, что величина новой переменной, вводимой в базис, будет равна нулю, и решение в новой таблице останется неопорным. При продолжении процесса, строка с нулевым элементом будет оставаться разрешающей, а изменения будут происходить в наборе базисных и небазисных неизвестных, и мы можем прийти к таблице, которая уже была, т.е. может наступить случай зацикливания.

Чтобы избежать вырожденности, а следовательно, и зацикливания, искусственно припишем нулевому элементу в столбце свободных членов знак ‘+’, а разрешающим столбцом будем выбирать тот, в котором находятся два отрицательных элемента: один – в строке с отрицательным, а другой – в строке с нулевым свободным членом.

Аналогично поступаем с вырожденной задачей при нахождении оптимального решения. За разрешающий столбец выбирается столбец, который содержит два отрицательных элемента: один – в строке с нулевым свободным членом, второй — в строке функции. Разрешающая строка находится, как обычно, по минимальному симплексному отношению.

Если при нахождении опорного или оптимального решения нельзя выбрать разрешающий столбец, в котором были бы два отрицательных элемента, то разрешающий столбец находится по общим правилам.


Сейчас читают про: