/I е гк о Ь
И-Ъ.
Методы оптимизации
ФАКУЛЬТЕТ
УДК 519.72
ББК В 183.4я73
М 54
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2008 года
Рецензент
кафедра информационных и сетевых технологий
Ярославского государственного университета им. П.Г. Демидова
Составитель: Н.В. Легкое
Методы оптимизации: метод, указания / сост. Н.В. Лег-
кое; Яросл. гос. ун-т. - Ярославль : Яр ГУ, 2008. - 32 с.
Приводятся описания методов решения задачи линейно-
го программирования. Рассмотрены графический метод и
симплекс-метод. Для симплекс-метода приводится метод
искусственного базиса нахождения начального решения.
Предназначены для студентов, обучающихся по направ-
лению 010500 Прикладная математика и информатика и
специальностям 010503 Математическое обеспечение и
администрирование информационных систем и 010501
Прикладная математика и информатика (дисциплина «Ме-
тоды оптимизации», блок ЕН, ОПД), очной формы обуче-
ния.
УДК 519.72
ББК В 183.4я73
© Ярославский государственный университет, 2008
1. Постановки задач
линейного программирования
Задача минимизации функции п переменных fix)=f(x}, ...,xj на
некотором множестве V<zEni не совпадающем со всем пространст-
вом Еп и заданном с помощью ограничений (равенств и нера-
венств) на координаты Xj точки х из пространства Ет называется
задачей математического программирования. При этом функцию
f(x) называют целевой функцией, а множество U - допустимым
множеством.
Решение задач математического программирования, как пра-
вило, связано со значительно большими трудностями, чем реше-
ние задач безусловной минимизации.
Простейшим частным случаем задачи математического про-
граммирования является задача линейного программирования
(ЗИП), состоящая в минимизации линейной целевой функции
п
=Х CjXj на множестве U^En, заданном системой
линейных ограничений (равенств и (или) неравенств) на коорди-
наты х^
Задача линейного программирования в общей форме форму-
лируется следующим образом:
Среди точек x=(xi,...,xn)eEn> удовлетворяющих ограничениям
п
ajjXj—bi, i- 1,2,...,I,	(1)
7=1
n
S aijXj <bi,i=l+l,...,m;	(2)
/=•
Xj >0,
n
найти те, в которых функция f(x)=X CjXj принимает минимальное
значение, и определить это значение.
Отметим, что в условии задачи линейного программирования
могут содержаться неравенства и противоположного, чем в (2),
3
знака, однако такие неравенства легко сводятся к виду (2) умно-
жением на -1.
Если в условии задачи линейного программирования не со-
держатся ограничения-неравенства (2), т.е. в (1) 1=т, то она назы-
вается задачей линейного программирования в каноническом виде.
Вводя дополнительные переменные хп^ >0, i=l+l,...,m, огра-
ничения-неравенства (2) можно записать в виде равенств
п
S aijXj+xn+i=bi, i=l+l,...,m.
7=1
Таким образом, любая задача линейного программирования
может быть записана в каноническом виде
п
f(x)=S CjXj-> min,	(3)
7=1
п
Е aijXj=bi,i=l,2,	(4)
7=1
Xj >0.	(5)
Часто используется векторная запись задачи (3)-(5)]:
f(x)=(c,x)-> min,
Ax=b,	(6)
х >0,
где x=(xl,...,xn) - вектор неизвестных, c=fc;,...,cj - вектор коэф-
фициентов целевой функции из (3), А=(ау) - прямоугольная мат-
рица размера mxn, b-(blf...,b,) - вектор правых частей системы
(4), ах >0 - краткая запись условий неотрицательности (5).
Третий часто используемый вид постановки задачи линейного
программирования - стандартная, или симметричная, форма. В
ней отсутствуют ограничения равенства:
п
Цх)=Е CjXj-*Tmn,	(7)
/=1
п
X aijXj <bj,i=l,2..m;	(8)
xj >0.	(9)
Векторная запись задачи (7)-(9)]:
f(x)=(c,x)-* min,
Ах <b,	(10)
х >0.
4
Иногда возникает необходимость привести задачу линейного
программирования, заданную в общей форме записи, к канониче-
ской форме. Рассмотрим на простых примерах несколько методов,
позволяющих сделать такое преобразование.
Пример 1. Привести к канонической форме записи задачу
xi+x2 min
Х1-Х2 < 1
2xi+x2=2
X] >0.
◄ Для того чтобы первое ограничение записать в форме ра-
венства, введем неотрицательную переменную х3 (х3 > 0). Заме-
ним переменную х2, на значение которой не наложено требование
неотрицательности, разностью двух неотрицательных перемен-
ных:
^=х,-^,Где
После этих преобразований исходная задача запишется в ка-
нонической форме:
+х2 -х2 —>min
2xj +х> -х,
jq i >0.	►
Пример 2. Привести к канонической форме записи задачу:
X] + 2х2 - 2х3 min
х[+х2-х,<1,
2xj + ах2 + х3 = 2 ?
•^з -0.
◄ Введем дополнительную неотрицательную переменную х3
(х, > 0) и запишем первое ограничение задачи в виде равенства:
jq +Х2 -х, +х4 =1.
Исключим из системы равенств переменные хх и х2, не свя-
занные условием неотрицательности. Для этого рассмотрим сис-
тему'
5
Л1+Л2_-Х3+Х4-1,
2Х| +ях2 +х3 =2.
Здесь возможны два случая.
Случай 1. а *2. Переменные xt и х2 единственным образом
выражаются через х3 и х4:
*i = — (2 -«-(« + 1)х3 + ах4),
2-«
л2 - —	(З*3 ~ 2х4) .
2 - а
При подстановке этих значений в линейную форму задача
примет вид
х3 > 0, х4 > 0.
Случай 2. а = 2. В этом случае нельзя выразить и х2 через
х3 и х4, но можно исключить одну из этих переменных, например
X, :
Если подставить найденное выражение для в линейную
форму и оставшиеся ограничения, то задача примет вид
1 + х2 - х3 - х4 —> min
Зх> -2*4=0,
х3 > 0,х4 >0.
Полученная задача в канонической форме неразрешима, так
как х2 входит в линейную форму с ненулевым коэффициентом, но
не входит в ограничения. Значит, неразрешима и исходная задача.
►
Математические модели многих важных для практики задач
оптимизации представляют собой задачи линейного программи-
рования.
Пример 3. Составить математическое описание следующей
задачи об оптимальном составе сплава и представить полученную
задачу линейного программирования в каноническом виде.
6
Для приготовления b0 кг сплава с заданными свойствами ис-
пользуют вещества Ар	В х кг вещества Aj содержится а^х
кг химического элемента Bh	Содержание элемента Bi в
сплаве должно заключаться в пределах от p-t до кг. Стоимость 1
кг вещества Л, составляет с7 руб.
Требуется определить такой состав для приготовления сплава,
при котором общая стоимость израсходованных веществ мини-
мальна.
◄ Обозначим Xj количество кг вещества Aj, используемое для
приготовления сплава (очевидно х7 >0,	Тогда содер-
п
жание элемента Д в сплаве составит X кг, а стоимость из-
/=>
п
расходованных веществ будет равна X ОД руб.
j=i
Поэтому, с учетом ограничений на содержание элементов Д в
сплаве, для величин х7- получим следующие неравенства:
л
ajjXj <bbi=1,2,...,m.
j=i
Кроме того, количество сплава должно составлять Ь(/ кг, по-
п
этому X Xj <Ь()
Таким образом, математическое описание задачи об опти-
мальном составе сплава принимает вид
л
f(x)=X ОД”* min,
7=1
п
X ayXj <bj,	(11)
7=1
n
X aijXj > £i,(i=l,...,m),	(12)
7=1
n
X Xj=bo,	(13)
y=i
Xj >0,j=l,...,n.
Запишем эту задачу линейного программирования в канони-
ческом виде.
7
Среди ограничений (11)—(13) на переменные х7 содержится 2 т
неравенств (11), (12). Для преобразования их в ограничения-
равенства введем 2т дополнительных неотрицательных перемен-
ных xn+i и xnim+b
Прибавив переменные xn+i к левым частям соответствующих
неравенств (11) и вычтя переменные из левых частей нера-
венств (12), получим задачу линейного программирования в кано-
ническом виде
п
f(x)= 2L CjXj-* min,
У=«
ayXj+Xn+^bi,
aijXj+xn+HH-i^j, (i=l,...,m),
n
S Xj=b0,
7=1
Xj >0, j=l,...,n.
Задачи
Привести задачи к канонической форме добавлением неотри-
цательных переменных и заменой переменных, не связанных ус-
ловием неотрицательности, разностью двух неотрицательных пе-
ременных.
1.1.
f = ~х{ - х2 -> min
2х. + х, > 1
1	Z.
< Xj - х2 < О
jc15x2 > О
f = -Х| + х2 -> min
8
1.3.
1.4.
f = -х, - x2 - x3 —> min
X, - x3 < 1
< x2 + x3 > 1
x. > 0
f = -Xj +x2 - x3 —> min
X, - x2 = 0
•x2 <1
x3 > 0
1.6.
f = Xj - x2 - 2x3 - 3x4 -> min f - xt - x2 - x3 +1 Ox4 -> max
Xj - x2 + x3 + x4 = 1
-Xj -x4 <5
x2 +x3 >10
Xj + x2 + x3 + x4 = 1
x2 + x3 + x4 = 1
x3 4- X4 =1
Привести задачи к каноническому виду методом исключения
переменных. Проанализировать вопрос о разрешимости задач в
тех случаях, когда невозможно исключить все переменные, не
связанные условием неотрицательности.
f = Xj + х3 -> min
3Xj + х2 < 1
2Xj + х2 < 2
1.8.
f = Xj + ах2 + х3 —> min
х,-Зх2+х3=1
* Xj - Зх2 +х3 = 2
х3 > 0
1.9.
f = х, - х2 - х3 -> max
х, -2х2 +х3 = 1
< Xj - 4х2 + ах3 < 2
Xj > 0
1.10.
f - Xj + х4 -> max
Xj + х2 + х3 + х4 = 1
Xj + х2 + Зх3 + 2х4 < 4
- Xj + х2 + 9х3 + 4х4 -16
х, >0
9
2. Графический метод
решения задачи линейного
программирования
Если задача линейного программирования содержит только
две переменные и в ее условии нет ограничений-равенств (1), то
такую задачу можно исследовать и решить графически.
Рассмотрим задачу'
f(x)=C|Xl+c2x2-* min	(14)
ailx1-+-ai2x2 <bb i=l,...,m,	(15)
X] > 0, х2 >0.	(16)
На плоскости (xJf х2) любое из неравенств (15) определяет по-
луплоскость, лежащую по одну из сторон от прямой ацХ1+ацХ2=Ь1.
Для того чтобы определить расположение этой полуплоскости от-
носительно граничной прямой, можно подставить координаты ка-
кой-либо точки (при Ь, 0 проще всего взять начало координат) в
соответствующее неравенство (15) и проверить его выполнение.
Таким образом, допустимое множество U задачи (15)-(16) яв-
ляется пересечением первого квадранта х{ > 0, х2 > 0 и полуплос-
костей, соответствующих неравенствам (11).
Поэтому множество U представляет собой либо:
а)	пустое множество, тогда задача (14)-(16) не имеет решений
из-за несовместности ограничений (15), (16);
б)	многоугольник (рис. 1);
в)	неограниченное многоугольное множество (рис. 2).
Для решения задачи (14)—(16) в случае U 7^0 рассмотрим се-
мейство линий уровня функции f(x) из (14)
C=const,	(17)
которые являются параллельными прямыми. Антиградиент -
f'(x)=(-c/;-c2)=e перпендикулярен прямым (17) и указывает на-
правление убывания f(x), Если перемещать параллельно самой се-
бе произвольную прямую (17), проходящую через допустимое
множество 17, в направлении е убывания f(x) до тех пор, пока эта
прямая будет иметь хотя бы одну общую точку с множеством 1/,
то в своем крайнем положении указанная прямая пройдет через
10
точку множества U, в которой целевая функция f(x) принимает
минимальное на U значение.
Рис. 1
Рис. 2.
Рис. 3
И
Пример 2. Используя графический метод, найти решение сле-
дующей задачи линейного программирования:
f(x)=-3x 1-2х2~* min
Xj+2x2 < 7,
2Xi+x2 <8
х2 <3
Xj > 0, х2 > 0.
◄ Изобразим на плоскости (х, х2) допустимое множество U
данной задачи (многоугольник ABCDE) и одну из линий уровня -
Зх7-2х2=С целевой функции (рис. 3). Направление убывания f(x)
указывает вектор е=(3;2). Совершая параллельный перенос линии
уровня вдоль направления ё, находим её крайнее положение. В
этом положении прямая -Зх7-2х2=С проходит через вершину D
(3;2) многоугольника ABCDE. Поэтому целевая функция f(x) при-
нимает минимальное значение /* в точке х*=(3;2), причём
/* =/3;2>-13. ►
Задача линейного программирования (14)-(16) может иметь и
бесконечное множество решений.
Пример 3. Решить задачу линейного программирования с це-
левой функцией f(x)=-xi-2x2 и ограничениями на допустимое мно-
жество U, взятыми из примера 2.
Рис. 4
◄ Множество U построено при решении примера 2. На рис. 4
изображена линия уровня -х7-2х2=С целевой функции f(x) В своем
крайнем положении при параллельном переносе вдоль направления
12
ё=(1;2) она содержит сторону CD многоугольника ABCDE. Таким
образом, все точки отрезка CD являются точками минимума функ-
ции fix) на множестве U. Так как концы С и D этого отрезка имеют
координаты (1;3) и (3;2) соответственно, то любая точка минимума
fix) представима в виде х* = a(l,3)+(l-Q!)(3,2)=(3-2Q;2+a), где
ае[0;1]. Минимальное значение целевой функции/* = /(х*)=-7. ►
В случае неограниченного допустимого множества U задача
линейного программирования (14)—(16) может не иметь решения,
так как целевая функция на таком множестве может быть не
ограниченной снизу.
Пример 4. Решить графическим методом задачу линейного
f(x)=-Xi-2x2-> min
Xi+X2 >1,
2xrx2 >-l,
xr2x2 <0,
xj > 0, x2 >0.
◄ Допустимое множество U данной задачи представляет со-
бой неограниченное многоугольное множество (рис. 5). Функция
fix) убывает в направлении е=(1;2). При параллельном переносе
линии уровня -хг2х2=С вдоль направления ё она всегда пересека-
ет множество U, а целевая функция fix) неограниченно убывает.
Поэтому рассмотренная задача не имеет решений. ►
13
Графический метод используется также для решения задачи
линейного программирования в каноническом виде (3)-(5) с про-
извольным числом переменных х7, если число свободных перемен-
ных системы уравнений (4) не превосходит двух.
Пусть ранг г матрицы системы ограничений (4) (т. е. матрицы
А из (6)) равен рангу расширенной матрицы (И|/>) этой системы. В
противном случае система (4) несовместна и задача линейного
программирования (3)-(5) не имеет решения, так как ее допусти-
мое множество U пусто.
Выберем произвольный базисный минор матрицы А. Для оп-
ределенности будем считать, что этот минор порядка г соответст-
вует первым г столбцам и строкам матрицы А. Если г<т, то урав-
нения (4) с номерами	являются следствиями остальных
уравнений и их следует опустить. Поэтому будем считать, что
г=т.
Предположим, что п-т=2 или л-/я=1. Считая переменные х7,
базисными, а остальные - свободными, решим систему
(4), т.е. выразим базисные переменные через свободные, после че-
го исключим базисные переменные из условия задачи (3)-(5). Для
этого полученные соотношения для базисных переменных подста-
вим в выражение (3) целевой функции и запишем условие неотри-
цательности (5) для всех переменных.
В результате получим задачу линейного программирования
вида (14)—(16'), эквивалентную исходной задаче и содержащую
только свободные переменные исходной задачи, а их число не
превосходит двух. Для решения полученной задачи можно ис-
пользовать графический метод.
Пример 5. Используя метод исключения переменных, свести
следующую задачу линейного программирования, заданную в ка-
ноническом виде, к виду, пригодному для применения графиче-
ского метода:
-2xi-x2-3x3-X4-^ min,
Х]+2х2+5хз-Х4=4,
хгх2-х3+2х4=1,
Xj >0, i= 1,2,3,4.
4 В данном случае матрица системы ограничений-равенств
имеет вид:
14
Г 1 2 5-1 I 4 ''
( 1 -1 -I ‘2 |	1/
Ее ранг г = 2, причем минор, образованный третьим и четвёр-
тым столбцами, может быть выбран в качестве базисного. Число
свободных переменных п-т=2, поэтому для решения задачи мож-
но использовать графический метод.
Решим систему ограничений-равенств относительно базисных
переменных х3, х4:
1	2	5-1	|	4	Г-1	1	1
(1-1-12	|	1 J	( 1	2	5
Г 1	1
r-l 1	1	-2	|	‘ ”
< 6 -3	0	9	|	9 )	| -	-1
I 3	3
I -2	|	-1
О 1	|	1
В итоге получим:
Исключая переменные х3 и
х4 из выражения для целевой
функции, находим:
f(x)=-|x1-|x2-4.
С учетом условия неотрицательности х, >0,	и только
что полученных равенств, получаем следующую задачу:
f(x)=-|xr|x2-4-> min,
-xr-x2 < 1.
з з
х3, х4 > 0.
15
Задачи
Решить следующие задачи линейного программирования гра
фически или убедиться в их неразрешимости.
f = -х( - 2х2 —> min
Гхг + х2 < 1
<1
2.2.
f = -Xj - 2x2 —> min
ХрХ2 > 0
2.3.
f = + x2 —> max
Xj + 2x2 < 1
2xj 4- x2 < 1
< Xj - x2 < 1
х, - 2x2 < 1
2xj - x2 < 1
xI5x2 > 0
2.5.
/ = х, + 2x2 —> max
3Xj - 2x2 <6
5 - Xj 4- 2x2 < 4
3xj 4-2x2 < 12
Xj,x2 > 0
2.4.
f - -Xj 4- x2 —> max
Xj 4- x2 < 1
X] - 2x2 < 1
< 2Xj 4- 3x2 <2
3xj 4- 2x2 < 3
Xj 4-x2 > 1/2
Xj,x2 > 0
2.6.
f - -2Xj - x2 -» min
Xj > 0
2.7.
f - 7Xj 4-5x2 min
Xj,x2 > 0
2.8.
f - -Xj 4- 2x2 —> min
2xj - 3x2 > 0
< x, - x2 <3
2X] - x2 =4
16
Используя метод исключения переменных, свести ЗЛП к ви-
ду, пригодному для применения графического метода, и решить
их.
2’л3
2.11.
f = -х1 + х2 + х4 + Зх5 —> min
X] 4- 2х2
- х3 — 5х4 + 2х5 = -5
<	+ х2 4- х3 - 2х4 4- 5х5 = —2
- 2х} 4- х3 4- Зх4 - Зх5 = 6
ху > 0,у = 1...3
2.10.
f = Xj 4- х3 - 7х4 4- х5 —> max
X] - х2 4- 6х4 - 2х5 - -1
< х2 - х3 - 4х4 + 6х5 = 24
Х[ 4- х2 - х3 - Зх4 4- 7х5 - 32
ху > 0,j = 1...5
2.12.
f = х, 4- х2 4- 2х3 - 9х4 —> max
2х, - х2 4- х3 - 4х4 < 6
X] 4- 2х2 - х3 4- 7х4 = 5
<
5х, 4- х2 - Зх4 = 11
Зх, + 2х2 4- х3 - Зх4 = 7
Xj, >0,у = 1...4
3. Симплекс-метод решения задачи
линейного программирования
Общим методом решения произвольной задачи линейного
программирования является симплекс-метод, рассматриваемый
ниже.
Пусть ранг г матрицы А-(а-,^ системы ограничений-равенств (4)
задачи линейного программирования в каноническом виде совпа-
дает с рангом расширенной матрицы (А\Ь).
Выберем какой-нибудь базисный минор матрицы А. Для опреде-
ленности будем считать, что он соответствует первым г столбцам
и строкам этой матрицы. Если г<т, то уравнения с номерами
i=r+l,...,m, являющиеся следствиями остальных уравнений систе-
мы, отбросим, полагая в дальнейшем г=т.
17
Для решения системы уравнений (4) относительно базисных
переменных Xj,	с помощью эквивалентных преобразова-
ний приведём её к виду
Х,+
Х2+	<АданХ<п+1+-„+ О|0,2,пХ„=/3(0 2,
(18)
Хщ^ И m^n+lXm+l"^* • О: m.nXn-/? т,
тогда общее решение системы (4) запишется следующим образом:
X|=	С/О)ЬПХП,
\2~	2"°^° 2,m-+lXm+]-...- с/°'2!ПХп,
(19)
т-^ т,т+1Хт+1_.• “ с/ т,пХп,
где свободные переменные хт±],...,хп могут принимать произволь-
ные значения.
Положив их равными нулю, получим частное решение
h %2~$ 2у“у $ ту^т+1 Хт+2 ••• %п~@
или
х(°ЧЛ Л;...; Л; 0;0;...;0),	(20)
которое назовем базисным решением системы (4). Каждому выбо-
ру базисных переменных соответствует свое базисное решение
системы (4).
Если все компоненты базисного решения (20) удовлетворяют
условию неотрицательности, т. е. если /3^,>0,	то такое
решение называют допустимым базисным решением системы (4)
или угловой точкой допустимого множества U задачи линейного
программирования (3)-(5). Если среди неотрицательных чисел
в (20) есть равные нулю, то допустимое базисное решение называ-
ется вырожденным (вырожденной угловой точкой), а соответст-
вующая задача линейного программирования также называется
вырожденной.
В основе симплекс-метода лежит следующий факт:
Если задача линейного программирования (3)-(5) разрешима,
то минимум целевой функции f(x) из (3) достигается хотя бы в од-
ной из угловых точек допустимого множества U этой задачи.
Так как различные базисные решения системы (4) соответст-
вуют различным вариантам выбора т базисных из общего числа п
переменных х7? то число допустимых базисных решений (угловых
18
точек) не превышает с;. Поэтому задачу линейного программиро-
вания можно решать посредством перебора конечного числа угло-
вых точек допустимого множества U, сравнивая значения целевой
функции в этих точках. Однако при большой размерности п зада-
чи линейного программирования этот подход затруднителен. Идея
симплекс-метода состоит в направленном переборе угловых точек
допустимого множества U с последовательным уменьшением зна-
чения целевой функции f(x).
Описание симплекс-метода
Предположим, что задача линейного программирования (3)-
(5) является невырожденной, а базисное решение (20) - допусти-
мым.
Используя соотношение (19), выразим целевую функцию из
(3) через свободные переменныех7? j=m+l
п
/(х)=р‘”+Ър™х1.	(21)
где
XW=SCX’	, j=m+l,...,n.
/=1	г=1
Справедливы следующие утверждения:
а)	Если в выражении (19) все коэффициенты pjo>, j=m+l,...,n
неотрицательны, то в угловой точке (18) достигается минимум
целевой функции f(x) из (3) на допустимом множестве U задачи
(3)-(5), и этот минимум равен р^.
б)	Если среди отрицательных коэффициентов p^,j #0 из (19)
есть такой (например р™), что в (16) все коэффициенты о$> <0,
i=l,...,m, то целевая функция f(x) не ограничена снизу на допус-
тимом множестве U и задача (3)—(5) не имеет решений.
в)	Если хотя бы один из коэффициентов p^,j тЮ в (19) отри-
цателен (например, р^}<0) и при этом среди коэффициентов а^в
(16) есть хотя бы один положительный, то существует угловая
точка х<!) множества U такая, что f(x!))< f(xf0>).
В случаях а) и б) процесс решения задачи линейного про-
граммирования на этом заканчивается. Рассмотрим подробнее
19
случай в). Пусть в (19) коэффициент pjo)< 0 и в (16) имеются по-
ложительные коэффициенты off'. Найдем номер к базисной пере-
менной из условия
где минимум берется по всем номерам	для которых
а™>0.
Найдем решение системы (4), считая свободными переменные
хт+],Xk, xi+1,..., хП9 т.е., поменяв местами свободную пере-
менную х- с базисной переменной х^ система уравнений вида (16)
в этом случае запишется следующим образом:
п	/у(0)	ЛУ(О)
V	к -	л'°>
Xj+ ZL ап	(0))xj	(0) хк=р^-а^Щ-^ I=l,...,m, 1 #k,
j=m+!	aki	a},1
(23)
V + 1
Xi+ L wx/+ wxk=U-, i=k.	(24)
j=m+lWJW	<Xki	a<t/>
j*l
Зависимость целевой функции от новых свободных перемен-
ных примет вид:
л	а(0)	п(0)
Z,„(0) „(0) */	Pl	Q<0)
(^/ Pi ^xj	+	(25)
/=ж+1	Ukl	tty'
/*/
Компоненты нового базисного решения x(h можно найти, при-
равняв нулю свободные переменные ху, j=m+l, j и х* и найдя
при этом условии значения базисных переменных из (23)-(24). Ба-
зисное решение х(1) является допустимым, т.е. угловой точкой
множества U, причем f(x(r,)<f(x(0)).
По знакам коэффициентов в системе (23) и выражении для
целевой функции (25) можно сделать одно из трех приведенных
выше заключений, как это было сделано для угловой точки х'0). В
случае в) следует совершить переход к очередной угловой точке
х(2>, аналогичный переходу от х('°[к х(!>, и т.д.
Так как число угловых точек допустимого множества U не
превышает С", то случай в) может повторяться конечное число
раз, т.е. в результате конечного числа шагов перехода к новой уг-
20
ловой точке будет либо найдено решение задачи, либо сделано за-
ключение о том, что она не имеет решений.
Реализация описанного выше симплекс-метода значительно
упрощается при использовании симплекс-таблиц. Записав коэф-
фициенты уравнений (18) и целевой функции (21) соответствую-
щим образом (см. таблицу 1), получим симплекс-таблицу задачи
(3)-(5) для угловой точки х0) из (20).
Рассмотрим переход от симплекс-таблицы, соответствующей уг-
ловой точке xlOj, к симплекс-таблице для угловой точки х(>-.
7^	Хщ+1	... Xi			Xn	
Х1	“1.Л1+1					Д01
Хк	а(0)	...			«s	
Хгг.	ат ,	• • •		...	c	№
	Pm+l	...		...	p™	-p?
Таблица 1	Таблица 2
	Xm+1	... Xk	• • • Xn	
Xl	ы1л>+1	...	... «s	д<’>
		...	• ••	...
Xl	a(1)	... «s	...	/Г
	...	•..		• • •
Xm	a(,) ,	...	... <	№
	»<•) Jr m+l		... p?	-p™
Пусть номера к и I определены так, как это сделано выше.
Элемент а также строка и столбец таблицы 1, на пересечении
которых он стоит, называются разрешающими, или опорными.
Из формул (23)-(25) следует, что преобразование исходной сим-
плекс-таблицы с опорным элементом ctf (см. таблицу 1) приводит
к новой симплекс-таблице (таблица 2), для определения элементов
которой необходимо выполнить следующие операции:
1.	Поменять местами переменные хк и хь остальные перемен-
ные оставить на прежних местах (см. таблицу 2).
2.	На место опорного элемента поставить число
ак!
3.	На остальных местах разрешающей строки записать соот-
ветствующие элементы исходной таблицы, деленные на опорный
элемент.
21
4.	На свободные места разрешающего столбца поставить со
знаком минус соответствующие элементы исходной таблицы, делен-
ные на опорный элемент.
5.	Оставшиеся свободные места в новой симплекс-таблице за-
полнить построчно следующим образом: из строки элементов ис-
ходной таблицы вычесть произведение ее элемента из разрешаю-
щего столбца на уже заполненную разрешающую строку новой
таблицы. Например, для строки с i-й базисной переменной имеем
(знак * стоит на месте элемента разрешающего столбца, заполнен-
ного согласно определению операции 4):
(<t,,..-Л.-.,aS,,/?r)-
-Л-.
Замечание. Если задача линейного программирования (3)-(5)
вырождена, то возможны холостые шаги симплекс-метода, т.е.
шаги, в результате которых значение целевой функции не изменя-
ется. При этом теоретически возможно и зацикливание, т.е. беско-
нечное повторение холостых шагов. Для того чтобы избежать за-
цикливания, разработаны специальные алгоритмы (антициклины),
Однако на практике зацикливание происходит крайне редко, по-
этому антициклины мы здесь не рассматриваем.
Пример 5» Решить задачу линейного программирования сим-
плекс-методом, используя в качестве начальной угловой точки ?0)
базисное решение, соответствующее свободным переменным и
х2-
-2х]-х2-Зхз-Х4-* min
х14-2х2+5х3-Х4=4
Х|-Х2-Х3+2Х4=1
Xj >0, i= 1,2,3,4.
◄ Столбцы с номерами 3 и 4 матрицы А системы ограниче-
ний-равенств данной задачи образуют базисный минор. С помо-
щью эквивалентных преобразований приводим эту систему к виду
(18), где базисными являются переменные х3 и х4\
Хз+ jX]+|x2=l	(*)
Хд+ |хг|х2=1
Полагая в равенствах (26) свободные переменные х} и х2 рав-
ными нулю, находим х3-1, х/=1, т.е. базисное решение х(0)=(0,0,1,1).
22
Так как все базисные переменные в х(0) положительны, данное ба-
зисное решение является допустимым (т.е. угловой точкой) и не-
вырожденным.
Исключив с помощью (*) базисные переменные в выражении
для целевой функции, получим
f(x)=-lxrlx2-4.	(**)
С помощью равенств (*) и (**) составляем симплекс-таблицу,
соответствующую угловой точке х(0)\
х(<”	Х1			Х2	
Хз	1 3			1 3	1
х4		2 3		3	1
	_1 3			"з	4
Среди коэффициентов pjo),y ^0, из (19) есть отрицательные
— это элементы -|и в последней строке симплекс-таблицы.
Следовательно, угловая точка х(0' не является решением задачи.
Для каждого из отрицательных элементов р'°' среди соответ-
ствующих коэффициентов а'” из (16) (т.е. элементов симплекс-
таблицы, стоящих в том же столбце, что и р'01) есть положитель-
ные, значит возможен переход к новой угловой точке х(,) с мень-
шим значением f(x).
Найдем разрешающий элемент. В качестве опорного можно
взять любой из столбцов таблицы, соответствующих свободным
переменным х3 и х4. Выберем, например, столбец при свободной
переменной х3.
Разрешающую строку находим в соответствии с (22): так как
= то разрешающей является строка, соответствую-
щая базисной переменной х4. Итак, опорный элемент найден, в
симплекс-таблице он обведен рамкой.
23
Заполнив новую симплекс-таблицу по правилам, описанным
выше, получим:
Отметим, что значение f(x) в новой угловой точке уменьши-
лось по сравнению со значением в исходной: -| вместо -4 (см.
элементы в правых нижних углах симплекс-таблиц).
В нижней строке последней таблицы есть отрицательный эле-
мент -р стоящий в столбце при свободной переменной х2. Кроме
того, в этом столбце имеются положительные элементы, поэтому
возможно дальнейшее уменьшение f(x) с помощью очередного
шага симплекс-метода.
На данном шаге выбор опорного столбца однозначен и опре-
деляется отрицательным элементом последней строки. Разре-
шающая строка также находится однозначно. Это строка при ба-
зисной переменной х3. Опорный элемент в последней таблице об-
веден рамкой.
Как и на предыдущем шаге, находим очередную симплекс-
таблицу по общим правилам:
х(2)	Хд	х3	
Х2	-1	2	1
Х1	1	1	2
	0	1	5
В этой симплекс-таблице оба коэффициента в последней
строке положительны. Поэтому угловая точка, соответствующая
24
свободным переменным х3 и х4, является точкой минимума целе-
вой функции f(x): х*=х(2>=(2,1,0,0). Минимальное значение f(x) со
знаком минус записано в правом нижнем углу симплекс-таблицы,
поэтому/=-5.	►
	Задачи
Решить ЗЛП симплекс-методом, используя х(0)в качестве на-
чальной угловой точки.
3.1. f - -Xj + 2х2 -х3 —> min	3.2. f = -X] - х2 - х3 min
fxj + 4х2 + х3 = 5 [xj -2х2 -х3 = -1	[- Х| + х2 + х3 =2 [3xj - х2 + х3 = 0
Xj > 0, j ~ 1...3 х(0) = (1;1;0)	х7 >о,у = 1...з х(0) = (0;1;1)
3.3. f = -2xj - х2 + Зх3 + х4 —) х, + 2х2 + 5х3 - х4 =4 < х, -х2 -х3 + 2х4 = 1 х.>о,; = 1...4 х(0) = (0;0;1;1)	3.4. ► min f = - 6xj - х2 - 4х3 - 5х4 -» min 3xj + х2 - х3 + х4 =4 5х1 + х2 + х3 - х4 = 4 ху >0,7 = 1...4 х(0) = (1;0;0;1)
3.5. f = -Xj - 2х2 - Зх3 + х4 —з [х] - Зх2 - х3 - 2х4 = -4 [Xj - х2 + х3 = 0	3.6. ► min f = -xt + Зх2 + 5х3 + х4 -> min х, + 4х2 + 4х3 + х4 = 5 |Xj + 7х2 + 8х3 + 2х4 = 9
xj >0,7 = 1...4 х(0> = (0;1;1;0)	Xj >0,7 = 1...4 х(0) = (1;0;1;0)
25
3.8.
f - -Xj - x2 - x3 - x4 —> min f = -Xj - 2x2 + x3 - x4 —> min
I Xj 4- 3x7 + x3 + 2x4 = 5
12Xj - x3 + x4 - 1
xy.>0J = 1...4
xm = (O;l;O;l)
;>0,j = 1...4
xm = (O;O;l;l)
3.9.
3.10.
f - -x, - x2 - x3 - x4 - x5 —> min
f2x, + 3x2 + 5x3 + 7x4 4- 9x5 =19
[Xj - x2 + x4 + 2x5 = 2
Xj. >0,7 = 1...5
xm = (l;0;l;2;0)
f = x, 4- 3x2 + 2x3 + 4x4 - 2x5 —> min
- %] + x3 - 2x4 - 2xs = -2
x2 - x3 4- x4 - 2x5 =0
2x, 4- x, 4- 5x4 4- xs =7
х^ > 0,7 = 1...5
x(0) = (3;l;l;0;0)
3.11.	3.12.
f = 3x, - 2x2 4- x3 4- 3x4 4- 3x5 —> max
f = 2xj -x2 -x34-x4 -4x5 -x6 -> min f2xl -x2 4-x3 +x4 4-x5 = 2
3x{ +x2 4-2х3 4-6x4 4-9xs +3x6 = 15	<{-4xt 4-3x2 -x3 -x4 -3x5 = -4
л + 2л, - x, + 2x„ + Зл5 + x6 = 5	[Зл, + 2л, + +3л, + 5x4 = 3
xj 0, j1...6
xl0) = 1;0;0;0;0;4)	xW = (1;0;0;0;0)
4. Метод искусственного базиса
Решение задачи линейного программирования симплекс-
методом начинается с поиска какой-либо угловой точки хт) допус-
тимого множества G этой задачи.
Метод искусственного базиса нахождения начальной угловой
точки х(0/ состоит в следующем. Пусть в ограничениях задачи ли-
26
нейного программирования (3)-<5) все b-t >0,	Если это
не так, то умножим соответствующие уравнения (4) на -1. Введем
т дополнительных переменных xn+h	и рассмотрим вспо-
могательную задачу линейного программирования
т
f(x)=S хп+1-> min,	(26)
7=1
п
Е aijXj+xn+i=bi,i=l,...,m;	(27)
;=1
хк >0, к= 1,...,n+m.	(28)
Одной из угловых точек допустимого множества G этой зада-
чи, очевидно, является точка х(0,=(0;...;0;/?7;...;^). Поэтом}7 для ре-
шения задачи (26)-(28) можно использовать симплекс-метод со
следующей начальной симплекс-таблицей:_______________________
	Х[	*2	хп	
Хп+1	ап	312	—	31 п	bi
Хп+2	a2i	а22	—	а2п	ь2
•..	♦ • •	• ♦ •	♦ ♦ • • • •	. *«
Xn-m	ami	ащ2	• ••	amn	Ьт
	Pl	Р2	Рп	-Ра
щ	гп
rAepj=-Xav;j=l,...,n;-pO=-E^ 
;=i	i=i
Отметим, что решение задачи (24)-(26) всегда существует, так
как ее допустимое множество G непусто (?(С|е(7), а целевая функ-
ция (26) ограничена снизу на G (f (л-)>о).
Пусть 7*=min /(х). Рассмотрим возможные случаи.
G
1. f‘>Q. Тогда допустимое множество G исходной задачи ли-
нейного программирования (3)—(5) пусто, т.е. эта задача не имеет
решений.
2. 7‘=0 и минимум целевой функции 7U) достигается в угло-
вой точке
xw =(^,.-,Х,.ля+1,-Л+Л)	(29)
допустимого множества G вспомогательной задачи. Тогда
х(0)=(х„х2,..^)	(30)
27
есть угловая точка допустимого множества U исходной задачи
(3)-(5) и ее можно использовать в качестве начальной угловой
точки при решении этой задачи симплекс-методом.
Из (24) видно, что равенство f (х)=/*=0 возможно только то-
гда, когда все координаты xn+i,	(29) равны нулю.
Если задача (26)-(28) невырождена, то это означает, что все
переменные хпЧ для угловой точки (29) являются свободными.
Опустим столбцы, соответствующие этим переменным в оконча-
тельной симплекс-таблице, составленной при решении задачи
(26)-(28). Полученная в результате этого таблица будет соответст-
вовать системе уравнений (4), разрешенной относительно т пере-
менных X/, являющихся базисными для угловой точки (29). По-
этому остается заменить в этой таблице последнюю строку на
строку коэффициентов целевой функции (3) исходной задачи и
продолжить ес решение симплекс-методом из начальной угловой
точки (30).
Если вспомогательная задача (26)-(28) вырождена, то в угло-
вой точке (29) некоторые из переменных xn+i,	могут ока-
заться базисными. Тогда эти переменные следует перевести в сво-
бодные с помощью холостых шагов симплекс-метода, выбирая в
качестве разрешающих произвольные элементы симплекс-таблиц,
отличные от нуля. После этого исходная задача (3)-(5) решается
симплекс-методом так, как описано выше.
Пример 6. Методом искусственного базиса найти какую-либо
угловую точку допустимого множества задачи линейного про-
граммирования, рассмотренной в примере 5, и записать соответст-
вующую этой угловой точке симплекс-таблицу.
◄ Введем дополнительные переменные х5, х6 и запишем ус-
ловие вспомогательной задачи линейного программирования (26)—
(28) для рассматриваемого случая:
f {х)=х5+х^ min
х1+2х2+5хз-х4+х5=4
Х1-Х2-Хз+2х4-гХ6=1
Xi >0, i=l,...,6.
Считая дополнительные переменные х5, х6 базисными, запи-
шем симплекс-таблицу этой задачи, соответствующую угловой
точке х(°’=(0;0;0;0;4;1). Затем, производя преобразования сим-
28
плекс-метода, получим такую последовательность симплекс-
таблиц (рамками обведены разрешающие элементы):
~(0>	Х1	х2	Хз	х4	х"’	\Хб 1	х2	хз	х4	
х5	1	2	5	-I	4	х5		Е	6	-3	3
Хб	0	-1	-1	2	1	X)		-1	-1	2	1
	-2	-1	-4	0	4	/2\	-3	-6	3	3
Столбец симплекс-таблицы, соответствующий вспомогатель-
ной переменной xn+h вводимой в свободные на каждом шаге мето-
да искусственного базиса, удобнее вычеркивать на данном шаге
вместо того, чтобы исключать такие столбцы одновременно в
окончательной симплекс-таблице.
В нижней строке последней симплекс-таблицы нет отрица-
тельных элементов, а в правом нижнем углу стоит нуль. Следова-
тельно, минимум /*=0 вспомогательной целевой функции достиг-
нут и х<0)=(2,1,0,0) есть угловая точка допустимого множества U
исходной задачи линейного программирования из примера 5.
Заменив нижнюю строку последней симплекс-таблицы на
строку коэффициентов целевой функции исходной задачи, полу-
чим симплекс-таблицу этой задачи, соответствующую найденной
угловой точке х(0>:
jf(2)	х3	Хд	
х2	2	-1	1
Х1	1	1	2
	1	0	5
29
В данном случае найденная угловая точка совпала с решением
исходной задачи. Другие варианты выбора разрешающих элемен-
тов в ходе реализации метода искусственного базиса могли при-
вести к другим угловым точкам допустимого множества U исход-
ной задачи.
Задачи
Решить ЗЛП симплекс-методом, находя начальную точку' ме-
тодом искусственного базиса.
 » X • f = -Xj - 4х2 - х3 —> min | Xj - х2 + х3 =3 [2xj - 5х2 - х3 = 0 ху >0,j = 1...3 4.3. f = -Xj - 2х2 - Зх3 4- 4х4 —> [ х, 4- х2 - х3 + х4 - 2 1 + 14х2 4-10х3 -10х4 = 24 х; > 0,/= 1...4 4.5. f = -Xj 4- 5х2 4- х3 - х4 —> Т Xj 4- Зх2 4- Зх3 + х4 = 3 2xj 4-Зх3 -х4 =4 ху >0,/ = 1...4	f = -Xj 4-10х2 - х3 —> min -х, 4- 5х2 + 7х3 = 13 < х, 4-14,5х2 4- 7х3 = 15 Xj >0,у = 1...3 4.4. mm f = -Xj 4-4х2 -Зх3 -10х4 —> min Xj 4- х2 - х3 4- х4 - 0 Xj 4- 14х2 4-10х3 — 10х4 = 11 ху > 0,j = 1...4 4.6. f = -л, - 10х2 4- х3 — 5х4	min nin г _ э	- Xj + 2х2 - х3 - х4 = 1 < - X] 4- 2х2 4- Зх3 4- х4 = 2 Xj 4- 5х2 + х3 - х4 = 5 xy>0J = 1...4
30
4.7.
f = -2xj + 2x2 + x, + 2x4 - 3x5 -> max
- 2x, + x, - x3 - x4 = 1
- X] -x2 + 2x3 + x4 + x5 = 4
- x, + x2 - xs = 4
x; >0,y = 1...5
4.9.
2xt 4- x2 + x3 + x4 - x5 = 3
< x, - x2 + x4 + x5 = 1
- 2x, - x2 - x3 + x4 = ]
Xj >O,J = 1...5
f = -5x, - 4x2 - 3x3 - 2x4 + 3x5 min
4.8.
f = 5Xj - 2x2 + 2x3 - 4x4 + x5 + 2x6 -> max
2x, - x2 + x3 - 2x4 + x5 + x6 = 1
5 - 3x, + x2 + x4 - x5 + x6 = 2
[- 5X] + x, - 2x3 + x4 - x6 = 3
x?. > 0,7 = 1...6
4.10.
f = 2x, + x2 -x3 + 3x4 -2x5 -> min
(8X] + 2x, + 3x3 + 9x4 + 9x5 = 30
< 5x, + x2 + 2x3 + 5x4 + 6x5 = 19
[x! +x2+ 3x4 = 3
Xj >0,7=1.. .5
Литература
1. Заславский Ю.Л. Сборник задач по линейному программи-
рованию. - М.: Наука, 1969.
2. Сборник задач по математике для втузов. Ч. 4: Методы оп-
тимизации. Уравнения в частных производных. Интегральные
уравнения : учеб, пособие / под ред. А.В. Ефимова. - М.: Наука,
1990.
31
Оглавление
1.	Постановки задач линейного программирования__________з
2.	Задачи__._______________________________________________л
3.	Графический метод решения задачи линейного
программирования----------------------------------------ю
4.	Симплекс-метод решения задачи линейного программирования
.................................................	17
5.	Метод искусственного базиса......_..........  —....26
Литература________—-------------------------------------з i
Учебное издание
Методы оптимизации
Методические указания
Составитель Легкое Николай Васильевич
Редактор, корректор И.В. Бунакова
Компьютерная верстка Е.Л. Шелеховой
Подписано в печать 23.06.2008 г. Формат 60x84/16.
Бумага тип. Уел. печ. л. 1,86. Уч.-изд. л. 1,53.
Тираж 150 экз. Зака-
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрГУ.
Отпечатано на ризографе.
Ярославский государственный университет.
150000 Ярославль, ул. Советская, 14.
32