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

Главная arrow Математика, химия, физика arrow Математика

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


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Отыскание оптимального решения основной задачи линейного программирования

В предыдущем параграфе мы научились находить опорное решение системы уравнений ОЗЛП; при этом мы вовсе не занимались минимизируемой функцией L. Теперь приступим к оптимизации решения, т.е. найдем такое опорное решение, которое обращает в минимум линейную функцию

Методика оптимизации решения была изложена в §5 главы 3. Теперь на примерах покажем, как эта оптимизация может быть проведена с помощью табличного алгоритма замены х. <-> у..

ОПРИМЕР 3.10. Найти решение задачи линейного программирования с уравнениями

обращающее в минимум линейную функцию

Решение. Все свободные члены в (3.45) неотрицательны, значит, опорное решение очевидно:

Является ли оно оптимальным? Нет, так как коэффициенты при х2 и х3 в (3.46) положительны, и, увеличивая эти переменные, мы уменьшаем L.

Запишем (3.45) и (3.46) в виде стандартной таблицы (табл. 3.18).

Так как коэффициенты в первой строке при х2 и х3 положительны, любую из этих переменных можно вывести из числа свободных. Пусть это будет х3. Какой из элементов столбца х3 выбрать разрешающим? Этот элемент должен быть положительным.

Свободный

член

*2

*3

L

0

-1

2

1

У^

2

1

1

-2

У2

1

1

-1

Уу

5

0

1

1

У 4

2

2

-1

0

Значит, у нас есть выбор: 1 в строке у2 или 1 в строке уу Выберем из них тот, для которого отношение к нему свободного члена минимально (обоснование см. в § 5 главы 3).

Отношения равны 1 / 1 = 1; 5 / 1 = 5. Минимальное из них 1. Значит, в качестве разрешающего нужно взять элемент 1 в столбце ху строке у2. Произведем замену х3 у2 (табл. 3.19 и 3.20).

В верхней строке табл. 3.20 есть положительный коэффициент при xv значит, х2 надо вывести из свободных переменных. Выбираем в качестве разрешающего тот положительный элемент столбца Ху для которого отношение к нему свободного члена минимально. Однако в столбце х2 единственный положительный элемент 2, его и выбираем в качестве разрешающего (табл. 3.20 и 3.21).

Оказывается, процедура еще не закончена: в первой строке табл. 3.22 имеется положительный элемент в столбце у2, значит, переменную у2 нужно вывести из числа свободных. В качестве разрешающего берем тот из положительных элементов столбца у7, для которого отношение к нему свободного члена минимально. Сравнивая отношения

Таблица 3.20

Свободный

член

*i

х2

У2

L

-1

-2

3

-1

Ух

4

3

-1

2

х3

1

1

-1

1

Уз

4

-1

(3)

-1

Уа

2

2

-1

0

Таблица 3.22

Свободный

член

Уз

у2

L

-7

_ 1

2

_ 3 2

  • 1
  • 2

Ух

6

  • 5
  • 2
  • 1
  • 2

©

3

  • 1
  • 2
  • 1
  • 2
  • 1
  • 2

X2

2

_ 1

2

  • 1
  • 2

_ 1

2

У 4

4

  • 3
  • 2
  • 1
  • 2

_ 1

2

выбираем в качестве разрешающего элемент 3/2 в строке у и столбце у2 и продолжаем процедуру оптимизации (табл. 3.23 и 3.24).

Таблица 3.23

В первой строке табл. 3.24 нет ни одного положительного элемента; значит, оптимальное решение достигнуто; оно таково:

*1 = >'з = У = 0; у2 = 4; *3 = 1; *2 = 4; у4 = 6.

При этих значениях переменных линейная функция L достигает своего минимального значения, равного

Возникает вопрос: как быть, если в столбце, содержащем положительный элемент строки L, не найдется ни одного положительного элемента, чтобы сделать его разрешающим? Легко убе-

Свободный

член

Уз

Ух

L

-9

  • 4
  • 3
  • 5
  • 3
  • 1
  • 3

У 2

4

  • 5
  • 3
  • 1
  • 3
  • 2
  • 3

1

  • 1
  • 3
  • 1
  • 3
  • 1
  • 3

х2

4

  • 1
  • 3
  • 2
  • 3
  • 1
  • 3

У 4

6

  • 7
  • 3
  • 2
  • 3
  • 1
  • 3

диться, что в этом случае функция L не ограничена снизу и ОЗЛП не имеет оптимального решения.

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

Итак, сформулируем правила нахождения оптимального решения ОЗЛП симплекс-методом.

  • 1. Если все свободные члены (не считая строки L) в симплекс- методе неотрицательны, а в строке L (не считая свободного члена) нет ни одного положительного элемента, то оптимальное решение достигнуто.
  • 2. Если в строке L есть положительный элемент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то линейная функция L не ограничена снизу и оптимального решения не существует.
  • 3. Если в этом столбце есть положительные элементы, то следует произвести замену одной из свободных переменных на одну из базисных, причем в качестве разрешающего надо взять такой элемент этого столбца, для которого отношение к нему соответствующего свободного члена минимально.

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

>ПРИМЕР 3.11. Найти решение задачи линейного программирования с условиями

обращающее в минимум линейную функцию

Решение. Записываем (3.47) и (3.48) в виде стандартной таблицы (см. табл. 3.25). Согласно общему правилу, находим в столбце х2 разрешающий элемент, для которого отношение к нему свободного члена неотрицательно и минимально. Сравнивая отношения 0:1 и 2:1, останавливаемся на разрешающем элементе 1 в строке у , для которого это отношение равно нулю. Осуществляем замену (табл. 3.26 и 3.27).

Таблица 3.25

Свободный

член

х2

*3

*4

L

0

-2

1

0

0

У.

0

-1

Q

0

0

2

0

1

-1

0

Уз

1

0

0

-1

-1

Таблица 3.27

Свободный

член

У

*3

*4

L

0

-1

-1

0

0

х2

0

-1

1

0

0

у2

2

1

-1

-1

0

Уз

1

0

0

-1

-1

При переходе от табл. 3.25 к табл. 3.27, естественно, не произошло уменьшения линейной функции L (она как была, так и осталась равной нулю), однако все элементы верхней строки стали неположительными, из чего видно, что оптимальное решение достигнуто: минимум функции равен нулю и достигается при *1 = У = *3 = х4= 0; Х2 = 0; у2 = 2; у3 = 1. ?

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>