Полная версия

Главная arrow Экономика arrow Исследование операций в экономике

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

5.5. Особые случаи симплексного метода

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

Неединственность оптимального решения (альтернативный оптимум)

5.7. Решить симплексным методом задачу:

при ограничениях:

Решение. Геометрическое решение задачи приведено в задаче 4.3 (см. рис. 4.3, а): оптимум достигается в любой точке отрезка АВ, так как линия уровня параллельна этому отрезку. Покажем, как проявляется наличие альтернативного оптимума при решении задачи симплексным методом.

На очередном шаге получаем:

основные переменные: xv х2, х5; неосновные переменные: ху хг

Выражаем основные переменные через неосновные:

Хх = (3; 5; 0; 0; 9) – допустимое базисное решение, соответствующее угловой точке /4(3; 5). Линейная функция F = 24 – х(. В этом выражении отсутствуют положительные коэффициенты при неосновных переменных, значит, критерий оптимальности выполнен, Xt – оптимальное базисное решение, Fmax = f(X, ) = 24. Однако в последнем выражении для F отсутствует неосновная переменная .г4 (формально входит с нулевым коэффициентом), поэтому изменение этой переменной нс повлечет за собой изменение линейной функции. Например, можно перевести в основную переменную х4; х4 = min {15; ∞; 9} = 9. Переменная х5 перейдет в неосновные, однако изменения линейной функции пе произойдет: AF = 9 ∙ 0 = 0. Действительно, на следующем шаге получим новое базисное решение: Х2 = (6; 2; 0; 9; 0), соответствующее угловой точке В(6; 2), Fmax = F(X2) = 24 (рекомендуем читателю убедиться в этом самостоятельно). Учитывая, что переменная х3 = 0 (в базисном решении Х2 она осталась неосновной), а переменная х4 удовлетворяет неравенству 0 < х4 < 9, из системы уравнений можно получить все множество оптимальных решений задачи. Положим для удобства х4 = 7, где 7е [0; 9]. Тогда множество оптимальных решений: х, =3 + (1/3)7, х2 =5-(1/3)7, х3 = 0, x4=t, х5=9 + 7 (7€ [0; 9]).

Замечание. В соответствии с теоремами 3.3 и 3.4 множество оптимальных решений можно представить как выпуклую линейную комбинацию X базисных решений Х{ = (3; 5; 0; 0; 9) и Х2 = (6; 2; 0; 9; 0), т.е. в соответствии с выражениями (3.5) и (3.4) имеем: X = оХ{ + (1 – а)Ху где 0 < а ≤ 1, или X = (6 – За; 2 + За; 0; 9 – 9а; 9а), где 0 < а < 1. ►

Появление вырожденного базисного решения

5.8. Решить симплексным методом задачу:

при ограничениях:

Решение. После введения дополнительных переменных, которые возьмем в качестве основных, получим

I шаг. Основные переменные: х3, х4, х5.

Неосновные переменные: х,, х2.

После преобразований получим

X, = (0; 0; 2; 6; 14) – допустимое базисное решение.

F = 2.r,-x2, Fj = F(X,) = 0. Критерий оптимальности на максимум не выполнен, поэтому переводим в основные переменную xv так как в выражение для F она входит с положительным коэффициентом: x, = min {2; 6/3; 14/6} = 2. Оценочные отношения в двух первых уравнениях совпадают, поэтому в качестве разрешающего можно взять любое из них, например первое.

II шаг. Основные переменные: xv χν х5.

Неосновные переменные: хт хт

Получим после преобразований

Х2 = (2; 0; 0; 0; 2) – вырожденное базисное решение, основная компонента х4 = 0.

Линейная функция цели, выраженная через неосновные переменные, имеет вид: F = 4 + x2-2x3. Переводя переменную х.г в основные, получаем: х2 = min{°°; 0; 1} = 0, поэтому на следующем шаге изменения функции цели не произойдет, AF = 0 1 = 0. Это нарушение принципа улучшения решения, который должен выполняться при использовании симплексного метода, в связи с чем уточним данный принцип: каждый следующий шаг должен улучшить или, в крайнем случае, не ухудшить значение линейной функции.

III шаг. Основные переменные: xv х2, .г..

Неосновные переменные: x3, хг

После преобразований получим

X., = (2; 0; 0; 0; 2) – это базисное решение тоже вырождено. Покомпонентно оно совпадает с Х2, однако формально отличается набором основных переменных. Выражение линейной функции через неосновные переменные имеет вид: F = 4 + х34; F(X3) = 4. (Решение предлагается продолжить читателю самостоятельно.) ►

Выполненный шаг, хотя и не вызвал увеличения значения линейной функции, не является лишним, так как привел к новому базисному решению. Наличие "пустых" шагов (∆F= 0) может привести к так называемому зацикливанию, т.е. возвращению к ранее найденному допустимому базисному решению (с тем же набором основных и неосновных переменных), и в этом случае процесс бесконечен. Избежать "зацикливания" можно с помощью определенных мер, которые в данном пособии не рассматриваются. Задачи с "зацикливанием" встречаются крайне редко, так как к нему приводит не только вырождение, но и сочетание его с другими специфическими условиями.

Вывод. Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающим является любое из них. На следующем шаге получаем вырожденное базисное решение, переход к очередному базисному решению может не изменить функцию цели (AF = 0).

Замечание. Вырождение, полученное при оптимальном решении, может привести к альтернативному оптимуму даже при ненулевых коэффициентах при всех неосновных переменных в линейной функции (об этом упоминалось при рассмотрении случая альтернативного оптимума).

Отсутствие конечного оптимума ( или )

5.9. Решить симплексным методом задачу:

при ограничениях:

Решение. Геометрическое решение этой задачи приведено в задаче 4.3 (см. рис. 4.5, б). На очередном шаге решения этой задачи симплексным методом получаем основные переменные хр х2, .г.; неосновные переменные х3, х4.

X = (5/3; 7/3; 0; 0; 4) – базисное решение; F = ; минимум не достигнут, так как критерий оптимальности на это условие не выполнен: переменная х3 имеет отрицательный коэффициент в выражении для F. Определяем х3 = min (∞; ∞; ∞} = ∞, так как в каждое из трех уравнений эта переменная входит с тем же знаком, что и свободный член. Уравнения не ограничивают рост х3, поэтому и значение функции F не ограничено и отрицательно, т.е. F. = -оо.

Вывод. Если на каком-либо шаге получаем, что базисное решение допустимое и во всех уравнениях системы бесконечны оценочные отношения той переменной, которая переводится в основные, то задача не имеет конечного оптимума (Fm.K = ∞, если задача на отыскание максимума, и F. = -∞, если задача на отыскание минимума).

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

 
<<   СОДЕРЖАНИЕ   >>