Линейная алгебра. Часть II. Линейное программирование, динамическое программирование и теория игр: Учебно-методическое пособие

Федеральное агентство по образованию 
Российская экономическая академия имени Г. В. Плеханова 
 
 
 
Сагитов Р.В., Шершнев В.Г. 
 
 
 
 
 
 
 
 
 
ЛИНЕЙНАЯ АЛГЕБРА   
Часть II. Линейное программирование,  
динамическое программирование и теория игр 
 
 
Учебно-методическое пособие  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва 2007 
 

ББК 22.1 
 
 
 
 
 
 
 
 
 
Сагитов Р. В., Шершнев В.Г. 
 
Линейная алгебра. Часть II. Линейное  программирование,  динамическое 
программирование и теория игр.  Учебно-методическое пособие. −М.: Издательство «Менеджер», 2007 – 192 с. 
 
 
 
 
 Излагаются основные разделы курса линейного программирования: 
графический и симплексный методы, теоремы двойственности, двойственный симплексный метод, метод потенциалов решения транспортных задач, 
метод Р.Е.Гомори решения задач целочисленного программирования. Также 
излагаются задачи динамического программирования и теории игр. Разбираются примеры решения каждого типа задач и приводятся задания для самостоятельного решения с ответами. Приводятся задания для контроля знаний. 
Пособие соответствует программе по линейной алгебре для студентов, обучающихся по направлению 080100.62  «Экономика». 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
© Р.В. Сагитов, В.Г. Шершнев, 2007 
 

ОГЛАВЛЕНИЕ 
    Введение……………………………………………………………………   5 
1. Математические  модели задач  линейного программирования ……….   6 
   1.1. Математические модели задач  математического программирования ……………………………………………………………………………..
 
  6 
   1.2. Примеры составления математических  моделей задач линейного 
программирования …………………………………………………………...   7 
   1.3. Каноническая форма задачи линейного программирования …...…..   8 
   1.4. Приведение общей задачи линейного программирования к канонической форме ………………………………………………………………   9 
   1.5. Задания для самостоятельного решения  ……………………………  13 
2. Графический метод решения задач линейного программирования ……  14 
   2.1. Задача с двумя переменными …………………………………………  14 
   2.2. Графический метод решения задач линейного программирования с 
n  переменными ……………………………………………………………..  20 
   2.3 Задания для самостоятельного решения ……………………………..  22 
3. Свойства  решений задач линейного программирования ……………..  26 
   3.1.  Многоугольники  и  многогранники ………………………………..  26 
   3.2. Теорема о виде области допустимых решений задачи линейного 
программирования ………………………………………………………….. 
 
 28 
   3.3. Теорема об экстремуме целевой функции …………………………..  29 
   3.4. Опорное решение задачи линейного программирования, его  взаимосвязь с угловыми  точками ……………………………………………….
 
 30 
4. Симплексный метод решения задач  линейного программирования ….  33 
   4.1. Нахождение начального опорного решения и переход к новому 
опорному решению …………………………………………………………..  33 
   4.2. Преобразование целевой функции при переходе от одного опорного   решения к другому ……………………………………………………..  36 
   4.3. Улучшение опорного решения ……………………………………….  38 
   4.4. Алгоритм  симплексного  метода  решения  задач линейного  программирования ……………………………………………………………….
 
 40 
   4.5. Метод  искусственного  базиса ………………………………………  45 
   4.6. Особенности  алгоритма  метода  искусственного  базиса ………..  49 
    4.7. Задания для самостоятельного решения ……………………………  56 
5. Теория двойственности……………………………………………………  61 
   5.1. Составление  математической модели двойственной  задачи ……..  61 
   5.2. Первая теорема двойственности………………………………………  64 
   5.3. Вторая теорема двойственности………………………………………  71 
   5.4. Двойственный симплексный метод (метод последовательного 
уточнения оценок)……………………………………………………………
 
 78 
   5.5. Алгоритм двойственного симплексного метода решения задач  
линейного программирования……………………………………………… 
 
 81 
   5.6. Постоптимальный   анализ……………………………………………  86 
   5.7. Задания для самостоятельного решения ……………………………  94 
6. Транспортная задача линейного программирования …..........................  97 

6.1. Текстовая формулировка транспортной задачи…………………….  97 
   6.2. Математическая модель транспортной задачи………………………  98 
   6.3. Необходимые и достаточные условия разрешимости транспортной 
задачи …………………………………………………………………………
 
101
   6.4. Свойство системы ограничений транспортной задачи……………... 102
   6.5. Опорное решение транспортной задачи…………………………….. 104
   6.6. Методы построения  начального  опорного  решения……………… 106
   6.7. Переход от одного опорного решения к другому…………………… 111
   6.8. Распределительный метод…………………………………………….. 112
   6.9. Метод потенциалов…………………………………………………… 116
   6.10. Особенности решения транспортных задач с неправильным балансом………………………………………………………………………… 117
   6.11.  Алгоритм  решения  транспортной  задачи методом потенциалов…………………………………………………………………………….. 119
   6.12. Транспортная задача с ограничениями на пропускную способность………………………………………………………………………….. 125
   6.13.  Транспортная  задача  по  критерию  времени……………………. 129
   6.14.  Применение транспортной задачи для решения экономических 
задач………………………………………………………………………….. 132
   6.15.  Задания для самостоятельного решения…………………………… 133
7. Метод Гомори решения задач  целочисленного программирования …. 136
   7.1. Задания для самостоятельного решения ……………………………. 139
8. Задачи динамического программирования……………………………… 140
    8.1. Задача о распределении ресурсов……………………………………. 140
    8.2. Примеры  задач  распределения  ресурсов  для  самостоятельного 
решения………………………………………………………………………..
 
146
9. Введение в математическую теорию игр………………………………… 147
    9.1. Основные понятия теории игр……………………………………….. 147
    9.2. Матричные игры……………………………………………………… 147
    9.3. Чистые и смешанные стратегии. Функция игры  в смешанных 
стратегиях……………………………………………………………………..
 
151
    9.4. Функция гарантированного выигрыша и проигрыша игроков. Оптимальные смешанные стратегии игроков и цена игры………………….. 
 
153
    9.5. Приведение матричной игры к паре двойственных задач  линейного  программирования……………………………………………………..
 
156
    9.6. Основная теорема матричных игр (теорема Дж. фон  Неймана –
Моргенштерна)………………………………………………………………..
 
157
    9.7. Методы вычисления оптимальных стратегий………………………. 158
    9.7.1. Случай седловой точки…………………………………………….. 158
    9.7.2. Графический способ……………………………………………….. 158
    9.7.3. Доминирование……………………………………………………... 161
    9.7.4. Решение матричных игр сведением к паре двойственных задач 
линейного программирования……………………………………………….
 
163
    9.7.5.  Приближенный  метод  решения  матричных  игр или  метод 
фиктивного разыгрывания  Брауна-Робинсона……………………………..
 
166

9.8. Задания для самостоятельного решения…………………………….. 168
10. Контрольные задания …………………………………………………… 169
11. Ответы. …………………………………………………………………… 188
Список литературы…………………………………………………………... 191
 
 
 
 
 
 
Введение 
Математическим программированием  называется раздел математики, 
занимающийся методами решения экономических задач, связанных с нахождением экстремумов функций при наличии ограничений на переменные. Отличие методов математического программирования от известных методов 
математического анализа обусловлено своеобразием целевых функций и областей их определения. 
Методами математического  программирования решаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, 
транспортные задачи и т.п. 
Математическое программирование возникло в 30-40-ые годы,  оформилось в самостоятельную науку в 50-60-ые годы ХХ века. Основной вклад в 
становление данного раздела математики внесли американские учёные. Один 
из основных методов математического программирования – симплексный 
метод был опубликован Дж. Данцигом в 1947 году. 
Математическое программирование имеет ряд разделов: линейное, нелинейное, динамическое, выпуклое, стохастическое программирование, теория 
игр и др. 
Данный раздел математики получил название программирование в связи 
с тем, что в результате решения рассматриваемых задач составляется программа – порядок действий решения задач.  
Основой учебного пособия явились лекции, читаемые авторами в Российской экономической академии им. Г.В. Плеханова. Данное учебное пособие 
содержит ряд разделов линейного программирования, основы динамического 
программирования и теории игр.  
 
 
 
 
 
 
 

1. Математические  модели 
задач  линейного программирования 
 
1.1. Математические модели задач математического 
программирования 
 
Основой для решения экономических задач являются математические 
модели.  
Математической  моделью  
задачи называется совокупность математических соотношений, описывающих суть задачи. 
Составление математической модели включает: 1) выбор переменных задачи; 2) составление системы ограничений; 3) выбор целевой функции. 
Переменными задачи называются величины 
n
x
x
x
 , . . . ,
 ,
2
1
, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора X = (
n
x
x
x
 , . . . ,
, 
2
1
). 
Системой ограничений задачи называют совокупность уравнений и неравенств, описывающих ограниченность ресурсов в рассматриваемой задаче. 
Целевой функцией задачи называют функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти. 
Общая задача математического программирования формулируется следующим образом: найти переменные X = (
n
x
x
x
 , . . . ,
, 
2
1
), обеспечивающие 
экстремум целевой функции  задачи 
(min)
 
max
)
 , . . . ,
 ,
(
)
(
2
1
→
=
n
x
x
x
f
X
Z
                     (1.1) 
и удовлетворяющие системе ограничений 

⎩⎨⎧
+
+
=
≤
ϕ
=
=
ϕ
.
 , . . . ,2
 ,1
   
,0 
)
 , . . . ,
 ,
(
, , . . . ,2 ,1
   
,0
)
 , . . . ,
 ,
(

2
1
2
1
m
l
l
i
x
x
x
l
i
x
x
x

n
i
n
i
            (1.2) 

Задача математического программирования называется задачей линейного программирования, если все функции, входящие в математическую модель (1.1), (1.2), линейные. 
 
В общем случае задача линейного программирования может быть записана в таком виде: 
 
(min)
 
max
 
  
...
  
         
)
(
2
2
1
1
→
+
+
+
=
n
nx
c
x
c
x
c
X
Z
,                    (1.3) 

⎪
⎪

⎩

⎪
⎪

⎨

⎧

≤
+
+
+

≤
+
+
+
=
+
+
+

=
+
+
+

+
+
+
+

,
   
. . .  
        
.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
,
 . . . 
,
   
. . .  
 
          
    
.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
,
  . . .
   
          

2
2
1
1

1
)1
(
2
2
)1
(
1
1)1
(
2
2
1
1

1
1
2
12
1
11

m
n
mn
m
m

l
n
n
l
l
l
l
n
ln
l
l

n
n

b
x
a
x
a
x
a

b
x
a
x
a
x
a
b
x
a
x
a
x
a

b
x
a
x
a
x
a

                     (1.4) 

n
t
t
j
x j
≤
=
≥
  ; , . . . ,2 ,1
  ,0
.                                 (1.5) 
Данная запись означает следующее: найти экстремум целевой функции 
(1.3) и соответствующие ему переменные X = (
n
x
x
x
 , . . . ,
, 
2
1
) при условии, 
что эти переменные удовлетворяют системе ограничений (1.4) и условиям 
неотрицательности  переменных(1.5). 

Допустимым решением (планом) задачи линейного программирования 
называется любой  n-мерный вектор X = (
n
x
x
x
 , . . . ,
, 
2
1
), удовлетворяющий 
системе ограничений и условиям неотрицательности.  
Множество допустимых решений (планов) задачи образует область  допустимых решений (ОДР). 
Оптимальным  решением  (планом)  задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума. 
 
1.2. Примеры составления математических  моделей  
задач линейного программирования 
 
Задача использования  ресурсов (сырья).  Для изготовления n видов 
продукции  используется   m  видов ресурсов (сырья). Известны: 
ib  (i = 1, 2, 
..., m) – запасы каждого i-го вида ресурса (сырья); aij, (i = 1, 2, ..., m;  j = 1, 2, 

3, ..., n) − затраты каждого i-го вида ресурса (сырья) на производство единицы объёма  j-го вида продукции; 
j
с  (j = 1, 2, 3, ..., n) − прибыль от реализации 
единицы объёма j-го вида  продукции. Требуется составить план производства продукции, который обеспечивает максимум прибыли при заданных ограничениях на ресурсы (сырьё). 
Р е ш е н и е. Введём вектор переменных задачи X = (
n
x
x
x
 , . . . ,
, 
2
1
), где  

j
x  (j = 1, 2, ..., n)  − объём производства  j-го вида продукции. Затраты i-го 

вида ресурса (сырья) на изготовление данного объёма 
j
x  продукции равны 

j
ij x
a
, поэтому ограничение на использование этого ресурса (сырья) на производство всех видов продукции имеет  вид  
i
n
in
i
i
b
x
a
x
a
x
a
≤
+
+
+
 . . . 
2
2
1
1
.  
Прибыль  от реализации  j-го  вида продукции равна
j
j x
с
, поэтому целевая 

функция 
n
nx
с
x
с
x
с
X
Z
+
+
+
=
 
...
 
)
(
2
2
1
1
. 
Математическая модель имеет вид 
 

⎪
⎪
⎩

⎪⎪
⎨

⎧

≤
+
+
+

≤
+
+
+

≤
+
+
+

→
+
+
+
=

,
 . . . 
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

,
 . . . 

,
 . . . 

        

,
max
   
. . . 
  
)
(

2
2
1
1

2
2
2
22
1
21

1
1
2
12
1
11

2
2
1
1

m
n
mn
m
m

n
n

n
n

n
n

b
x
a
x
a
x
a

b
x
a
x
a
x
a

b
x
a
x
a
x
a

x
c
x
c
x
c
X
Z

 

             
   
 
 
 
x
j
n
j ≥
=
0
1 2
,
,
, ...,
. 
Задача составления рациона. Для полноценного откорма каждое животное должно получать ежедневно m питательных веществ в количествах не 
менее 
m
b
b
b
 , . . . ,
 ,
2
1
.  В рацион животных входят n видов кормов. Известно: 
aij (i = 1, 2, ..., m; j = 1, 2, 3, ..., n) − содержание i-го питательного вещества в 

единице j-го вида корма; c j  ( j = 1, 2, 3, ..., n) − стоимость единицы j-го вида 

корма. Требуется составить суточный рацион полноценного откорма животных, обеспечивающий минимальные затраты. 
Р е ш е н и е.  Введём  переменные  задачи  X = ( x
x
xn
1
2
 
...  
,
,
,
),  где  x j    

( j = 1, 2,..., n) − объём j-го вида корма, входящего в суточный рацион. Так 
как количество i-го питательного вещества, содержащегося в j-ом виде корма 
равно a x
ij
j , то ограничение на содержание этого питательного вещества в 
рационе имеет вид 
i
n
in
i
i
b
x
a
x
a
x
a
≥
+
+
+
 . . . 
2
2
1
1
. Так как стоимость j-го вида 
корма, входящего в суточный рацион равна c x
j
j,  то целевая функция 

n
nx
с
x
с
x
с
X
Z
+
+
+
=
 
...
 
)
(
2
2
1
1
.  
Математическая модель имеет вид 

⎪⎩

⎪⎨

⎧

≥
+
+
+

≥
+
+
+
≥
+
+
+

→
+
+
+
=

,
 . . . 
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
,
 . . . 
,
 . . . 

        

min,
 . . . 
  
)
(

2
2
1
1

2
2
2
22
1
21
1
1
2
12
1
11
2
2
1
1

m
n
mn
m
m

n
n
n
n
n
n

b
x
a
x
a
x
a

b
x
a
x
a
x
a
b
x
a
x
a
x
a
x
c
x
c
x
c
X
Z

 

                  
   
 
 . . .  
x
j
n
j ≥
=
0
1 2
,
,
,
,
. 
 
1.3. Каноническая форма задачи линейного программирования 
 
В общем случае задача линейного программирования записывается так, 
что ограничениями являются как уравнения, так и неравенства, а переменные 
могут быть как неотрицательными, так и произвольно изменяющимися.  В 
том случае, когда все ограничения являются уравнениями и все переменные 
удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Она может быть представлена в координатной,  векторной  или матричной записи. 
1. Каноническая задача линейного программирования в координатной 
записи имеет вид: 

⎪⎩

⎪⎨

⎧

=
+
+
+

=
+
+
+
=
+
+
+

→
+
+
+
=

,
 . . . 
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
,
 . . . 
,
 . . . 

        

,
(min)
max
 . . . 
)
(

2
2
1
1

2
2
2
22
1
21
1
1
2
12
1
11
2
2
1
1

m
n
mn
m
m

n
n
n
n
n
n

b
x
a
x
a
x
a

b
x
a
x
a
x
a
b
x
a
x
a
x
a
x
c
x
c
x
c
X
Z

                    (1.6) 

n
j
x j
 , . . . ,2 ,1
    
,0
  
=
≥
.  
Данную задачу можно записать, используя знак суммирования, 

.
 , . . . ,2 ,1
   
,0
     

,
 , . . . ,2 ,1
   
,

,
(min)
max
)
(

1

1

n
j
x

m
i
b
x
a

x
c
X
Z

j

n

j
i
j
ij

n

j
j
j

=
≥

=
≤

→
=

∑

∑

=

=

                                 (1.7) 

 
2. Каноническая задача линейного программирования в векторной записи 

имеет вид: 

.
    
          

,
 . . . 
(min),
max
)
(
    

0
2
2
1
1
θ
≥

=
+
+
+

→
=

X

A
x
A
x
A
x
A
CX
X
Z

n
n
                           (1.8) 

В данном случае введены векторы 
),
 , . . . ,
 ,
(
2
1
n
x
x
x
X =
  
),
 , . . . ,
 ,
(
2
1
n
c
c
c
C =
 
)
0 , . . . ,0 ,0
(
=
θ
, 

,
 , . . . ,2 ,1
   
,
. . .
2

1

n
j

a

a
a

A

mj

j

j

j
=
⎟⎟
⎟
⎟

⎠

⎞

⎜⎜
⎜
⎜

⎝

⎛

=
    
⎟
⎟
⎟

⎠

⎞

⎜
⎜
⎜

⎝

⎛

=

m
b

b
b

A
...
2
1

0
. 

3. Каноническая задача линейного программирования в матричной  записи имеет вид: 

,
   
,
  
(min),
max
)
(

0
θ
≥
=

→
=
X
A
AX
CX
X
Z
                                   (1.9) 

где  

,

 . . . 
 
.  .  .  .  .  .  .  .  .  .  .
 . . . 
  
  . . . 
  

2
1

2
22
21
1
12
11

⎟
⎟
⎟

⎠

⎞

⎜
⎜
⎜

⎝

⎛
=

mn
m
m

n
n

a
a
a

a
a
a
a
a
a

A
    
⎟
⎟
⎟

⎠

⎞

⎜
⎜
⎜

⎝

⎛
=

n
x

x
x

X
...
2
1
,  
⎟
⎟
⎟

⎠

⎞

⎜
⎜
⎜

⎝

⎛
=

m
b

b
b

A
...
2
1

0
. 

Здесь А − матрица коэффициентов системы уравнений, Х − матрицастолбец переменных задачи, A0 − матрица-столбец правых частей системы 
ограничений. 
Нередко используются задачи линейного программирования, называемые 
симметричными, которые  в  матричной записи имеют вид:  

θ
≥
≤

→
=
X
A
AX
CX
X
Z
  ,
  
max,
)
(

0
                                       (1.10)  

или  

    
.
  ,
   

min,
)
(

0
θ
≥
≥

→
=

X
A
AX

CX
X
Z
                                       (1.11) 

 
1.4. Приведение общей задачи линейного программирования  
к канонической форме 
 
В большинстве методов решения задач линейного программирования 
предполагается, что система ограничений состоит  из уравнений и естественных  условий неотрицательности переменных. Однако при составлении математических моделей экономических задач ограничения в основном формируются  в виде системы неравенств, поэтому необходимо уметь переходить 
от системы неравенств к системе уравнений. Это может быть сделано следующим образом. 
Возьмём, например, линейное неравенство 
b
x
a
x
a
x
a
n
n
≤
+
+
+
 . . . 
2
2
1
1
 
и прибавим к его левой части некоторую величину 
1
+
n
x
, такую, чтобы нера

венство превратилось в равенство  
b
x
x
a
x
a
x
a
n
n
n
=
+
+
+
+
+1
2
2
1
1
 . . . 
. При 
этом данная величина 
n
n
n
x
a
x
a
x
a
b
x
−
−
−
−
=
+
...
2
2
1
1
1
 является неотрицательной. 
Следующая теорема даёт основание для возможности такого преобразования. 
Теорема 1.1. Каждому решению β
β
β
β
= (
,
,
,
)
1
2
 
 . . .  
n  неравенства 
b
x
a
x
a
x
a
n
n
≤
+
+
+
 . . . 
2
2
1
1
                            (1.12) 
соответствует единственное решение 
)
 ,
 , . . . ,
 ,
(
1
2
1
+
β
β
β
β
=
β
n
n
 уравнения 
b
x
x
a
x
a
x
a
n
n
n
=
+
+
+
+
+1
2
2
1
1
 . . . 
                      (1.13) 
и неравенства 
0
1 ≥
+
n
x
,                                                (1.14) 

и, наоборот,  каждому решению β  уравнения  (1.13) и неравенства  (1.14) соответствует единственное решение βнеравенства  (1.12). 
Д о к а з а т е л ь с т в о.   Пусть  
)
 , . . . ,
 ,
(
2
1
n
β
β
β
=
β
 − решение неравенства (1.12), тогда 
b
a
a
a
n
n
≤
β
+
+
β
+
β
 . . . 
2
2
1
1
 и 
0
)
 . . . 
(
1
2
2
1
1
≥
β
=
β
+
+
β
+
β
−
+
n
n
n
a
a
a
b
. 
Подставим в уравнение (1.13) вместо переменных 
1
2
1
,
,...,
,
+
n
n x
x
x
x
 значения 
, . . . ,
 ,
2
1 β
β
 β
β
n
n
, 
+1, получим  
=
β
+
β
+
+
β
+
β
+1
2
2
1
1
 . . . 
n
n
n
a
a
a
 
b
a
a
a
b
a
a
a
n
n
n
n
=
β
+
+
β
+
β
−
+
β
+
+
β
+
β
=
)
...
(
 . . . 
2
2
1
1
2
2
1
1
. 
Таким образом, 
)
 ,
 , . . . ,
 ,
(
1
2
1
+
β
β
β
β
=
β
n
n
 удовлетворяет уравнению (1.13) 
и неравенству (1.14). Значит доказана первая часть теоремы. 
Пусть теперь β  удовлетворяет уравнению (1.13) и неравенству (1.14), т.е. 
имеем  
b
a
a
a
n
n
n
=
β
+
β
+
+
β
+
β
+1
2
2
1
1
 . . . 
   и   βn+ ≥
1
0. 
Отбрасывая в левой части последнего равенства неотрицательную величину  βn+1, получаем  
b
a
a
a
n
n
≤
β
+
+
β
+
β
 . . . 
2
2
1
1
, т.е. 
)
 , . .. ,
 ,
(
2
1
n
β
β
β
=
β
 
удовлетворяет неравенству (1.12). Теорема доказана.  
Если неравенство имеет вид 
b
x
a
x
a
x
a
n
n
≥
+
+
+
 . . . 
2
2
1
1
, то дополнительную неотрицательную переменную 
1
+
n
x
 необходимо ввести в его левую 
часть со знаком минус, т.е. 
b
x
x
a
x
a
x
a
n
n
n
=
−
+
+
+
+1
2
2
1
1
 . . . 
. 
Неотрицательные переменные, вводимые в ограничения неравенства для 
превращения их в уравнения, называются дополнительными переменными. 
Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на её значение. 
В том случае, когда задача имеет произвольно изменяющиеся переменные, то любую такую переменную x j  заменяют разностью двух неотрица
тельных переменных, т.е. 
j
j
j
x
x
x
′′
−
′
=
, где 
0
≥
′j
x
 и 
0
≥
′′j
x
. 
Иногда возникает также необходимость перейти в задаче от нахождения 
минимума к нахождению максимума или наоборот. Для этого достаточно из

менить знаки всех коэффициентов целевой функции на противоположные, а 
в остальном задачу оставить без изменения. Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций на оптимальных решениях отличаются только знаком. 
Пример 1.1. Привести к каноническому виду задачу линейного программирования. 
min,
   
 
  
3
)
(
3
2
1
→
+
+
=
x
x
x
X
Z
 

  

.3 ,2
  ,0
   
          

 
,5 
2
  
2
,1 
2
  
  
,7
  
2
+
  
        

5

4
3
2
1
3
2
1
3
2
1

=
≥
−

+
⎪⎩

⎪⎨
⎧

≥
−
+
≤
+
−
=
+

j
x
x

x
x
x
x
x
x
x
x
x
x

j

 

Р е ш е н и е. Перейдем к задаче на отыскание максимума целевой функции. Для этого изменим знаки коэффициентов целевой функции. Для превращения второго и третьего неравенств системы ограничений в уравнения 
введём неотрицательные дополнительные переменные  x
x
4
5
,
 (на математической модели эта операция отмечена буквой Д).  Переменная x4  вводится в 
левую часть второго неравенства со знаком  "+", так как неравенство имеет 
вид 
"
"≤ . Переменная 
5
x  вводится в левую часть третьего неравенства со зна
ком  "−", так как неравенство имеет вид 
"
"≥ . В целевую функцию переменные 

5
4, x
x
 вводятся с коэффициентом, равным нулю. Переменную 1x , на которую не наложено условие неотрицательности, заменяем разностью
1
1
1
x
x
x
′′
−
′
=
, 
,0
1 ≥
′x
0
1 ≥
′′x
. Записываем задачу в каноническом виде 

 

⎪⎩

⎪⎨
⎧

=
−
−
+
′′
−
′
=
+
+
−
′′
−
′
=
+
+
′′
−
′

→
+
+
−
−
′′
+
′
−
=

,5
 
          
2
  
2
2
,1
  
         
  
2
  
 
   
  
,7
        
          
  
2
  
   
  
    
          

max,
0
0
  
 
3
3
)
(

5
3
2
1
1
4
3
2
1
1
3
2
1
1

5
4
3
2
1
1

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
X
Z

 

                                        
4 
3,
 
2,
 
,0
,0
,0
1
1
=
≥
≥
′′
≥
′
j
x
x
x
j
, 5.  

 
В некоторых случаях возникает необходимость приведения канонической 
задачи к симметричной задаче. Рассмотрим пример. 
Пример 1.2. Привести к симметричному виду  задачу линейного программирования  
Z X
x
x
x
x
(
)
max,
=
−
+
+
→
4
5
2
1
2
3
4
  
 
 

                                        
⎩⎨⎧
=
−
+
+
−
=
+
+
−
,2
4
3
10
7
,6
4
  
2
 
3
   

4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
 

                                              x
j
j ≥
=
0,
1, 2, 3, 4. 

 
Р е ш е н и е. Методом Жордана-Гаусса приведём систему уравненийограничений задачи к равносильной разрешённой. Одновременно разрешённые неизвестные исключим из целевой функции. Для  этого  в  таблице  решения задачи (табл. 1.1) наряду  с  коэффициентами  уравнений  системы  ог
Д 

раничений  в  дополнительной  строке  запишем  коэффициенты  целевой  
функции. В последнем столбце дополнительной строки (на месте правой  
части уравнений) запишем  свободный член целевой функции, равный нулю. 
При  вычислениях  учитываем,  что  разрешающий  элемент  в  последней  
строке  (в  целевой  функции)  выбирать  нельзя.  
 
                                                    Таблица 1.1 
x1 
x2 
x3 
x4 
b 

3 
−2 
1 
4 
6 

−7 
10 
3 
−4 
2 

4 
−5 
1 
2 
0 

3 
−2 
1 
4 
6 

−16 
16 
0 
−16
−16

1 
−3 
0 
−2 
−6 

3 
−2 
1 
4 
6 

−1 
1 
0 
−1 
−1 

1 
−3 
0 
−2 
−6 

1 
0 
1 
2 
4 

−1 
1 
0 
−1 
−1 

−2 
0 
0 
−5 
−9 

 
Число  −9,  полученное  в  последнем  столбце  последней  строки  таблицы,  необходимо  записать  в  целевую  функцию  с  противоположным  знаком. В результате данных преобразований задача принимает следующий вид 
                                 
                                 
max,
9
5
     
          
2
)
(
4
1
→
+
−
−
=
x
x
X
Z
 

                                             
⎩⎨⎧
−
=
−
+
−
=
+
+
,1
         
,4
  
2
       
   

4
2
1
4
3
1
x
x
x
x
x
x
 

                                                  x
j
j ≥
=
0,
1, 2, 3, 4. 

 
Переменные x
x
2
3
,
  неотрицательные, каждая из которых входит только 
в одно из уравнений, и не входит в целевую функцию. Отбросив их, можно 
записать задачу в симметричном виде 
 
                                        Z X
x
x
(
)
max,
= −
−
+
→
2
5
9
1
4
 

                                                       
+
  
  
x
x
x
x

1
4

1
4

2
4
1
≤
−
−
≤ −
⎧
⎨
⎩

,
,  

                                                        x
j
j ≥
=
0,
1, 4. 

 
 
 
 
 
 
 

× (−3)   × (−1) 
 
 

  целевая функция  
 
×

16
1  

                 
 
× 2  × 3 
 

+

+

+

1.5. Задания для самостоятельного решения 
 
Привести к каноническому виду. 
1.3. Z X
x
x
x
(
)
max,
=
−
+
→
3
2
1
2
3
 
 

          

.3 ,2 ,1
  ,0
     

,2
  
2
  

,6
2
4
3 

,1
3
         
2 

3
2
1

3
2
1

3
1

=
≥

⎪⎩

⎪⎨

⎧

≥
−
+

≥
+
+

−
≤
−

j
x

x
x
x

x
x
x

x
x

j

 

 
1.4.Z X
x
x
x
x
(
)
max,
=
+
−
+
→
2
4
1
2
3
4
 
3
 

                 

.4 ,3 ,2 ,1
  ,0
     

,8
      
          
3
  

,4
2
      
3
2

,5
      
3
  
 

,4
 
2
+
 

2
1

4
2
1

3
2
1

4
3
2
1

=
≥

⎪
⎪
⎩

⎪⎪

⎨

⎧

=
+

≥
−
+

≤
+
−

≥
+
−

j
x

x
x

x
x
x

x
x
x

x
x
x
x

j

 

 
Привести к симметричной форме записи.  
 
1.5. Z X
x
x
x
x
(
)
max,
=
−
+
+
→
2
2
1
2
3
4
  
 

           −
+
+
−
=
−
−
+
=
⎧
⎨
⎩

x
x
x
x
x
x
x
x

1
2
3
4

1
2
3
4

2
2
9
6
5
6
  
 
,
, 

                   x
j
j ≥
=
0,
1, 2, 3, 4. 

 
1.6. Z X
x
x
x
x
(
)
max,
=
−
+
+
→
4
3
4
1
2
3
4
  
 
 

            
2
 
  
  
7
10
3
6
4
3
12

1
2
3
4

1
2
3
4

x
x
x
x
x
x
x
x
−
−
+
=
−
+
+
+
=
⎧
⎨
⎩

,
, 

                   x
j
j ≥
=
0,
1, 2, 3, 4. 

 
1.7. Z X
x
x
x
x
x
(
)
max,
=
−
−
+
+
→
9
11
3
8
5
1
2
3
4
5
 

           
−
+
+
−
+
=
+
+
+
+
=
−
−
+
−
= −

⎧

⎨⎪

⎩⎪

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x

1
2
3
4
5

1
2
3
4
5

1
2
3
4
5

2
2
3
2
2
2
9
14
3
2
1

 
   
  
 
   
 
  
 2
 
   
 
  

,
,
,
 

                       
5
4,
 
3,
 
2,
 
1,
,0
=
≥
j
x j
. 

 
1.8. Z X
x
x
x
x
x
(
)
max,
=
+
+
−
+
→
  
 
 
 
1
2
3
4
5
2
3
 

           
−
+
+
−
−
=
−
+
+
+
=
+
+
+
+
=

⎧

⎨⎪

⎩⎪

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x

1
2
3
4
5

1
2
3
4
5

1
2
3
4
5

4
2
5
2
7
9
8
9
15

 
 
 
  
 3
 
  
 2
2
 
 
3

,
,
,
 

                        
5
4,
 
3,
 
2,
 
1,
,0
=
≥
j
x j
.