Методы решения задачи программирования. Симплекс-метод Зуховицкого. Тема 5

1.

Тема
лекции
№5.
Методы
решения
задачи
программирования. Симплекс-метод Зуховицкого.
Цель лекции: Рассмотреть методы решения задачи
программирования. Симплекс-метод Зуховицкого.
линейного
линейного
Конспект лекции: Основным методом решения общей задачи линейного
программирования, позволяющим преодолеть затруднения, является так
называемый симплекс-метод.
Существует 4 вида симплекс- метода:
1) симплекс-метод обратных матриц;
2) симплекс-метод базисных переменных;
3) симплекс-метод Зуховицкого;
4) двойственный симплекс-метод.
Симплекс-метод состоит из алгоритма отыскания какого-нибудь
опорного среди решений системы линейных неравенств.
Симплекс-метод Зуховицкого.
Алгоритм метода Зуховицкого можно разобрать на следующие этапы:
1) перевод задачи к стандартному виду и построение симплекс-таблицы;
исключение свободных переменных;
2) исключение 0-строки;
3) определение опорного (допустимого) решения;
4) определение оптимального решения.
Основу вычислительной схемы алгоритма Зуховицкого составляют
модифицированные жордановы исключения (МЖИ). Алгоритм одного шага
МЖИ с разрешающим элементом состоит в следующем:
1. на месте разрешающего элемента в новой таблице записывается
единица;
2. остальные элементы разрешающей строки (r) остаются без изменений;
3. остальные элементы разрешающего столбца (s) изменяют лишь свои
знаки;
4. все остальные элементы таблица
формуле
β ij (i≠r , j≠s) вычисляются по
β ij=α ij α rs −α is α rj .
5. все элементы новой таблицы делятся на разрешающий элемент α rs .
Данный метод предназначен для решения задачи ЛП с ограниченияминеравенствами вида (5.1) либо смешанными ограничениями типа (5.1). При
этом предполагается, что все переменные x j неотрицательные, т. е.
x j ≥0;
j=1,...,n. Перейдем к подробному описанию метода. Первое, что
следует сделать, – это привести задачу к канонической форме. Далее нужно
проверить, что все правые части ограничений неотрицательны. Если это не
так, то обе части соответствующих равенств следует умножить на (-1).
1. Исключение «0-строк». Остановимся подробно на этапе исключение 0строк. Ограничения-равенства задачи ЛП запишем в виде 0-строк:

2.

0=a11 (−x 1 )+a12 (−x 2 )+...+a1n (−x n )+a1
... .... .............................. ......... ...........
0=a p 1 (−x 1 )+a p 2(−x 2 )+...+a pn (−x n )+a p .
(5.1)
При этом предполагаем, что свободные члены ai неотрицательны, т.е.
ai ≥0 ; i=1 ,. . ., p .
В случае, если это не так, то соответствующее уравнение (5.1)
умножаем на (-1). От ограничений-неравенств задачи ЛП переходим к
ограничениям равенствам путем введения дополнительных переменных
y p+1 =a p+1 (−x 1 )+a p+1,2 (−x 2 )+.. .+a p+1 , n (−x n )+a p+1 ≥0 ,
y m=a m 1 (−x 1 )+a m 2 (−x n )+. . .+amn (−x n )+a m≥0 .
y i≥0 , i=p+1,. .. ,m .
(5.2)
Используя соотношения (5.1), (5.2) составляем таблицу 5.2.
Просматриваем левый столбец таблицы 5.1, проверяем, есть ли в ней 0строки. Если отсутствуют, то переходим ко второму этапу.
Таблица 5.1
-х1
0
....
0
....
y p+1
....
ym
a11
....
ap 1
....
a p +1,1
....
am1
-х2
a12
....
ap 2
....
a p +1,2
....
am2
−x n
....
....
1
a1
....
ap
....
a p +1
....
am
a1 n
....
a pn
....
a p+1 ,n
....
amn
....
z
−c 1
−c 2
−c n
0
Тогда r -ю строку берем в качестве разрешающей, так что разрешающий
элемент будет α rs .
В случае вырождения, когда min {ai / ais }=0 , берем α rs в качестве
разрешающего столбца лишь при α rs >0 . Выполняем один шаг МЖИ
относительно разрешающего элемента.
Если разрешающим оказался элемент, стоящий в k-й 0-строке, т. е. r=k,
то после одного шага МЖИ относительно разрешающего элемента мы

3.

избавимся от k-й 0-строки, т. е. нуль, стоящий слева этой строки, попадает на
верх таблицы и будет вычеркнут вместе с расположенным под ним столбцом,
что уменьшит размерность таблицы на один столбец.
Если же разрешающим оказался элемент, не стоящий в 0-строке, то
продолжаем шаги МЖИ, работая с k-й 0-строкой (т.е. выбирая каждый раз
разрешающий элемент из столбца, содержащего положительный
коэффициент k-й 0-строки) до тех пор, пока либо не избавимся от k-й 0строки, либо в k-й 0-строке не останется ни одного положительного
коэффициента при положительном свободном члене, что означает
несовместность системы.
2. Поиск опорного решения. Процесс поиска опорного решения начинается с
просмотра столбца свободных членов. Если все свободные члены
неотрицательны, то в этом случае таблица дает возможность получить сразу
одно из опорных решений задачи ЛП. Это решение получается, если все
независимые переменные, стоящие в верхней части таблицы, приравнять 0.
Пусть есть хотя бы один отрицательный член, например, α i <0 . В данном
случае мы не можем получить опорное решение, приравнивая переменные,
стоящие в верхней части таблицы, нулю, т. к. получаем y i=α i < 0 . Но это
противоречит условию неотрицательности y i .
Симплекс-метод для отыскания опорного решения означает правило
перехода от данной вершины к такой вершине, которую отделяет от
многогранника меньшее число плоскостей, т. е. для которых в
соответствующей таблице содержится меньшее число отрицательных
свободных членов.
Производим один шаг модифицированного жорданова исключения,
выбирая разрешающий элемент по следующим правилам:
1. выбираем строку с отрицательным свободным членом, пусть
например, α i <0 .
Если среди коэффициентов этой строки нет отрицательных, то система
ограничений несовместна, т. к. мы не можем избавиться от отрицательного
свободного члена;
2. если же среди коэффициентов рассматриваемой строки есть
α is <0
отрицательные, то берем любой из них, пусть
и столбец,
содержащий этот коэффициент, берем в качестве разрешающего;
3. выбор разрешающей строки производится так. Вычисляем все
ai /ais ≥0
неотрицательные
отношения
свободных
членов
к
соответствующим отличным от нуля коэффициентам разрешающего столбца.
Находим среди них наименьшие отношения, пусть это ars /ars . Тогда r-ю
строку берем в качестве разрешающей, так что ars − разрешающий элемент.
Как и при исключении 0-строк, в случае вырождения, когда
min {ai /ais }=ar /ars =0 , мы берем ars в качестве разрешающего лишь при

4.

ars >0 .
Если разрешающий элемент оказался в l-й строке, то после шага
модифицированного жорданова исключения новый свободный член b ℓ
рассматриваемой l-й строки станет уже положительным.
В противном случае мы продолжаем работать с этой строкой до тех пор,
пока либо избавимся от отрицательности ее свободного члена, либо
установим несовместность исходной системы ограничений. Так поступаем
последовательно со всеми строками, в которых свободные члены
отрицательные.
3. Отыскание оптимального решения. После нахождения опорного решения
мы получим таблицу, в которой все элементы столбца свободных членов
являются
неотрицательными.
Начинаем
просматривать
z-строку,
предполагая, что решается максимизация функции. Если все коэффициенты
этой строки неотрицательны, то задача ЛП решена, а оптимальное решение
может быть получено, если приравнять переменные, стоящие в верхней части
таблицы нулю.
Пусть среди коэффициентов z-строки есть отрицательные, например,
пусть q s >0 . Симплекс-метод для отыскания оптимального решения
представляет специальное правило перехода от полученной вершины к
соседней вершине многогранника, в котором значение z больше. Этот
процесс продолжается, пока не будет найдена вершина, в которой значение Z
максимально, т.е. для которой все коэффициенты Z-строки будут
неотрицательны, или пока не будет установлено, что функция не ограничена
сверху.
Выбор разрешающего элемента производится по следующему правилу:
1. в качестве разрешающего берем столбец, содержащий отрицательный
элемент Z-строки q j ;
2. отбираем все положительные коэффициенты этого столбца, делим на
них соответствующие свободные члены, берем среди этих отношений
наименьшее, пусть это достигается при i=r.
ars
Тогда r-ю строку берем разрешающей, так что элемент
разрешающий.
Производим
шаг
модифицированных
жордановых
исключений, знак элемента q s изменится на противоположный. Так
поступаем до тех пор, пока Z не ограничена сверху.
Контрольные вопросы:
1 Перечислите основные этапы симплекс-метода.
2 Из каких пунктов состоит один шаг МЖИ?
3 Как определяется разрешающий элемент(РЭ) при исключении свободной
переменной?
4 Как определяется РЭ при исключении 0-строки?
5 Как определяется РЭ при определении допустимого решения?
6 Как определяется РЭ при определении оптимального решения?
7 Литература:

5.

8 1. Акулич И.Л. Математическое программирование в примерах и задачах, Изд. "Высшая
школа" 1986.
9 2. Бурков В.Н., Кулжабаев Н.М. Активные системы и деловые игры–Алматы:2000.
10
3. Бурков В.Н. Основы математической теории активных систем. М.: Наука, 1977.
11
4.Вентцель Е.С. Исследование операций. Задачи, принципы, методология –
Москва: Наука, 1988
12
5.Зуховицкий С.И. Авдеева Л.И. Линейное и выпуклое программирование, Изд.
"Наука". Москва 1967.
13
6.Кулжабаев Н.М. Исследование операции. Учебное пособие. –Алматы:РИК КАО
имени И.Алтынсарина,1999.
14
7.Кулжабаев Н.М. Муханова Г.С. Системный анализ и исследование операции.