МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

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

Version 4.8.

1. Введение

1.1 Предмет исследования операций.

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

Успехи использования математических методов в естественных
науках много раз наталкивали на мысль приложить их и к
управленческим задачам.

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

Несмотря на это математические модели всё шире применяют
при изучении таких вопросов, которые ранее изучались только
на гуманитарном уровне. Этот подход позволяет выделять и
обобщать существенные закономерности, а иногда и формули-
ровать решающие рекомендации.

Исследование операций представляет собой применение мате-
матических методов к проблемам управления, возникающим в
промышленности, деловой сфере, обороне и др.

Важнейшим этапом при этом является построение математиче-
ской модели.

1
2
3
4
1.2 Задача математического программирования.
Математическое программирование —дисциплина,
изучающая теорию и методы решения задач о нахождении
экстремума функции на заданном множестве.
1
2
3
4
5
6
7
Именно менеджер должен увидеть в реальной ситуации возмож-
ности применения соответствующих моделей для повышения
эффективности управления, собрать необходимую исходную
информацию.
А после решения задачи осмыслить полученный результат и
продумать, как его использовать для принятия разумного управ-
ленческого решения.
1
2
3
4
5
Надо подчеркнуть, что хотя математические
методы дают чёткие ответы на точно постав-
ленные вопросы, сами по себе они вопросов не
ставят, критерии не выбирают и решения не
принимают. Это - задача менеджера.
1
2
Сформулировать
проблему
1
2
3
Построить новую или
выбрать существующую
модель
1
2
Найти решение в рамках
выбранной модели
1
2
Протестировать
найденное решение
1
Внедрение

В зависимости от природы допустимого множества U изучают
различные виды задач. Например:

  • задачи дискретного программирования — если множе-
    ство U конечно или счётно;
  • задачи линейного программирования, если все ограни-
    чения и целевая функция являются линейными;
  • задачи нелинейного программирования, если ограниче-
    ния или целевая функция содержат нелинейные выраже-
    ния;
  • задачи целочисленного программирования — если зна-
    чения переменных являются целыми числами.

Методы решения задач разных классов совершенно различны и
существенно используют специфику задачи.

Например, задача дискретного программирования при неболь-
шом размере множества U может быть решена простым пере-
бором.

Пример. Задача о назначениях.
Требуется распределить пять работников на
пять работ. Эффективность работы зависит от
опыта и квалификации. Эффективность

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
i-го работника на j-й работе (зависящая от опыта и квалифика-
ции) стоит на пересечении i-й строки и j-го столбца матрицы
Другими словами, требуется найти пять клеток в матрице так,
чтобы все они были в разных строках и столбцах, и сумма чи-
сел была максимальна
Ответ. Максимальное значение суммы равно 15.
Пример. Портфель ценных бумаг.
Пусть в нашем распоряжении имеется денежная сумма 100.
Можно приобрести три вида акций. Средняя дневная
доходность, посчитанная за прошлый год, равна,
соответственно, 0,28%, 0,25%, 0,05%. Дисперсии равны 5, 2, 2
ковариации cov 12 =3, cov 13 =4, cov 23 =1. Требуется составить
наименее рискованный портфель с доходностью 0,2% в день.
Обозначим Xj ─ количество денег, вложенных в акции j-го
вида.
За меру рискованности инвестиционного портфеля можно
принять его дисперсию (т.е. разброс доходности относительно
среднего значения).
1
2 4 2 1
1
5 2 2 2 3
1
1 3 2 3
1
1 2
1
2
2
3
1
2
2
2
1
2
3
2
1
       
1
2
          
X X X X
1
Dx X X X X X
1
Получим задачу
1
 
1

1
2


1

1
2


1

1

1
  
1
     
1
              
1
, , 0
1
100
1
0 , 28 0 , 25 0 , 05 0 , 2
1
5 2 2 6 8 2 min
1
1 2 3
1
1 2 3
1
1 2 3 1 2 3
1
1 2 1 3 2 3
1
2
2
3
1
2
2
2
1
2
2
1
1
X X X
1
X X X
1
X X X X X X
1
X X X X X X X X X
1
Пример. Задача о найме работников.
1
Целевая функция
1
2
3
Ограничения, определяю-
щие допустимое множество
U
1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

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

Для выполнения некоторого проекта в течение шести месяцев
по нормам требуются следующие количества работников оди-
наковой квалификации:

m 1 =6, m 2 =m 3 =m 4 =4, m 5 =5, m 5 =2,
причем перед началом первого месяца (в нулевом месяце) фак-
тически имеется M 0 = 2 сотрудника.

Администрация планирует в конце каждого месяца корректи-
ровать число работающих.

На прием одного сотрудника необходимо затратить 200 у. е., а
на увольнение — 600 у. е.

Предполагается, что ежедневные расходы на содержание избы-
точного работника составляют 20 у. е., а в случае нехватки пер-
сонала приходится нести затраты в размере 40 у. е. за каждое
вакантное место.

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

  1. Задача нелинейной оптимизации

2.1 Экстремальные задачи без ограничений.

В классической постановке такой задачи ограничений нет, а
целевая функция дифференцируема.

1
f(x)fx 1 ,...,xnmaxmin

Необходимое условие экстремума. Если в точке
x 0 =(x 10 ,…,xn^0 ) функция f(x 1 ,…,xn) имеет экстремум и диф-
ференцируема, то в этой точке каждая из частных произ-
водных функции f(x 1 ,…,xn) равна 0, т.е.

gradf (^0)
Достаточное условие экстремума.
Пусть в некоторой точке grad f=0. Тогда

  1. Если матрица Гессе Hf в этой точке положительно определе-
    на, то в этой точке минимум.
  2. Если матрица Гессе Hf в этой точке отрицательно определе-
    на, то в этой точке максимум.















    // // //
    // // //
    // // //

    … … … …


    1 2
    21 22 2
    11 12 1
    n n nn
    n
    n
    xx xx xx
    xx xx xx
    xx xx xx
    f
    f f f
    f f f
    f f f
    H
    Знакоопределённость матрицы Hf, можно проверять следую-
    щим образом:

Критерий Сильвестра.

  1. Hf положительно определена ↔ Все Δk>
  2. Hf отрицательно определена ↔ Δ1<0, Δ2>0, Δ3<0, Δ4>0, и
    т.д. (знаки чередуются)
    Здесь
    , …,…
    , ,
    3 4
    1 2
    31 32 33
    21 22 23
    11 12 13
    21 22
    11 12
    11
     
      
      
      
     
     
     
        
    xx xx xx
    xx xx xx
    xx xx xx
    xx xx
    xx xx
    xx
    f f f
    f f f
    f f f
    f f
    f f
    f

Пример. Найти экстремумы функции

Решение. Выпишем необходимое условие экстремума

Получилась одна точка. Выпишем теперь матрицу Гессе.

1
2
3
 


1
2
3



1
2

 
1
2
3
  


1
2


1
2


1
2
3


2 2

(^222)
// //
// //
x x
x x
yx yy
xx xy
f
e y e
e x y e y
f f
f f
H
В точке x= −1, y=0:
2 0
0 2
0
0 , 1 2
1
2
1
1  

      

 e
e
e
e
Ответ. В точке x= −1, y=0 минимум.
Типовая задача.
Цены на два вида товаров равны соответственно P 1  8 руб. и
P 2  10 руб. Определить, при каких количествах x и y продаж
этих товаров прибыль будет максимальной, если функция из-
держек имеет вид Cx^2 xyy^2.
Решение.
Функция прибыли имеет вид
P(x,y) 8 x 10 yx^2 xyy^2.^
Необходимое условие экстремума выглядит так:









   
   
 
4.
2 ,
10 2 0 ;
8 2 0 ,
0
y
x
f x y
f x y
gradf
y
x
Выпишем матрицу Гессе:






 
 








1 2
2 1
// //
// //
yx yy
xx xy
f f f
f f
H.
3 0
1 2
2 1
1 2 0 , 2  
 
 
    .
Значит, матрица Гессе отрицательно определена, следователь-
но, максимум прибыли, равный f(2;4)=28 будет достигаться при
при х=2, y=4.
Ответ. Максимум в точке (2;4)
Задача. Найти экстремумы функции fx,yx^3 y^3  3 xy.
Ответ. Максимум в точке (-1;1).
Задача. Найти экстремумы функции fx,y 2 xy 4 x 2 y.
Ответ. Экстремума нет.
Задача. Найти экстремумы функции
fx,y 3 x^2 x^3  3 y^2  4 y.
Ответ. Минимум в точке (0;-2/3).
Задача. Цены на два вида товаров равны соответственно
P 1  32 руб. и P 2  24 руб. Определить, при каких количествах
x и y продаж этих товаров прибыль будет максимальной, если
функция издержек имеет вид^222
2
3
C x  xyy.

f(x,y)xy^2 ex

1
2
 
  
1
2


1
2
3



1
2


1
2

  
1
2
3
   
 
0
1
2
1
2 0
1
1 0

( ) (^0) /
/ 2
y
x
f e y
f e x y
gradf x x
y
x
x







 

0 2
0
1
1
e
e
Hf

Ответ. При x 8 , y 4 достигается максимум прибыли, рав-

ный 176 руб.

2.2 Градиентный метод поиска экстремума функ-
ции.

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

Будем рассматривать задачу на максимум. (Задача на минимум
сводится к ней изменением знака функции f(x).)

1
f(x)fx 1 ,...,xnmaxmin

Как известно, градиент функции показывает направление
наискорейшего возрастания функции в данной точке

Идея градиентных методов состоит в том, чтобы, начав с неко-
торой точки, сделать шаг в направлении градиента.
Затем вычислить новый градиент и сделать шаг в направлении
его.
И так далее.

xn 1 xnngradf(xn)

В качестве чисел λn можно, напри-
мер, взять первое число из списка
(1,1/2,1/4,1/8,…), для которого

1
fxn 1 fxn

Пример. Сделаем несколько шагов
градиентного метода для задачи.

1
f(x,y) 100  25 sinx 2 x^2 xyy^2 max
1
Шаг 1. Начнём, например, с точки x 0 =(0;0). f(x 0 )=100.
1

1
2


1
2

  
1
2
   
2 0
1
2
25 cos 4 25
/
1
/
1
f x y
1
f x x y
1
y
1
x
gradf( 25 , 0 ); x 1 x 0 ( 25 , 0 )
 1 x 1 x 0 ( 25 , 0 )( 25 , 0 ),f(x 1 ) 1153  100
1
2
( 25 , 0 ) ( 12 , 5 , 0 ), ( ) 214 100
2
1
2
1
2
1
1
 x 1 x 0   f x 1  
1
2
( 25 , 0 ) ( 6 , 25 , 0 ), ( ) 21 100
4
1
2
1
4
1
1
 x 1 x 0   f x 1  
1
2
( 25 , 0 ) ( 1 , 56 ; 0 ), ( ) 120 , 1 100
16
1
2
1
16
1
1
1
...
 x 1 x 0   f x 1  

Шаг 2. x 1 =(1,56;0). f(x 1 )=1 20 ,1.

1

1
2


1
2

  
1
2
   
2 1 , 56
1
2
25 cos 4 6 , 04
/
1
/
1
f x y
1
2
f x x y
y
1
x
1
( ) 120 , 46 120 , 1
1
2
( 6 , 04 ; 1,56) ( 1 , 18 ; 0 , 09 ),
16
1
2
1
16
1
1
1
...
1
2
1
2
2 1
 
1
       
1
f x
1
 x x

2.3 Экстремальные задачи с ограничениями типа
равенств.

1
2
   
 
1
  
1
2


1

1
2


1

1

1

1
 
1
0
1
...
1
0
1
2
( ) ,..., max min
1
1
1
1
g x
1
g x
1
f x f x x
1
m
1
n

Необходимое условие условного экстремума.
Пусть в некоторой окрестности точки x 0 целевая функция f(x) и
ограничения gi(x) дифференцируемы и пусть grad(g 1 ), …,
grad(gm) линейно независимы. Тогда для того, чтобы в точке x 0
был условный экстремум, необходимо, чтобы в этой точке
grad(f) разлагался по
grad(g 1 ), …, grad(gn).

Пример. Найти расстояние от точки
A(0;2) до параболы y=x^2.

Решение.

1
2
 

1

1
2


1
2
  
2

(^222) min
y x
x y
f x^2 y 2 ^2 ,gradf 2 x; 2 y 4 ^
В этом случае всего одно ограничение, поэтому необходимое
условие экстремума примет вид:
   
  



 
1 0
1
g x

grad f  grad g
1
2
3
   


1

1
2


1
2
  
2
1
2
2 ; 2 4 2 ; 1
y x
x y  x
1
2
3



1
2


1

1

1
 
1

1
2
1
2 4
1
2 2
1
y x
1
y
1
x x
y 0 , x 0 либо y^1 ,^5 , x^1 ,^5
1
2
3
4
Три точки, М 1 ,М 2 , М 3 :
В точке М 1 локальный максимум расстоя-
ния, в точках М 2 , М 3 – минимумы
Ответ. Расстояние равно
1
 1 , 5   1 , 5 2 ^21 , 75
1
2
2
AM 2    
1
2
3
4
5
6
7
8
Типовая задача.
Предприниматель решил выделить на расширение своего дела
150 тыс. руб. Известно, что если на приобретение нового обо-
рудования затратить x тыс. руб., а на зарплату вновь принятых
работников y тыс. руб., то прирост объема продукции составит
Q 0 , 001 x^0 ,^6 y^0 ,^4. Как следует распределить выделенные де-
нежные ресурсы, чтобы прирост объема продукции был макси-
мальным?

A

M(x,y

)

A

M

2

M

1

M

3

Решение.

Имеем задачу вида

1

1

1
2

 
1
2
 
150.
1
2
0 , 001 0 ,^60 ,^4 max,
x y
1
f x y
1
gradf( 0 , 0006 x^0 ,^4 y^0 ,^4 ; 0 , 0004 x^0 ,^6 y^0 ,^6 ).

Имеем всего одно ограничение, поэтому необходимое условие
экстремума примет вид:

1
2
   
  
1

1
2


1
2
 
1 0
1
2
1
g x
grad f  grad g
1

1

1

1

1

1

1

1

1
 
1

1

1
2
3



1
2


1

1
 
1

1
2


1

1
150.
1
3 2 ,
1
6 10000 ,
1
150
1
0 , 0004 ,
1
0 , 0006 ,^0 ,^4
1
0 , 4
1
0 , 6 0 , 6
1
0 , 4 0 , 4
1
x y
1
y x
1
x
1
y
1
x y
1
x y
x y 

Откуда получаем x=60, y=90. Так как в этой точке выполнены
необходимые условия экстремума и, например f(150;0)=0, то
(60;90) - точка максимума. Значит, 60 тыс. руб. нужно напра-
вить на приобретение нового оборудования, а 90 тыс. руб. на
зарплату новых работников. Тогда прирост объема продукции
будет максимальным.

Ответ. (60;90).

Задача. Найти экстремумы функции z 2 xy при условии

1
x^2 y^2  5
1
2
Ответ. Условный минимум в точке (-2;-1), zmin 5 ; условный
максимум в точке (2;1), zmax 5.
1
2
Задача. Найти экстремумы функции
x y
1
z
1
2
1 1
  при условии
1
xy 2.
1
Ответ. Условный минимум в точке (-3/2;-3/2), zmin 4 , 75.
1
2
3
4
5
6
7
Задача. Общие издержки производства заданы функцией
TC 0 , 5 x^2  0 , 6 xy 0 , 4 y^2  700 x 600 y 2000 , где x^ и y^ -^ со-
ответственно количество товаров A и B. Общее количество
произведенной продукции должно быть равно 500 ед. Сколько
единиц товара A и B нужно производить, чтобы издержки на
их изготовление были минимальными?
Ответ. (0;500)
1
2
2.4 Экстремальные задачи с ограничениями типа
равенств и неравенств
1
   
1
 
1
2
 

1

1

1

1

1

1

1

1

1

1

1

1
2


1
2


1

1
2


1
2


1

1

1

1

1
2


1
2


1

1
2


1
2


1

1

1

1

1
 
1
0
1
...
1
0
1
( ) ,..., max min
1
1
1
1
1
g x
1
g x
1
f x f x x
1
m
1
n
1
2
3
Если искомая точка лежит строго внутри области, (неравенства
выполняются как строгие), то искать её можно обычными ме-
тодами безусловной оптимизации.

Но экстремум может достигаться и на границе (тогда некото-
рые неравенства превращаются в равенства).

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

Пример. Найти наибольшее и наименьшее значения функции
f(x,y)=x^2 ─2y+3 в области
x≤0, y≥0, y≤x+

Пример. 1) Сначала найдём экстремальные точки внутри обла-
сти

1
gradf 2 x; 2  0  2  0

Внутри экстремумов нет

  1. На стороне AO. y=0, ─1≤x≤0. f=x^2 +3. Экстремальные точки :
    2 x=0 (точка О).

  2. На стороне BO. x=0, 0≤y≤1.
    f(x,y)=─2y+3. Экстремальные точки:
    ─2=0. Нет.

  3. На стороне AB. y=x+1, ─1≤x≤0.
    f(x,y)=x^2 ─2x+1. Экстремальное значе-
    ние: 2x─2=0. Не лежит на AB.

  4. Вычислим значения функции в
    найденных экстремальных точках и в углах.

f(O)=3, f(A)=4, f(B)=1, f(O)=3.

Ответ. Минимальное значение функции = 1, максимальное
значение = 4. З адача.

Найти наибольшее и наименьшее значение функции
fx,y 1 x 2 y в области x 0 , 0 y 3 x.

Ответ. fmax 7 f 0 , 3 ,fmin 1 f 0 , 0 

1
2
3
Задача.
Найти наибольшее и наименьшее значение функции
f(x,y)x^2 xy 2 x 2 y в области 0 x 1 , 0 y 2.
1
Ответ. fmax 9 f 1 , 2 ,fmin 0 f 0 , 0 .
1
2
3
Задача.
Найти наибольшее и наименьшее значение функции
f(x,y) 2 x 3 y 4 в области |x| 2 , |y| 3.^
1
Ответ. fmax 17 f 2 , 3 ,fmin 9 f 2 , 3 .
1
2
3
Задача.
Найти наибольшее и наименьшее значение функции
f(x,y) 5 x 6 y 1 в области |x| 1 , x 1 yx 2.
1
Ответ. fmax 18 f 1 , 2 ,fmin 22 f 1 , 3 .
1
2
2.5 Решение задач оптимизации при помощи
MS Excel
1
2
3
4
Пример. На ферме в качестве корма для животных
используются два продукта – M и N.
Сбалансированное питание предполагает, что каждое животное
должно получать в день не менее 200 килокалорий,
1
2
3
Для решения оптимизационных задач в MS Excel
необходимо, чтобы был установлен инструмент "По-
иск решения", который не устанавливается при

ссттааннддааррттнноойй установке MS Office, а только при ввыы–

1
ббооррооччнноойй.

причем потребляемое при этом количество жира не должно
превышать 14 единиц.
В 1 кг продукта содержится соответственно:

  • в продукте M - 150 килокалорий и 14 единиц жира;
  • в продукте N - 200 килокалорий и 4 единицы жира.
    Разработать максимально дешевый рацион откорма животных.
    Стоимость 1 кг продукта М составляет 1,5 руб, а 1 кг продукта
    N - 2,3 руб.

Решение.
Формализация задачи:
Переменные:

x 1 - количество продукта М в рационе;
x 2 - количество продукта N в рационе.
Целевая функция - стоимость рациона:
1,5x 1 +2,3x 2 →min
Ограничение по количеству килокалорий:
150x 1 +200x 2 ≥
Ограничение по количеству жира:
14x 1 +4x 2 ≤
Неотрицательность переменных:
x 1 ≥0; x 2 ≥
Ввод исходных данных в ячейки Excel:

Итак, в ячейки А2 и А3 вводим начальные значения x 1 и x 2 -
нули.
В ячейки А4 и А5 вводим левые части ограничений (первона-
чально получатся нули), в ячейки В4 и В5 - правые части соот-
ветствующих ограничений.
В ячейку А6 вводим целевую функцию.

1
2
3
4
Ввод исходных данных завершен.
 Решение задачи.
Последовательностью команд меню Сервис - Поиск решения
вызываем инструмент " Поиск решения ".
1
2
3
4
5
6
7
1) С использованием красной стрелки (переход на рабочий
лист) устанавливаем целевую ячейку - $A$6 равной ми-
нимальному значению.
2) Изменяя ячейки - $A$2:$A$3 с использованием кнопки
Добавить, последовательно добавляем три исходных
ограничения.
3) Нажимаем кнопку Выполнить.
1
2
3
 Интерпретация результатов.
После вычислений на рабочем листе получили следующие ре-
зультаты (см. рис. ниже):

Итак, при дневном рационе

  • 0,909 кг продукта М и
  • 0,318 кг продукта N
    потребности животного в питании будут удовлетворены, при
    этом стоимость рациона будет минимальной и составит 2,
    руб.
  1. Задача линейного программирования

3.1 Постановка задачи.

В задаче линейного программирования целевая функция и
ограничения линейны, т.е. представляют собой суммы произве-
дений констант на переменные задачи.

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
2

  
1

1

1

1

1

1

1

1

1

1

1

1

1
2

  
1
    
1
m m mn n m
1
n n
1
n n
1
a x a x a x b
1
a x a x a x b
1
f x cx cx cx
1
...
1
... ... ... ... ... ...
1
...
1
( ) ... max(min)
1
11 2 2
1
111 12 2 1 1
1
11 2 2

При помощи моделей линейного программирования удаётся
проанализировать множество важных для практики проблем,
относящихся к самым разным сферам деятельности.

1
2
3
4
Важность задачи линейного программирования обусловлена
ещё и тем, что существует достаточно эффективный и универ-
сальный алгоритм решения (симплекс-метод и его разновидно-
сти). Нелинейный случай оказывается существенно сложнее.
1
3.2 Примеры задач линейного программирования.
1
2
3
4
5
6
7
8
9
10
11
12
3.2.1 Задача о рационе.
Рацион кормления коров на молочной ферме может состоять из
трёх продуктов: сена, силоса и концентрата. Эти продукты со-
держат питательные вещества: белок, кальций и витамины.
Численные данные приведены в таблице.
Белок^ Кальций^ Витамины^ Цена ед.^
Сено 50 10 2 30
Силос 70 6 3 40
Концентраты 180 3 1 120
Суточные
нормы по-
требления
1
2000 210 87
1
Формализация задачи
  1. Переменные задачи:
    x 1 - количество сена;
    x 2 - количество силоса
    x 3 – количество концентратов.

Целевая функция : стоимость рациона f(x)=…
3. Ограничения :
3.1. По белку: 50 x 1 + 70 x 2 +… ≥ 2000
3.2. По кальцию: …
3.3. По витаминам: …
3.4. Прочие ограничения: …

1

1

1

1

1

1

1

1

1

1
  
1
  
1
  
1
   
1
0
1
2 3 1 87
1
10 6 3 210
1
50 70 180 2000
1
( ) 30 40 120 min
1
1 , 2 , 3
1
1 2 3
1
1 2 3
1
1 2 3
1
1 2 3
1
x
1
x x x
1
x x x
1
x x x
1
f x x x x

3.2.2 Задача о раскрое.

Из брёвен изготавливаются комплекты брусьев следующего со-
става:

1
(2 бруса по 0,6 м + 1 брус по 1,5 м + 3 бруса по 2,5 м)

Имеется 100 брёвен длины 3 м. Найти план распила, позволя-
ющий получить максимальное количество комплектов.

Формализация задачи

  1. Переменные задачи: Сначала нужно обдумать, какими ра-
    зумными способами можно распилить бревно.
1
2
3
4
 5 брусьев по 0,6 м.
 2 по 0,6 м + 1 по 1,5 м
 2 по 1,5 м
 1 по 2,5 м

xj – количество брёвен, распиленных по j-му способу.

Получаем переменные x 1 ,x 2 ,x 3 ,x 4 – этого не хватает.

Нужно ещё x 5 – количество комплектов.

Целевая функция : количество комплектов f(x)=x 5

  1. Ограничения :

3.1. По брусьям длины 0,6 м и т.п.: …

3.2. По количеству брёвен: …

1
3.3. Прочие ограничения
1

1

1

1

1

1

1

1

1

1

1

1
   
1

1
 
1
 
1
 
1
0
1
100
1
3
1
2
1
5 2 2
1
( ) max
1
1 , 2 , 3 , 4 , 5
1
1 2 3 4
1
4 5
1
2 3 5
1
1 2 5
1
5
1
x
1
x x x x
1
x x
1
x x x
1
x x x
1
f x x
1
2
3
4
5
3.3 Графический метод решения задачи линейного
программирования.
Этот метод можно применять, если количество неизвестных в
задаче
равно 2. Рассмотрим пример.
1
2
3
4
5
6
7
8
9
10
Графически каждому из неравенств соответствует полуплос-
кость. Чтобы её изобразить, нужно сначала нарисовать пря-
мую, заменив знак в неравенстве на “=”. Затем нужно выбрать
одну из двух полуплоскостей, на которые прямая разделяет
плоскость, и заштриховать эту полуплоскость. Чтобы правиль-
но выбрать, нужно взять какую-нибудь точку плоскости, не ле-
жащую на прямой, и подставить в неравенство. Если неравен-
ство выполняется, то точка лежит в нужной полуплоскости,
иначе нужно выбрать другую полуплоскость.
Так, например, неравенству (1) соответствует
   

 
 
  
 
 
  
0 4
3 3
2 8 2
2 7 1
3 2 max 0
1
1 , 2
1
2
1
1 2
1
1 2
1
1 2
x
x
x x
x x
f x x x

Затем

И так далее. Получаем

Кроме выпуклого многоугольника могут получаться и другие
выпуклые фигуры, а также пустое множество.
Далее, вектор c=(3,2), координаты которого – коэффициенты
при неизвествых в целевой функции, показывает направление
наискорейшего возрастания целевой функции. Самая далёкая
точка области в этом направлении – точка максимума. В обрат-
ном направлении – точка минимума. Чтобы найти самую далё-
кую точку, следует провести прямую перпендикулярно вектору
и смещать её параллельно самой себе до крайнего положения.

1
2
Координаты точки находятся решением системы уравнений пе-
ресекающихся в ней прямых.

Задача.

1
2
3
Ответ. Максимума нет, целевая функция неограниченна. Ми-
нимум в точке (1;0)
Задача.
1
2
Ответ. Минимум в точке (1;1).
Задача.
1
, 0
1
3 ,
1
2 2 ,
1
3 2 6 ,
1
2 ,
1
( ) 3 2 max,
1
1 2
1
2
1
1 2
1
1 2
1
1 2
1
1 2
1

1

1
2


1

1
2


1

1

1
 
1
 
1
 
1
  
1
x x
1
x
1
x x
1
x x
1
x x
1
f X x x
1
2
Ответ. Максимум в точке (4;3)
Задача.
1

1
2


1

1
2


1

1

1
 
1
 
1
 
1
  
1
4 ,
1
2 6 ,
1
2 16 ,
1
4 0 ,
1
( ) 4 2 min,
1
1
1
1 2
1
1 2
1
1 2
1
1 2
1
x
1
x x
1
x x
1
x x
1
2
3
4
5
6
f X x x
  



 
1

1

1

1

1

1

1

1

1
 
1
  
1
 
1
  
1
0 4
1
2 1 3
1
2 1 2
1
1 1
1
2 min,max 0
1
1 , 2
1
1 2
1
1 2
1
1 2
1
1 2
1
x
1
x x
1
x x
1
x x
1
f x x x
1
2
3
4
5
 



 
1

1

1

1

1

1

1

1

1
 
1
 
1
  
1
  
1
0 4
1
1 3
1
2 3 2
1
0 1
1
2 min 0
1
1 , 2
1
1 2
1
1 2
1
1 2
1
1 2
1
x
1
x x
1
x x
1
x x
1
2
3
4
5
В зависимости от вида f x x x
допустимого множества U
в ЗЛП может встретиться
только один из следующих
случаев:
  • РРооввнноо оодднноо рреешшее–
    ннииее;

• (^) ББеессккооннееччннооее ммнноо–
жжеессттввоо рреешшеенниийй;

  • ННеетт рреешшеенниийй,, так
    как ццееллееввааяя ффууннкк–
    цциияя ннееооггррааннииччееннннаа;;

• (^) ННеетт (^) рреешшеенниийй,, так
как ссииссттееммаа ооггррааннии–

ччеенниийй ппррооттииввооррее–

1
ччиивваа.

Ответ. Минимум в точке Xmin( 1 t) 2 ; 2 t 1 ; 4 , 0 t 1.

3.4 Симплекс - метод

1
Рассмотрим задачу линейного программирования вида
1
푍(푋)= с 0 +푐 1 푥 1 +푐 2 푥 2 +⋯+푐푛푥푛→푚푖푛 3
1
{

푎 11 푥 1 +푎 12 푥 2 +⋯+푎 1 푛푥푛=푏 1
푎 21 푥 1 +푎 22 푥 2 +⋯+푎 2 푛푥푛=푏 2

푎푚 1 푥 1 +푎푚 2 푥 2 +⋯+푎푚푛푥푛=푏푚
푥푗≥ 0 ,푗= 1 ,…,푛,
Здесь 푏푖≥ 0.
Если все ограничения системы заданы уравнениями и
переменные неотрицательные, то такая модель задачи линейно-
го программирования (ЗЛП) называется канонической.
Если хотя бы одно ограничение является неравенством,
то модель задачи не является канонической. Чтобы перейти от
неканонической модели к канонической, необходимо в каждое
неравенство ввести балансовую переменную. Если знак нера-
венства ≤, то переменная вводится со знаком плюс, если знак
неравенства ≥, то со знаком минус. В целевую функцию балан-
совые переменные не вводятся. Кроме того, если правая часть
какого-либо ограничения отрицательна, то нужно домножить
обе части данного ограничения на (-1).
Пусть ранг матрицы 퐴 равен 푟<푛. Без ограничения
общности, будем считать, что базисными переменными явля-
ются первые 푟 неизвестных 푥 1 ,푥 2 ,…,푥푟. Неизвестные
푥푟+ 1 ,푥푟+ 2 ,…,푥푛 будут свободными переменными.

1
2
3
Общее решение системы ограничений, которое можно
получить, например, с помощью метода Жордана-Гаусса, за-
пишется в виде
1
{
1
2
3
푥 1 =훽 1 −(훼 1 푟+ 1 푥푟+ 1 +⋯+훼 1 푗푥푗+⋯+훼 1 푛푥푛),
...
푥푟=훽푟−(훼푟,푟+ 1 푥푟+ 1 +⋯+훼푟푗푥푗+⋯+훼푟푛푥푛).
1
(5.3)
1
Целевая функция примет вид
1
2
3
4
5
6
7
8
푍(푋)=훾 0 −(훾푟+ 1 푥푟+ 1 +⋯+훾푗푥푗+⋯+훾푛푥푛)
Решение системы уравнений называется базисным. если
свободные переменные равны нулю.
Базисное решение системы уравнений называется допу-
стимым базисным , если базисные переменные неотрицатель-
ны.
Полученную ЗЛП будем называть стандартной фор-
мой записи допустимого базисного решения.
1
2
3
4
5
6
7
Идея симплекс - метода
ЗЛП со многими переменными не имеют такой ясной
геометрической интерпретации, как задачи с двумя перемен-
ными. Для решения таких задач можно использовать симплекс-
метод.
В основу симплекс-метода и многих его модификаций
лежат следующие принципы:
1
2
3
4
5
 Решение ЗЛП, если оно существует, всегда
находится на границе области допустимых решений
(ОДР).
 Если оптимальное решение единственно,
то оно всегда достигается в одной из вершин ОДР.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 Для того, чтобы найти оптимальное реше-
ние, достаточно перебрать все вершины многогранника и
выбрать ту, в которой целевая функция принимает опти-
мальное значение. Такие решения называют допустимы-
ми базисными решениями.
 Этап нахождения допустимых базисных
решений - координат вершин ОДР - является составной
частью любого алгоритма поиска оптимального решения.
 Алгоритм перебора допустимых решений
для поиска оптимума в симплекс-методе организуется
целенаправленно так, чтобы при переходе от одной вер-
шины к другой значение целевой функции не возрастало
(в задаче на минимум).
 Если на одном из этапов переход к сосед-
ним вершинам ОДР приводит к уменьшению (в задаче
на минимум) целевой функции, то поиск прекращается, а
найденное допустимое базисное решение является опти-
мальным.

Итак, симплекс-метод - это рациональный перебор до-
пустимых базисных решений системы, при котором целевая
функция, по крайней мере, не увеличивается.

Симплекс - таблица
При переходе от одного допустимого базисного решения
к другому удобно пользоваться так называемой симплекс-
таблицей
СП Своб.
член

푥푟+ 1 …^ 푥푗 …^ 푥푛
БП
푍 훾 0 훾푟+ 1 …^ 훾푗 …^ 훾푛
푥 1 훽 1 훼 1 ,푟+ 1 …^ 훼 1 푗 …^ 훼 1 푛

1
2
3
4
5
6
7
8
9
10
11
... ... ... ... ... ... ...
푥푖 훽푖 훼푖,푟+ 1 ...^ 훼푖푗 ...^ 훼푖푛
...... ... ... ... ... ...
푥푟 훽푟 훼푟,푟+ 1 ... 훼푟푗 ... 훼푟푛
Правило выбора генерального столбца: в строке 푍, не
считая свободного члена выбрать любое положительное число.
Если положительных чисел нет, решение оптимально.
Пусть 훾푗> 0.
Правило выбора генеральной строки: в столбце 푥푗
среди положительных чисел, не считая строки 푍, выбрать то,
для которого отношение к нему свободного члена
1
2
3
4
5
6
훽푖
훼푖푗^ мини-
мально. Выбор генерального столбца и генеральной строки од-
нозначно определяет генеральный элемент 훼푖푗.
Переход к новому допустимому базисному решению
осуществляется путем пересчета симплекс-таблицы
1
Правила пересчета симплекс - таблицы:
  1. 푥푖 и 푥푗 меняются местами.
  2. На месте генерального элемента пишется величина
    ему обратная.
  3. Все элементы генеральной строки (кроме генерально-
    го элемента) делятся на генеральный элемент.
  4. Все элементы генерального столбца (кроме генераль-
    ного элемента) делятся на генеральный элемент и берутся с
    противоположным знаком.
  5. Все остальные элементы пересчитываются по правилу
    прямоугольника
1
푦̃ 0 =
1
2
훾 0 훼푖푗−훾푗 훽푖
훼푖푗
1
,푦̃푘=
1
2
훾푘 훼푖푗−훾푗 훼푖푘
훼푖푗
1
훽̃푙=
1
2
훽푙훼푖푗−훼푙푗훽푖
훼푖푗
1
,훼̃푙푘=
1
2
훼푙푘훼푖푗−훼푙푗훼푖푘
훼푖푗
1
Порядок работы по симплекс - методу:
  1. Найти исходное допустимое базисное ре-
    шение в стандартном виде и заполнить симплекс-
    таблицу.
  2. Выбрать генеральный столбец. Если его
    выбрать нельзя, решение оптимально.
  3. Выбрать генеральный элемент, и гене-
    ральную строку. Если ее выбрать нельзя, задача реше-
    ний не имеет.
  4. Пересчитать симплекс-таблицу, получив.
    таким образом, новое оптимальное решение.
  5. Перейти к п.2.

Пример. Рассмотрим решение ЗЛП с помощью
симплекс-таблицы:

СП Своб. чл. (^) 푥 1 푥 2
БП
푍 0 3 2
푥 3 9 3 - 2
푥 4 25 2 5
В качестве генерального столбца возьмем столбец 푥 1 , а в
качестве генеральной строки - строку 푥 3. Перейдем к новому
допустимому базисному решению:
СП Своб.
чл.
푥 3 푥 2
Б
БП
푍 -^9 -^1
푥 1 3 1/3 2/
푥 4 19 - 2/3^ 19/^
В качестве генерального столбца возьмем столбец 푥 2 , а
в качестве генеральной строки - строку 푥 4. Перейдем к новому
допустимому базисному решению:
СП (^) Своб. чл.
БП 푥^3 푥^4
푍 - 21 - 1/19 - 3/
푥 1 5 5/19^ 2/^
푥 2 3 - 3/19 3/
Далее генеральный столбец выбрать нельзя, значит
решение оптимально.
опт =( 5 ; 3 ; 0 ; 0 ), 퐹 опт =− 21
Замечание. Для решения задачи на максимум достаточ-
но рассмотреть функцию 푍 1 (푋)=−푍(푋), которую следует ми-
нимизировать при заданных ограничениях. Соответственно,
(푍 1 )푚푎푥=−푍푚푖푛, и так как система ограничений одна и та же в
обоих случаях, то точка оптимума не изменяется при переходе
от одной задачи к другой, то есть (푋 1 )푚푎푥=푋푚푖푛.
Описанный выше пример показывает наличие значи-
тельной вычислительной трудоемкости, возникающей при ис-
пользовании симплекс-метода для решения ЗЛП даже с не-
большим количеством переменных и ограничений.
Рассмотрим еще один пример, который проиллюстри-
рует одно из слабых мест симплекс-метода - поиск начального
допустимого базисного решения.
Пример. Решить симплекс-методом ЗЛП:
푍(푋)= 3 푥 1 −푥 2 − 4 푥 3 →푚푖푛,
{
−푥 2 +푥 3 ≤ 1 ,
− 5 푥 1 +푥 2 +푥 3 = 2 ,
− 8 푥 1 +푥 2 + 2 푥 3 ≥ 3 ,
푥푗≥ 0 ,푗= 1 , 2 , 3.

Решение. Очевидно, что для начала необходимо добавив
две балансовые переменные, т.е. привести задачу к канониче-
скому виду:
푍(푋)= 3 푥 1 −푥 2 − 4 푥 3 →푚푖푛,

1
{
1
2
3
−푥 2 +푥 3 +푥 4 = 1 ,
− 5 푥 1 +푥 2 +푥 3 = 2 ,
− 8 푥 1 +푥 2 + 2 푥 3 −푥 5 = 3 ,
1
푥푗≥ 0 ,푗= 1 , 2 , 3.

Используя метод Жордана-Гаусса, приведем систему
ограничений задачи к равносильной разрешенной системе
уравнений, сохранив правые части уравнений неотрицательны-
ми. Для этого п роведем элементарные матричные преобразо-
вания расширенной матрицы системы ограничений. Исходная
матрица имеет вид.

1
(
1
2
3
0 − 1 1 1 0
− 5 1 1 0 0
− 8 1 2 0 − 1
1
|
1
2
3
1
2
3
1
).

Очевидно, что переменная 푥 4 уже выбрана как базисная.
Следующей такой переменной выберем переменную 푥 2. Для
этого к первой строке прибавим вторую, к третьей строке при-
бавим вторую с противоположным знаком. Получим матрицу

1
(
1
2
3
− 5 0 2 1 0
− 5 1 1 0 0
− 3 0 1 0 − 1
1
|
1
2
3
3
2
1
1
).

Имеем уже две базисных переменных 푥 2 и 푥 4. Послед-
ней базисной переменной станет 푥 3 после того, как к первой
строке прибавим третью, умноженную на (-2), а ко второй тре-
тью, умноженную на (-1). Получим матрицу

1
(
1
2
3
1 0 0 1 0
− 2 1 0 0 0
− 3 0 1 0 − 1
1
|
1
2
3
1
1
1
1
),
1
которой соответствует система уравнений
1
{
1
2
3
4
5
6
7
8
9
10
11
푥 2 = 1 + 2 푥 1 ,
푥 3 = 1 + 3 푥 1 +푥 5 ,
푥 4 = 1 −푥 1.
Имеем три базисных переменных 푥 2 , 푥 3 и 푥 4 , и две сво-
бодных 푥 1 и 푥 5.
Выразим целевую функцию через свободные перемен-
ные
푍(푋)= 3 푥 1 −푥 2 − 4 푥 3 = 3 푥 1 −( 1 + 2 푥 1 )− 4 ( 1 + 3 푥 1 +푥 5 )
=− 5 − 11 푥 1 − 4 푥 5
Запишем начальное допустимое базисное решение в
стандартной форме:
1
{
1
2
3
푥 2 = 1 −(− 2 푥 1 ),
푥 3 = 1 −(− 3 푥 1 −푥 5 ),
푥 4 = 1 −(푥 1 ),
1
푥푗≥ 0 ,푗= 1 , 2 , 3 , 4 , 5
1
2
3
4
5
6
7
8
푍(푋)=− 5 −( 11 푥 1 + 4 푥 5 )→푚푖푛
или
푋 1 =( 0 ; 1 ; 1 ; 1 ; 0 ), 푍(푋 1 )=− 5.
Так как в скобках у целевой функции есть положитель-
ные коэффициенты, то найденное решение можно улучшить.
Составим симплекс-таблицу и выберем генеральный элемент:
СП Своб.
чл.
1
2
3
4
5
6
7
8
9
10
11
푥 1 푥 5
БП
푍 -^5 11
푥 2 1 - 2 0
푥 3 1 -^3 -^1
푥 4 1 1 0
Произведем пересчет таблицы, поменяв роли перемен-
ных 푥 1 и 푥 4.
Новая таблица примет вид
СП Своб.
чл.
1
2
3
푥 4 푥 5
БП
푍 - 16 - 11 4

푥 2 3 2 0
푥 3 4 3 - 1
푥 1 1 1 0
В последней таблице в строке 푍 имеется положительный
элемент, то есть генеральный столбец выбрать можно, но в
этом столбце нет ни одного положительного элемента, а это
значит, что генеральную строку, а следовательно, и генераль-
ный элемент выбрать нельзя. Найденное решение и является
оптимальным. Запишем его.

1
{
1
2
3
푥 1 = 1 −(푥 4 ),
푥 2 = 3 −( 2 푥 4 ),
푥 3 = 4 −( 3 푥 4 −푥 5 ),
1
푥푗≥ 0 ,푗= 1 , 2 , 3 , 4 , 5

푍(푋)=− 16 −(− 11 푥 4 + 4 푥 5 )→푚푖푛
или
Xmin=( 1 ; 3 ; 4 ), Zmin=− 16.
В векторе Xmin исключены неизвестные 푥 4 и 푥 5 , так как
их не было в исходной формулировке задачи.
Можно заметить, что в этой задаче наиболее трудоем-
ким оказался этап поиска начального допустимого базисного
решения. Иногда это решение найти весьма проблематично.
Это одна из главных проблем симплекс-метода.

Задача. Решите задачу линейного программирования сим-
плекс-методом

푍(푋)=푥 1 −푥 2 + 3 푥 3 −푥 4 →푚푎푥.

{
−푥 1 + 2 푥 2 +푥 3 = 2 ,
3 푥 1 − 2 푥 2 +푥 4 = 6 ,
푥푗≥ 0 , 푗= 1 ,…, 4
Ответ. Максимум в точке (2;0;4;0), значение функции в точке
максимума равно 14.

Задача. Решите задачу линейного программирования сим-
плекс-методом

1
2
3
4
5
6
7
8
푍(푋)=푥 1 + 5 푥 2 +푥 3 −푥 4 →푚푎푥.
{
푥 1 + 2 푥 2 +푥 3 = 3 ,
2 푥 1 +푥 2 +푥 4 = 4 ,
푥푗≥ 0 , 푗= 1 ,..., 4
Ответ. Максимум в точке
Xmin( 1 t) 0 ; 3 / 2 ; 0 ; 5 / 2 t 5 / 3 ; 2 / 3 ; 0 ; 0 , 0 t 1 , значение
функции в точке максимума равно 5.
1
2
3
4
Задача. Решите задачу линейного программирования сим-
плекс-методом
푍(푋)=− 4 푥 1 − 2 푥 2 +푥 3 →푚푖푛.
{
1
2
3
4
5
3 푥 1 − 2 푥 2 + 4 푥 3 ≤ 6 ,
2 푥 1 +푥 2 + 3 푥 3 ≤ 18 ,^
푥푗≥ 0 , 푗= 1 , 2 , 3
Ответ. Минимум в точке Xmin( 1 t) 0 ; 18 ; 0 t 6 ; 6 ; 0 , 0 t 1 ,
значение функции в точке минимума равно -36.
1
2
3
Задача. Решите задачу линейного программирования сим-
плекс-методом
푍(푋)=푥 1 + 2 푥 2 +푥 3 →푚푎푥.
1
{
1
2
3
4
5
− 2 푥 1 +푥 2 +푥 3 ≤ 2 ,
−푥 1 +푥 2 + 3 푥 3 ≤ 3 ,
푥 1 − 3 푥 2 +푥 3 ≤ 1 ,
푥푗≥ 0 , 푗= 1 , 2 , 3
Ответ. Функция неограниченно возрастает.

3.5 М - метод (метод искусственного базиса.

Пусть требуется решить КЗЛП (каноническую задачу
линейного программирования) вида
푍(푋)=с 0 +푐 1 푥 1 +푐 2 푥 2 +⋯+푐푛푥푛→min

1
{

푎 11 푥 1 +푎 12 푥 2 +⋯+푎 1 푛푥푛=푏 1
푎 21 푥 1 +푎 22 푥 2 +⋯+푎 2 푛푥푛=푏 2

푎푚 1 푥 1 +푎푚 2 푥 2 +⋯+푎푚푛푥푛=푏푚
푥푗≥ 0 ,푗= 1 ,…,푛,

где кроме того все 푏푖≥ 0.
При решении этой задачи возникает трудность нахожде-
ния исходного допустимого базисного решения. Для того что-
бы обойти эту трудность воспользуемся так называемым М-
методом.
Запишем систему уравнений в виде

1
{

푏 1 −(푎 11 푥 1 +푎 12 푥 2 +⋯+푎 1 푛푥푛)= 0 ,
푏 2 −(푎 21 푥 1 +푎 22 푥 2 +⋯+푎 2 푛푥푛)= 0 ,

푏푚−(푎푚 1 푥 1 +푎푚 2 푥 2 +⋯+푎푚푛푥푛)= 0.
Наряду с исходной КЗЛП рассмотрим вспомогательную
КЗЛП

1
{

푏 1 −(푎 11 푥 1 +푎 12 푥 2 +⋯+푎 1 푛푥푛)=휉 1 ,
푏 2 −(푎 21 푥 1 +푎 22 푥 2 +⋯+푎 2 푛푥푛)=휉 2 ,

푏푚−(푎푚 1 푥 1 +푎푚 2 푥 2 +⋯+푎푚푛푥푛)=휉푚.
푥푗≥ 0 ,푗= 1 ,…,푛, 휉푖≥ 0 ,푖= 1 ,…,푚.
В качестве целевой функции возьмем
퐺(푋)=с 0 +푐 1 푥 1 +푐 2 푥 2 +⋯+푐푛푥푛
+푀(휉 1 +휉 2 +⋯+휉푚)→푚푖푛,
где М – некоторое достаточно большое число. Эту
КЗЛП назовем М-задачей.

1
2
3
4
5
6
7
8
9
Очевидно, что последняя задача уже является стандарт-
ной записью исходного допустимого базисного решения, так
как 푥푗,푗= 1 ,...,푛 - свободные переменные, а 휉푖,푖= 1 ,...,푚 -
базисные переменные, причем 휉푖=푏푖≥ 0 ,푖= 1 ,...,푚 по усло-
вию
Переменные 휉푖,푖= 1 ,...,푚 иногда называют искус-
ственным базисом.
При решении М-задачи симплекс-методом могут быть
два варианта:
  1. 푀 - задача имеет решение.
  2. 푀 - задача не имеет решения.
    В соответствии с этими вариантами рассмотрим Следу-
    ющие утверждения:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Теорема 1. Если 푀 - задача имеет оптимальное решение ,
в котором 휉푖= 0 ,푖= 1 ,...,푚, то и исходная задача имеет опти-
мальное решение. при этом минимальные значения целевых
функций равны.
Теорема 2. Если 푀 - задача имеет оптимальное решение,
в котором хотя бы одна из неизвестных 휉푖≠ 0 , то исходная за-
дача противоречива.
Теорема 3. Если 푀 - задача не имеет оптимального ре-
шения, то и исходная задача не имеет оптимального решения.
Замечание. Если в процессе решения 푀 - задачи сим-
плекс-методом переменная 휉푖 перешла из базисных неизвест-
ных в свободные, нет смысла возвращать ее из свободных не-
известных в базисные. Поэтому эту переменную можно исклю-
чить, так как она свою роль отыграла.
1
2
Пример. Решить ЗЛП М-методом:
{
1
2
3
4
푥 1 −푥 2 + 4 푥 3 − 2 푥 4 = 1 ,
2 푥 1 +푥 2 + 5 푥 3 −푥 4 + 3 푥 5 = 5 ,
푥푗≥ 0 ,푗= 1 ,..., 5 ,
푍(푋)= 5 − 2 푥 1 +푥 2 − 6 푥 3 + 5 푥 4 →푚푖푛.

Решение. Составим М-задачу и запишем ее базисное
решение в стандартном виде.

1
{
1
2
3
휉 1 = 1 −(푥 1 −푥 2 + 4 푥 3 − 2 푥 4 ),
휉 2 = 5 −( 2 푥 1 +푥 2 + 5 푥 3 −푥 4 + 3 푥 5 ),
푥푗≥ 0 ,푗= 1 ,..., 5 , 휉푖≥ 0 ,푖= 1 , 2
1
2
퐺(푋)=푍(푋)+푀(휉 1 +휉 2 )→푚푖푛
или
1
2
퐺(푋)= 5 −( 2 푥 1 −푥 2 + 6 푥 3 − 5 푥 4 )
+푀( 6 −( 3 푥 1 + 9 푥 3 − 3 푥 4 + 3 푥 5 ))→푚푖푛
1
Составим симплекс-таблицу
1
2
СП^ Своб.
чл.
1
2
3
4
5
6
푥 1 푥 2 푥 3 푥 4 푥 5
БП
푍 5 2 - 1 6 - 5 0
푀 6 3 0 9 - 3 3
휉 1 1 1 -^1 4 -^2 0
휉 2 5 2 1 5 - 1 3

Так как 푀 - сколь угодно большое положительное число,
генеральный столбец выбираем по строке 푀, т.е. любое поло-
жительное число, не считая свободного члена в строке 푀.
Выберем столбец 푥 1. В качестве генеральной строки

возьмем строку 휉 1 так как
1
1 <

5
2. Переменная 푥^1 становится ба-
зисной, а переменная 휉 1 - свободной. Ее мы опускаем (то есть
столбец 푥 1 исчезает). Все элементы генеральной строки делятся
на генеральный элемент, а остальные элементы таблицы пере-
считываются по правилу прямоугольника.
Получаем новую симплекс-таблицу:

СП^ Своб. чл. (^) 푥 2 푥 3 푥 4 푥 5
БП
푍 3 1 -^2 -^1 0
푀 3 3 -^3 3 3
푥 1 1 - 1 4 - 2 0
휉 2 3 3 -^3 3 3
Выберем теперь в качестве генерального столбца стол-
бец 푥 2 , который исчезает, а в качестве генеральной строки -
строку 휉 2. Строка 푀 обнуляется, и мы ее опускаем.
СП^ Своб. чл. 푥 3 푥 4 푥 5
БП
푍 2 - 1 - 2 - 1
푥 1 2 3 -^1 1
푥 2 1 - 1 1 1
Далее генеральный столбец выбрать нельзя, поэтому
решение оптимально.
Следовательно, оптимальное решение: 푋 опт =
( 2 ; 1 ; 0 ; 0 ; 0 ), 푍 опт = 2.
Пример. (случай несовместности системы ограничений)
Решить КЗЛП М-методом:
{
푥 1 + 6 푥 2 −푥 3 +푥 4 =− 5 ,
3 푥 1 − 2 푥 2 +푥 3 −푥 4 = 1 ,
푥푗≥ 0 ,푗= 1 ,…, 4 ,
푍(푋)=푥 1 −푥 2 −푥 3 +푥 4 →푚푖푛.
Решение. Составим М-задачу и запишем ее базисное
решение в стандартном виде.
{
휉 1 = 5 −(−푥 1 − 6 푥 2 +푥 3 −푥 4 ),
휉 2 = 1 −( 3 푥 1 − 2 푥 2 +푥 3 −푥 4 ),
푥푗≥ 0 ,푗= 1 ,…, 4 , 휉푖≥
0 ,푖= 1 , 2
퐺(푋)=푍(푋)+푀(휉 1 +휉 2 ) →푚푖푛

1
2
3
4
или
퐺(푋)= 0 −(−푥 1 +푥 2 +푥 3 −푥 4 )
+푀( 6 −( 2 푥 1 − 8 푥 2 + 2 푥 3 − 2 푥 4 ))→푚푖푛
Составим симплекс-таблицу

СП^ Своб. чл. (^) 푥 1 푥 2 푥 3 푥 4
БП
푍 0 -^1 1 1 -^1
푀 6 2 - 8 2 - 2
휉 1 5 -^1 -^6 1 -^1
휉 2 1 3 - 2 1 - 1
В качестве генерального столбца возьмем столбец 푥 3 а в
качестве генеральной строки - строку 휉 2 и пересчитаем сим-
плекс-таблицу. Получим
СП^ Своб. чл. (^) 푥 1 푥 2 푥 4
БП
푍 - 1 - 4 3
푀 4 -^4 -^4 0
휉 1 4 - 4 - 4 0
푥 3 1 3 -^2 -^1
Генеральный столбец выбрать нельзя, так как в строке 푀
все элементы (кроме свободного члена) неположительны. По-
этому решение М-задачи оптимально. Получили 푥 1 = 0 ,푥 2 = 0 ,
푥 3 = 1 , 푥 4 = 0 , 휉 1 = 4 , 휉 2 = 0.
C другой стороны, так как 휉 1 ≠ 0 , то исходная задача не
имеет решений.
Задача. Решите задачу линейного программирования М-
методом
푍(푋)=− 2 푥 1 +푥 2 + 8 푥 3 − 2 푥 4 →푚푖푛.
{
5 푥 1 −푥 2 − 7 푥 3 + 2 푥 4 = 6 ,
3 푥 1 −푥 2 − 4 푥 3 +푥 4 = 2 ,^
푥푗≥ 0 , 푗= 1 ,…, 4
Ответ. Минимум в точке (0;2;0;4), значение функции в точке
минимума равно -6.
Задача. Решите задачу линейного программирования М-
методом
푍(푋)= 2 푥 1 + 8 푥 2 + 3 푥 3 + 4 푥 4 →푚푖푛.
{
13 푥 1 − 3 푥 2 + 2 푥 3 − 7 푥 4 = 4 ,
7 푥 1 − 2 푥 2 +푥 3 − 4 푥 4 = 1 ,
푥푗≥ 0 , 푗= 1 ,…, 4
Ответ. Минимум в точке Xmin( 1 t) 1 ; 3 ; 0 ; 0 t 3 ; 0 ; 0 ; 5 , 0 t 1 ,
значение функции в точке минимума равно 26.
Задача. Решите задачу линейного программирования М-
методом
푍(푋)= 3 푥 1 + 2 푥 2 − 2 푥 3 + 3 푥 4 +푥 5 →푚푎푥.
{
푥 1 −푥 2 +푥 3 −푥 4 = 2 ,
−푥 1 +푥 2 + 2 푥 3 +푥 5 = 4 ,
2 푥 1 −푥 3 +푥 4 +푥 5 = 4
푥푗≥ 0 , 푗= 1 ,…, 5
Ответ. Максимум в точке (3;3;2;0;0), значение функции в точке
максимума равно 11.
Задача. Решите задачу линейного программирования М-
методом
푍(푋)= 2 푥 1 + 6 푥 2 +푥 3 +푥 4 →푚푎푥.
{
4 푥 1 − 5 푥 2 − 2 푥 3 +푥 4 = 6 ,
− 5 푥 1 + 4 푥 2 +푥 3 −푥 4 = 1 ,
푥푗≥ 0 , 푗= 1 ,…, 4

Ответ. Система ограничений несовместна.

3.6 Использование надстройки “Поиск решения” MS
Excel для решения задачи линейного программиро-
вания.

Стандартный метод решения задачи линейного программиро-
вания – так называемый симплекс-метод.

При не очень большом количестве переменных можно исполь-
зовать надстройку “Поиск решения” из MS Excel (см. 2.5 выше)

Типовая задача.
Цех может выпускать два вида продукции: шкафы и тумбы для
телевизора.
На каждый шкаф расходуется 3,5 м стандартных ДСП, 1 м ли-
цевого стекла и 1 человеко-день трудозатрат. На тумбу -1м
ДСП, 2 м стекла и 1 человеко-день трудозатрат. Прибыль от
продажи 1 шкафа составляет 200 у. е., а 1 тумбы -100 у е.
Материальные и трудовые ресурсы ограниченны: в цехе рабо-
тают 150 рабочих, в день нельзя израсходовать больше 350 м
ДСП и более 240 м стекла.
Какое количество шкафов и тумб должен выпускать цех, чтобы
сделать прибыль максимальной?

Решение.

1. Формализуем задачу (составим математическую модель
данной ситуации).

1
2
Переменные решения Целевая функция
x 1 - количество шкафов
1
x 2 - количество тумб, произ-

водимых ежедневно

1
P 200 x 1  100 x 2 max
1
Ежедневная прибыль цеха
1
Ограничения
1
2


1
2


1

1
 
1
 
1
 
1
150
1
2 240
1
3 , 5 350
1
1 2
1
1 2
1
1 2
1
x x
1
x x
1
x x
1
x 1 ,x 2  0

2. Организуем данные на листе MS-Excel так, как это пока-
зано на рис.
3. Выберем пункт меню “Сервис” “Поиск решения”. По-
явится окно, озаглавленное поиск решения:

а). В поле окна “ Установить целевую ячейку “ отметим ячейку
B13;

б). Установим переключатель на отметке “ Равной максималь-
ному значению
“;

в). В поле окна “ Изменяя ячейки “ отметим ячейки B11:C11;

г). Добавим ограничения, щелкая по кнопке “ Добавить “.

В появившемся окне “ Добавление ограничения “, щелкнем в по-
ле “Ссылка на ячейку”, а затем отметим ячейки B16:B18, выбе-
рем знак ограничения и отметим ячейки D16:D18, содержащие
ограничения по ресурсам.

4. Щелкнем по кнопке “Параметры”.
Появится окно “ Параметры поиска решения “, в котором можно
(но не нужно) менять многочисленные параметры.

1
2
3
4
Нас интересует, установлены ли флажки " Линейная модель " и
" Неотрицательные значения " (ограничения x 1 ,x 2  0 устанав-
ливаются здесь). Если нет, установим их, щелкнем по кнопке
Оk и вернемся к окну " Поиск решения ".

5. Щелкнем по кнопке “Выполнить”.
Оптимизационная программа MS-Excel выполнит поиск реше-
ния, после чего появится окно “ Результаты поиска решения “.

Прочтите сообщение программы в этом окне. Если все сделано
правильно, программа сообщит: “Решение найдено. Все огра-
ничения и условия оптимальности выполнены”.

Вид листа MS-Excel, соответствующий оптимальному реше-
нию, показан на рис.

  1. Убедимся, что переключатель в окне “ Результаты поиска
    решения
    “ находится в положении “ Сохранить найденное значе-
    ние
    “, щелкнем по кнопке Ok и прочтем ответ в ячейках
    B11:C11. В ячейках D16:D18 содержатся значения ресурсов,
    которые необходимы для получения оптимального плана.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"Значения целевой ячейки не сходятся" или
"Поиск не может найти решения" или
"Условия линейной модели не выполняются".
Ответ. При производстве 80 шкафов и 70 тумб в день достига-
ется максимум прибыли, равный 23000 у.е.
Задача.
При составлении суточного рациона кормления скота можно
использовать свежее сено (не более 50 кг) и силос не более 85
кг. Рацион должен обладать определенной питательностью
(число кормовых единиц не менее 30) и содержать питательные
вещества: белок (не менее 1 кг), кальций (не менее 100 г) и
фосфор (не менее 80 г). Определить оптимальный рацион из
условия минимума себестоимости.
Данные о содержании указанных компонентов в 1 кг каждого
продукта питания и о себестоимости этих продуктов приведены
в таблице:
Про-
дукт
1
2
3
4
Кол - во
кормо-
вых
единиц
1
2
3
Бе-
лок,
г/кг
1
2
3
Каль-
ций,
г/кг
1
2
3
Фос-
фор,
г/кг
1
2
Себестои-
мость, у.е./кг
1
2
Сено
свежее
1
0,5 40 1,25 2 1,2
1
2
3
4
5
6
Силос 0,5 10 2,5 1 0,8
Ответ. Сено 20 кг, силос 40 кг.
Задача.
Предприятие выпускает три вида крепежных изделий: болты,
гайки и шайбы. Нормы расхода сырья, времени работы обору-
дования и затарат электроэнергии, которые необходимы для

производства одной тонны каждого изделия, приведены в
табл.4.
Месячные запасы ресурсов, которыми располагает предприя-
тие, ограничены. По сырью эти ограничения обусловлены ем-
костью складских помещений, по оборудованию – станочным
парком и трудовыми ресурсами, по электроэнергии – техниче-
скими и финансовыми причинами. Размеры запасов и доход от
реализации продукции в у.е. за 1 тонну приведены в таблице.

Ресурсы

1
2
3
4
5
6
7
Нормы расхода ресурсов на
тонну продукции
Ограничения
по ресурсам
Шайбы
Гайки
Болты

Сырье 5 8 11 330
Оборудование 4 6 10 270
Электроэнергия 5 7 9 250
Доход (у.е./т) 90 140 200
Помимо запасов на формирование программы влияет необхо-
димость выполнения контрактных обязательств: предприятие
должно обеспечить поставку шайб в количестве 4 т, гаек – в
количестве 2 т, болтов – в количестве 3 т.
Требуется сформировать месячную производственную про-
грамму (определить объемы выпуска каждого вида продукции),
при которой доход от реализации будет максимальным.

Ответ. 12,77 т шайб, 4,82 т гаек, 0,41 т болтов.

Задача.
Частный инвестор предполагает вложить 500 тыс. руб. в раз-
личные ценные бумаги. После консультаций со специалистами
фондового рынка он отобрал 3 типа акций, 2 типа государ-
ственных облигаций. Часть денег предполагается положить на
срочный вклад в банк.
Тип вложе- Риск Предпола-

1
2
3
4
5
6
7
8
9
10
11
ния гаемый ежегод-
ный доход, %
Акции A Высокий 15
Акции B Средний 12
Акции C Низкий 9
Облигации долгосрочные 11
Облигации краткосрочные 8
Срочный вклад 6
Имея в виду качественные соображения диверсификации порт-
феля и неформализуемые личные предпочтения, инвестор вы-
двигает следующие требования к портфелю ценных бумаг:
  • все 500 тыс. руб. должны быть инвестированы;
  • по крайней мере 100 тыс. руб. должны быть на сроч-
    ном вкладе в любимом банке;
  • по крайней мере 25% средств, инвестированных в ак-
    ции, должны быть инвестированы в акции с низким риском;
  • в облигации нужно инвестировать по крайней мере
    столько же, сколько в акции;
  • не более чем 125 тыс. руб. должно быть вложено в бу-
    маги с доходом менее чем 10%.
    Определить портфель бумаг инвестора, удовлетворяющий всем
    требованиям и максимизирующий годовой доход. Какова вели-
    чина этого дохода?

Ответ. 150 тыс. руб. - в акции А, 50 тыс. руб. - в акции С, 200
тыс. руб. - в долгосрочные облигации, 100 тыс. руб. - срочный
вклад в банке.
Задача.
Фермер имеет 150 га земель в одной из южных областей и в
предстоящем сезоне собирается выращивать пшеницу, кукуру-
зу, овес и сою. В таблице представлены данные о величине
ожидаемого урожая, финансовых и трудовых затратах, расходе

минеральных удобрений и предполагаемых ценах на выращен-
ное зерно.
Тип
зерна

1
2
3
4
Ожидае-
мая уро-
жайность
(ц/га)
1
2
3
Труд
(час./га
)
1
2
3
4
Из-
держки
(руб./га
)
1
2
3
Удоб-
рения
(ц/га)
1
2
3
Ожидаемая
цена
(руб./ц)

Пшени-
ца

1
21 8 1000 4 160

Кукуру-
за

1
30 10 1500 12 128

Овес 18 6 600 2 73
Соя 24 20 1200 8 155
Основываясь на анализе прошлогоднего рынка зерновых, фер-
мер хочет произвести не менее 150 ц пшеницы и не менее 150 ц
кукурузы, но не более 125 ц овса. Он располагает 250 тыс. руб.
для покрытия издержек, связанных с обработкой и уходом за
полями, и планирует работать 12 ч в день в течение 150-
дневного сезона. Он также не хочет перерасходовать имею-
щийся у него с прошлого года запас минеральных удобрений в
120 т.
Какое количество гектаров земли фермер должен отвести под
каждую зерновую культуру, чтобы максимизировать прибыль
от предполагаемого урожая?

Ответ. 95,8 га пшеницы, 5 га кукурузы, 49, 2 га сои, прибыль
составит 361766,7 руб.
Задача.
Большой универсальный магазин собирается заказать новую
коллекцию костюмов для весеннего сезона. Решено заказать 4
типа костюмов. Три типа - это костюмы широкого потребления:
(1) костюмы из полиэстровых смесей, (2) шерстяные костюмы
и (3) костюмы из хлопка. Четвертый тип - это дорогие импорт-
ные модельные костюмы из различных тканей. Имеющийся у
менеджеров магазина опыт и специальные исследования позво-

1
2
3
4
5
6
7
ляют оценить средние затраты рабочего времени продавцов на
продажу одного костюма каждого типа, количество средств на
рекламу и площадей в расчете на один костюм каждого типа.
Все эти данные, а также прибыль от продажи одного костюма
каждого типа представлены в таблице.
Тип ко-
стюма
1
2
3
4
Прибыль
на один ко-
стюм,
долл.
1
2
3
4
Рабочее
время
продав-
цов
1
2
3
4
Затраты на
рекламу на
один ко-
стюм
1
2
3
4
5
6
Площадь
на один ко-
стюм (кв.
фут)
Полиэс-
тер
1
35 0,4 $2 1,00
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Шерсть 47 0,5 $4 1,5
Хлопок 30 0,3 $3 1,25
Импорт 90 1,0 $9 3,00
Предполагается, что весенний сезон будет длиться 90 дней. Ма-
газин открыт 10 часов вдень, 7 дней в неделю. Два продавца
постоянно будут в отделе костюмов. Выделенная отделу ко-
стюмов площадь составляет прямоугольник 100*60 футов.
Бюджет, выделенный на рекламу всех костюмов на весенний
сезон, составляет 15 тыс. долл.
Сколько костюмов каждого типа нужно закупить, чтобы мак-
симизировать прибыль?
Ответ. 33 костюма из полиэстера, 2535 шерстяных костюма,
1731 костюм из хлопка, 0 импортных костюмов. Прибыль со-
ставит 172230$.
Задача. Из пункта А в пункт В ежедневно отправляются ско-
рые и пассажирские поезда. Наличный парк вагонов разных ти-
пов, из которых ежедневно можно комплектовать данные поез-
да, и число пассажиров, вмещающихся в каждом из вагонов,
приведены ниже:
Вагон Число вагонов в поезде Число пас- Парк
1
2
3
Скором Пассажирском сажиров^ вагонов^
Багажный 1 1 - 12
Почтовый 1 - - 8

Плацкартный 5 8 58 81

Купейный 6 4 40 70
Мягкий 3 1 32 26
Определить:
а). количество скорых и пассажирских поездов, при которых
число перевозимых пассажиров достигнет максимума;
б). оптимальное количество поездов для случая, когда железная
дорога не может пропустить более шести пассажирских поез-
дов.
Ответ. а). 5 скорых и 7 пассажирских; б). 6 скорых и 6 пасса-
жирских.

3.7 Транспортная задача в матричной форме

3.7.1 Постановка задачи.

Пусть имеется 푛 станций отправления 퐴 1 ,…,퐴푛, на ко-
торых сосредоточены объемы груза 푎 1 ,…,푎푛 и 푚 станций
назначения 퐵 1 ,…,퐵푚, на которых есть потребность в этих гру-
зах 푏 1 ,…,푏푚, причем сумма запасов груза равна сумме потреб-
ности в них, т.е.

1
∑푎i
1

1
푖= 1
1
=∑푏j
1

1
j= 1
1
.

Известна стоимость перевозки единицы груза 푐푖푗 со
станции 퐴푖 на станцию 퐵푗. Требуется так спланировать объемы

перевозок 푥푖푗 со станции 퐴푖 на станцию 퐵푗, чтобы все запасы

1
2
3
4
5
6
7
8
9
10
были бы вывезены, все потребности удовлетворены и суммар-
ная стоимость перевозок была бы минимальной.
Сведем все данные в таблицу
퐵 1 ... 퐵푗 ... 퐵푚 푥 11 ... 푥 1 푗 ... 푥 1 푚 푎 1
퐴 1 푐 11 ... 푐 1 푗 ... 푐 1 푚 ⋮ ... ⋮ ... ⋮ ⋮
⋮ ⋮ ... ⋮ ... ⋮ 푥푖 1 ... 푥푖푗 ... 푥푖푚 푎푖
퐴푖 푐푖 1 ... 푐푖푗 ... 푐푖푚 ⋮ ... ⋮ ... ⋮ ⋮
⋮ ⋮ ... ⋮ ... ⋮ 푥푛 1 ... 푥푛푗 ... 푥푛푚 푎푛
퐴푛 푐푛 1 ... 푐푛푗 ... 푐푛푚 푏 1 ... 푏푗 ... 푏푚
Математическая модель транспортной задачи имеет вид:
1
푍(푋)=∑∑푐푖푗푥푖푗
1

1
푗= 1
1

1
푖= 1
1
→min
1
{
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
푥 11 +푥 12 +⋯+푥 1 푚=푎 1
...
푥푛 1 +푥푛 2 +⋯+푥푛푚=푎푛
푥 11 +푥 21 +⋯+푥푛 1 =푏 1
...
푥 1 푚+푥 2 푚+⋯+푥푛푚=푏푚
푥푖푗≥ 0 ∀푖,푗
Если условие баланса ∑푛푖= 1 푎i=∑푚j= 1 푏j выполняется, то
транспортная задача называется сбалансированной , в против-
ном случае – несбалансированной. Поскольку ограничения
модели могут быть выполнены только при сбалансированной
транспортной задаче, то при построении транспортной модели
необходимо проверять условие баланса. В случае, когда сум-
марные запасы превышают суммарные потребности , необхо-
дим дополнительный фиктивный пункт потребления, который
будет формально потреблять существующий излишек запасов,
то есть
1
푏ф=∑푎i
1

1
푖= 1
1
−∑푏j
1

j= 1
Если суммарные потребности превышают суммарные
запасы
, то необходим дополнительный фиктивный пункт от-
правления, формально восполняющий существующий недоста-
ток продукции в пунктах отправления:

1
푎ф=∑푏j
1

1
j= 1
1
−∑푎i
1

푖= 1
Введение фиктивного потребителя или отправителя по-
влечет необходимость формального задания фиктивных тари-

фов 푐푖푗ф (реально не существующих) для фиктивных перевозок.

Расходы 푐푖푗ф по доставке груза до фиктивного потребителя или

фиктивного поставщика равны нулю, так как груз фактически
не перевозится.

3.7.2 Решение транспортной задачи методом потенциа-
лов.

1
2
Алгоритм решения транспортной задачи методом
потенциалов
  1. Найти исходное допустимое базисное ре-
    шение. число базисных (заполненных) клеток должно
    быть равно 푚+푛− 1. Если их оказалось меньше поста-
    вить недостающее число нулей с учетом того, что не
    должно существовать цикла, все вершины которого ле-
    жат в базисных клетках.
  2. Найти потенциалы из системы уравнений
    푢푖−푣푗=푐푖푗 для базисных клеток.
  3. Найти свободную клетку, для которой не
    выполняется неравенство
    푢푖−푣푗≤푐푖푗.
    Если таких клеток нет, то решение оптимально.
  4. Для найденной свободной клетки постро-
    ить цикл ее пересчета и осуществить сдвиг по нему на
    величину, равную минимальному объему перевозки в
    отрицательных вершинах цикла. Построить новую таб-
    лицу перевозок. Если клеток с минимальным объемом
    несколько, то только одну из них перевести в разряд
    свободных. Остальные оставить среди базисных с нуле-
    вым объемом перевозки.
  5. См. п.2.
1
2
Пример. Решить транспортную задачу методом потен-
циалов:
1
퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
1
2
3
퐴 1
10 9 8 5 3
100
1
2
3
퐴 2
4 7 13 6 2
150
1
2
3
퐴 3
8 6 9 7 1
90
1
2
3
퐴 4
5 4 7 9 2
30
1
40 80 110 50 90
1
2
3
Решение.
Так как ∑^4 푖= 1 푎i= 100 + 150 + 90 + 30 = 370 и
∑^5 j= 1 푏j= 40 + 80 + 110 + 50 + 90 = 370 , то данная транс-

портная задача является сбалансированной. Следовательно, до-
бавлять фиктивного потребителя или фиктивного поставщика
не требуется.

Шаг 1. Построение опорного плана
Опорным, называется любой допустимый базисный,
как правило, не оптимальный план, который является исход-
ным для последующего решения. Для построения опорного
плана существует ряд методов. Самый простой из них – метод
северо-западного угла.

1
Метод северо - западного угла

Берем «северо-западную» клетку матрицы – это клетка
퐴 1 퐵 1 и записываем в нее максимально возможную поставку – 40
т (объем выгрузки 40 т, ресурсы станции отправления 100т). По-
скольку ресурсы станции отправления 퐴 1 не исчерпаны, следуем
по первой строке вправо и записываем в клетку 퐴 1 퐵 2 макси-
мально возможный объем перевозки – 60 т. Таким образом по-
лучается, что ресурсы станции 퐴 1 полностью использованы, од-
нако спрос станции назначения 퐵 2 не удовлетворен. Тогда от
клетки 퐴 1 퐵 2 опускаемся вниз до клетки 퐴 2 퐵 2 и записываем в нее
поставку равную 20 т. Описанным способом следуем далее до
последней «юго-западной» клетки матрицы. В результате полу-
чаем допустимый базисный план перевозок груза.
퐵 1 퐵 2 퐵 3 퐵 4 퐵 5

1
2
3
4
퐴 1
10 9 8 5 3
100
40 60
1
2
3
4
5
퐴 2
4 7 13 6 2
150
20 110 20
퐴 3 8 6 9 7 1 90
1
30 60
1
퐴 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
5 4 7 9 2
30
30
40 80 110 50 90
В результате получаем допустимый базисный план пе-
ревозок груза. Стоимость перевозки составит:
푍С−З= 10 ⋅ 40 + 9 ⋅ 60 + 7 ⋅ 20 + 13 ⋅ 110 + 6 ⋅ 20 + 7 ⋅ 30 + 1
⋅ 60 + 2 ⋅ 30 = 2960
Количество клеток матрицы, содержащих перевозки,
должно быть равно 푛+푚− 1. В нашем случае это условие со-
блюдается: 8 = 4 + 5 – 1.
Метод северо-западного угла имеет существенный недо-
статок. При его использовании не учитываются значения пока-
зателей критерия оптимальности в клетках матрицы. Поэтому
поставки могут попасть в «дорогие» клетки с заведомо высокой
ценой. Опорный план, полученный с использованием данного
метода, как правило, далек от оптимального, что обусловливает
большой объем последующих расчетов для доведения его до
оптимального. Описанный метод обычно не применяется.
1
Метод наименьшей стоимости
1
2
3
4
5
6
Наиболее предпочтительным при ручном решении
транспортных задач считается метод минимальной стоимости.
Суть его в следующем. В транспортной матрице выбирается
клетка с минимальной стоимостью. В нашем случае это клетка
퐴 3 퐵 5. В нее записывается максимально возможная поставка –
это 90 т:

(^) 퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
퐴 1
10 9 8 5 3
100 ; 50 ; 0
X X 50 50 X

1
2
3
4
퐴 2
4 7 13 6 2
150 ; 110 ; 60 ; 0
40 50 60 X X
1
2
3
4
퐴 3
8 6 9 7 1
90 ; 0
X X X X 90
1
2
3
4
퐴 4
5 4 7 9 2
30 ; 0
X 30 X X X

(^40)
0
80
50
0
110
60
0
50
0
90
0
После осуществления данной перевозки спрос станции
퐵 5 полностью удовлетворен, а на станции 퐴 3 товара больше не
осталось. Поэтому столбец 5 и строку 2 следует из дальнейше-
го построения плана исключаем (ставим “Х ” в пустые клетки).
Следующие по величине показателя критерия оптималь-
ности клетки со стоимостью 4 – это клетки 퐴 2 퐵 1 и 퐴 4 퐵 2. Вы-
бираем одну из них, например, 퐴 2 퐵 1 и записываем в нее по-
ставку 40 т. В результате данной поставки спрос станции 퐵 1
полностью удовлетворен, следовательно, столбец 1 исключает-
ся из дальнейшего построения плана. На станции 퐴 2 останется
150 − 40 = 110 т груза.
Далее идет клетка 퐴 4 퐵 2 – поставка 30 т, потом 퐴 1 퐵 4 – 50
т, 퐴 2 퐵 2 – 50 т. Все оставшиеся ресурсы по станциям погрузки
распределяем между клетками третьего столбца в клетки 퐴 1 퐵 3
и 퐴 2 퐵 3.
После составления опорного плана во избежание оши-
бок целесообразно проверить балансы по строкам и по столб-
цам матрицы. Стоимость данной перевозки:
푍(푋)= 2150.
Таким образом, построенный план значительно лучше
плана, построенного методом северо-западного угла. Однако
число базисных клеток в плане – 7. Это не соответствует требо-
ванию к числу заполненных клеток.
Поэтому необходимо ввести недостающее количество
базисных клеток с нулевыми поставками. В нашем случае
необходимо ввести одну нулевую поставку. Нулевую поставку
необходимо вводить в матрицу рядом с базисной клеткой, ко-
торая обусловила «пропажу» базисной клетки.
Для того чтобы понять, почему «пропадают» поставки,
обратимся к методу северо-западного угла. Из построенного
этим методом плана следует, что как только была заполнена
«северо-западная» клетка, рядом с ней сразу появляется сосед-
няя базисная клетка, потом еще одна и т.д. Цепочка базисных
клеток без разрыва следует до «юго-восточного угла» матрицы.
Однако если бы в этой цепочке появилась клетка, связывающая
поставщика и потребителя с равными объемами погрузки и вы-
грузки, и в нее была бы записана такая же поставка, то это при-
вело бы к пропаже базисной клетки.
Описанная ситуация имела место в плане, когда в клетку
퐴 3 퐵 5 была введена перевозка 90 т, равная объемам погрузки и
выгрузки по соответствующим станциям. Поэтому необходимо
ввести в план дополнительную базисную клетку с нулевой по-
ставкой. Эта клетка должна стоять рядом с клеткой 퐴 3 퐵 5. Из
трех соседних клеток следует выбрать клетку с минимальной
стоимостью, например, 퐴 2 퐵 5. Записываем в нее перевозку, рав-
ную «0»:
퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
퐴 (^1 10 9 8 50 5 50 3)
퐴 2
(^4 7 13 6 2)
40 50 60 0
퐴 (^3 8 6 9 7 1 90)
퐴 4 5 4 7 9 2

1
30

Таким образом, причиной вырождения плана транспорт-
ной задачи является наличие поставщиков и потребителей с рав-
ными объемами погрузки и выгрузки или равными объемами
сумм погрузки и выгрузки по нескольким станциям в разнооб-
разных комбинациях. Такие случаи необходимо уметь находить
для того, чтобы правильно определять места для нулевых поста-
вок. В процессе решения задачи возможны случаи, когда число
базисных клеток превышает величину 푛 + 푚 – 1. Это означает
появление ошибки вследствие того, что при построении опорно-
го плана в какую-то клетку была введена не максимально воз-
можная поставка.

1
Шаг2. Проверка плана на оптимальность

Расчет потенциалов
Проверка плана транспортной задачи в описываемом
методе на оптимальность осуществляется с помощью потенци-
алов. Потенциалы – это такие числа, которые по определенным
правилам назначаются каждой строке и каждому столбцу. По-
тенциалы строк
обозначим 풖풊, потенциалы столбцов – 풗풋.
Они могут принимать любые значения. Однако для удобства
будем считать, что 푢 1 = 0. Остальные потенциалы рассчиты-
ваем с помощью формулы 푢푖−푣푗=푐푖푗.

(^) 퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
(^) 푣푗
푢푖
1 − 2 − 8 − 5 3
퐴 (^1 0 10 9 8 50 5 50 3)
퐴 2 5
4 7 13 6 *^2
40 50 60 0
퐴 3 4 8 6 9 *^7 *^1
90
퐴 4 2 5 4 7

  • (^9 2)
    30
  • *Проверка небазисных клеток на соответствие их
    условию оптимальности**
    Оптимальный план транспортной задачи должен отвечать
  • *критерию оптимальности** , который выражается в том, соответ-
    ствуют ли небазисные клетки матрицы условию, формулируемо-
    му следующим выражением: 푢푖−푣푗≤푐푖푗
    Если это условие для всех небазисных клеток выполняет-
    ся, то план является оптимальным, а если нет, хотя бы для одной
    клетки, то план не оптимален. В нашем случае есть четыре клет-
    ки, для которых данное условие не выполняется (отмечены звез-
    дочкой).
  • *Шаг 3. Улучшение плана**
    Поскольку полученный план не оптимален, дальней-
    шие действия алгоритма состоят в его преобразовании в
    лучшую сторону или просто улучшения.
  • *Построение цикла перераспределения поставок**
    Улучшение плана осуществляется по одной из небазис-
    ных клеток, для которой условие оптимальности оказалось не-
    выполненным. В нашем плане имеется четыре такие клетки.
    Выбираем одну из них, для которой условие оптимальности не
    выполняется в наибольшей степени. В нашем плане это клетка
    퐴 2 퐵 4. Для нее условие оптимальности не выполнено на 4 еди-
    ницы ( 5 +(− 5 ) – 6 = 4 ). Для этой клетки строим цикл пере-
    распределения поставок. Цикл перераспределения поставок –

это такая замкнутая ломаная линия, которая проходит по клет-
кам матрицы ходом шахматной ладьи. В вершинах контура
обязательно лежит одна небазисная клетка (несоответствующая
условию оптимальности, найденная ранее), а остальные соот-
ветствуют только базисным клеткам. Линии контура могут пе-
ресекаться. Для небазисной клетки 퐴 2 퐵 4 цикл будет проходить
по клеткам А 1 В 4 ,А 1 В 3 ,А 2 В 3.

(^) 퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
퐴 1 10 9 8 +^5 -^3
50 50
퐴 2 4 7 13 6 2
40 50 - 60 + 0
퐴 3 8 6 9 7 1
90
퐴 4 5 4 7 9 2
30
Перераспределение поставок
Перераспределение поставок производится по циклу.
Вначале определим объем перераспределения поставок. Для
этого присвоим клеткам – вершинам цикла – знаки. В небазис-
ную клетку 퐴 2 퐵 4 ставим «+», поскольку в нее будет вводиться
поставка. Далее, чередуя «+» с «–», расставляем знаки по
остальным вершинам контура. Величина объема перераспреде-
ления поставок принимается равной минимальной поставке в
отрицательной клетке. Для нашего случая min( 60 ; 50 )= 50
единиц груза. Перераспределение заключается в том, что к по-
ставкам в положительных клетках найденный объем прибавля-
ется, а для отрицательных клеток отнимается:
(^) 퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
퐴 1
10 9 8 5 3
100
퐴 2
4 7 13 6 2
40 50 10 50 0
퐴 3
8 6 9 7 1
90
퐴 4
5 4 7 9 2
30
Стоимость новой перевозки 푍= 1950.
Полученный улучшенный план, в свою очередь, требует
проверки на оптимальность, поэтому необходимо вернуться к
шагам 2 и 3. Совокупность действий, описанных в операциях 2
и 3, в процессе решения задачи повторяется до тех пор, пока не
будет получен оптимальный план.
Для рассматриваемой задачи оптимальный план перево-
зок следующий:
퐵 1 퐵 2 퐵 3 퐵 4 퐵 5
퐴 1
10 9 8 5 3
100
퐴 2
4 7 13 6 2
40 60 50 0
퐴 3
8 6 9 7 1
90
퐴 4
5 4 7 9 2
20 10
Стоимость новой перевозки 푍= 1920.

Таким образом, получен план перевозок, обеспечиваю-
щий минимальный объем перевозочной работы для транспор-
тировки всего груза между станциями погрузки и выгрузки.

Задача 14. Решите транспортную задачу методом потенциалов

1
Заказы

Запасы

1
11 7 8 4
1
2
3
9 2 5 8 1
16 8 3 9 2
5 7 4 6 3

Ответ. Минимальные затраты составят 120.

Задача 15. Решите транспортную задачу методом потенциалов

1
Заказы

Запасы

1
100 200 200 300
1
2
3
4
100 1 3 4 1
200 5 2 2 7
400 4 4 3 6
200 7 2 5 3

Ответ. Минимальные затраты составят 2100.

Задача 17. Решите транспортную задачу методом потенциалов

1
Заказы

Запасы

1
200 200 100 200
1
2
200 5 2 1 1
300 1 3 4 4
1
2
3
200 4 2 3 1
200 4 3 5 2
100 3 2 4 2
1
Ответ. Минимальные затраты составят 900.
1
2
3
4
5
6
7
8
9
10
11
12
13
3.7.3 Решение транспортной задачи с помощью
надстройки «Поиск решения».
Задача.
В районе имеется 4 песчаных карьера, с которых песок
вывозится на 5-тонных грузовиках. Предприятия-поставщики
S1 - S4 разрабатывающие карьеры, могут поставлять опреде-
ленное количество грузовиков с песком в день.
В этом районе имеется 5 заводов железобетонных кон-
струкций - потребителей песка D1-D5, которым требуется
определенное количество грузовиков с песком в день. Стоимо-
сти перевозки песка одним грузовиком от карьера-поставщика
Si к заводу-потребителю Di (в условных единицах) приведены в
таблице параметров.
1
2
3
4
5
6
D1 D2 D3 D4 D5 Запасы
S1 13 7 14 7 5 30
S2 11 8 12 6 8 48
S3 6 10 10 8 11 20
S4 14 8 10 10 15 20
Заказы 18 27 42 26 15
1
Требуется:
  1. Составить план перевозок, минимизирующий затраты.
  2. Указать какой из 5 заводов не получит песок в нуж-
    ном объеме.
  1. Как изменится оптимальный план, если маршрут от S 2
    к D4 запрещен.

Решение.
Суммарные запасы песка составляют 118 грузовиков в
день, суммарные заказы на песок составляют 128 грузовиков в
день, т.е. имеем транспортну задачу с дефицитом. Для вырав-
нивания баланса добавим фиктивного поставщика Sf ictS 5 с

запасом песка в 10 грузовиков (тарифы на перевозки каждому
из заводов будут равны 0).

1
2
Построим математическую модель задачи.
Переменные решения Целевая функция
1
xij - объем поставок от i-го ка-

рьера ( 1 i 5 ) j-му заводу (

1 j 5 )

1
min
1
5
1
1
1
5
1
1

 

1
i j
1
C cijxij
1
2
Ежедневная затраты на пе-
ревозку
1
Ограничения
1

1
2


1
2
3



1

1
 
1
 
1

1

1

1

1
, 1 , 2 , 3 , 4 , 5
1
, 1 , 2 , 3 , 4 , 5
1
5
1
1
1
5
1
1
1
x D j
1
x S i
1
2
j
i
1
ij
1
2
i
j
1
ij

xij (^0)
Организуем данные так как это показано на рисунке:
Вызовем “Поиск решения”:

Не следует требовать явно, чтобы переменные
В11:
F 14 были целыми.

Вид листа MS-Excel, соответствующий оптимальному
решению, показан на рис.

1
2
3
4
5
Для замкнутой (или сбалансированной) задачи все невы-
везенные запасы и невыполненные заказы должны быть равны
0 (напомним, что, например, число 4,2Е-11 есть 4 , 2  10 ^11 , т.е.
его можно приближенно считать равным нулю).
Итак ответ на первый вопрос: оптимальный план пере-
1
возок
1

1

1

1

1

1

1

1

1

1

1

1

1

1
0 0 20 0 0
1
18 0 2 0 0
1
0 12 10 26 0
1
0 15 0 0 15
1
Xopt , затраты при этом составят
1
2
3
4
5
6
7
8
880 у.е.
Ответ на второй вопрос. Очевидно, что завод D3 не до-
получит песка в объеме 10 машин (это те машины, которые от-
правлены на завод D3 от фиктивного поставщика).
Для ответа на третий вопрос придется заново запустить
"Поиск решения", установив тариф на перевозку от поставщика
S2 к потребителю D4 равным, например, 100. Результат изоб-
ражен на рисунке.

Очевидно, что матрица перевозок получилась совер-
шенно иной, а затраты достигли 954 у.е., увеличившись на 54
у.е.
Замечание. Следует заметить, что введение любого до-
полнительного ограничения в “Поиск решения” для транспорт-
ной задачи приводит к тому, что эффективные “транспортные”
методы решения таких задач перестают быть применимыми, и
задача будет решаться с помощью общих алгоритмов решения
ЛП-задач. Помимо того, что эти методы менее эффективны,
они не могут гарантировать целочисленного решения, и про-
блема перейдет в разряд более сложных задач целочисленного
программирования.

Задача.
Компания, занимающаяся сбором и переработкой ме-
таллолома, имеет четыре промышленные площадки S 1 - S4, ко-
торые могут поставлять металлургическим предприятиям опре-

1
2
3
4
5
6
7
8
деленное количество товарного металлолома в месяц ( в тоннах
указано в таблице в графе "Запасы").
В настоящее время у компании имеются заявки на сле-
дующий месяц от 5 предприятий D1-D5, которым требуется
определенное количество металлолома в месяц (в тоннах ука-
зано в таблице в графе "Заказы"). Стоимости перевозки 1 т ме-
таллолома от промплощадки-поставщика Si к заводу-
потребителю Di (в условных единицах) приведены в таблице.
1
2
3
4
5
6
D1 D2 D3 D4 D5 Запасы
S1 3 4 5 4 6 30
S2 1 5 7 1 5 48
S3 4 6 6 3 4 20
S4 2 7 4 7 2 30
Заказы 18 27 42 26 15
1
2
3
Составить математическую модель задачи нахождения
плана перевозок, минимизирующего затраты. Найти решение
задачи с помощью MS Excel.
1
Ответ.
1

1

1

1

1

1

1

1

1

1

1

1

1

1
0 0 15 0 15
1
0 0 20 0 0
1
18 4 0 26 0
1
0 23 7 0 0
1
Xopt , минимальные за-
1
траты составляют 401 у.е.
1
2
3
4
5
6
7
Задача.
В районе имеется 4 песчаных карьера, с которых песок
вывозится на 5-тонных грузовиках. Предприятия-поставщики
S1 - S4 разрабатывающие карьеры, могут поставлять опреде-
ленное количество грузовиков с песком в день.
В этом районе имеется 5 заводов железобетонных кон-
струкций - потребителей песка D1-D5, которым требуется

определенное количество грузовиков с песком в день. Стоимо-
сти перевозки песка одним грузовиком от карьера-поставщика
Si к заводу-потребителю Di (в условных единицах) приведены в
таблице параметров.

D1 D2 D3 D4 D5 Запасы
S1 1 3 4 3 1 500
S2 9 5 2 4 8 600
S3 3 4 7 4 3 900
S4 5 7 2 6 6 1000
Заказы 300 900 800 400 400

1
Требуется:
  1. Составить план перевозок, минимизирующий затраты.
  2. Составить план перевозок, максимизирующий затра-
    ты. Найти разность между наибольшими и наименьшими из
    возможных затратами.
  3. Указать на каком из двух карьеров останется невыве-
    зенный песок, в каком количестве.
  4. Как изменится оптимальный план, если маршрут от S 4
    к D3 запрещен.

Ответ.

  1. Наилучший план
1

1

1

1

1

1

1

1

1

1

1

1

1

1
0 0 600 0 400
1
0 400 200 100 0
1
300 0 0 300 0
1
0 500 0 0 0
1
Xopt ,

минимальные затраты составляют 9 700 у.е..

  1. Наихудший план
1

1

1

1

1

1

1

1

1

1

1

1

1

1
0 600 0 400 0
1
300 300 200 0 0
1
0 0 600 0 0
1
0 0 0 400 100
1
Xmax ,
1
максимальные затраты составляют 17 800 у.е.
  1. Невывезенный песок в количестве 200 машин оста-
    нется на карьере S3.
1
4.
1

1

1

1

1

1

1

1

1

1

1

1

1

1
300 100 0 400 0
1
0 100 800 0 0
1
0 200 0 400 0
1
0 500 0 0 0
1
Xopt , минимальные затра-
1
2
ты составляют 10900 у.е., т.е. закрытие маршрута приведет к
общему повышению издержек на 1200 у.е.
1
2
3
4
5
6
7
8
9
10
11
12
13
Задача.
Фирма, занимающаяся перевозкой грузов собственных
автомобилях КамАЗ, обслуживает своих клиентов в централь-
ных городах России. Клиенты могут заказать фирме доставку
груза из любого населенного пункта в любой город. После до-
ставки КамАЗы ждут распоряжений диспетчера о выполнении
следующей заявки в том городе, куда был доставлен груз.
В настоящий момент 4 порожних автомобиля ждут рас-
поряжений в Иваново, 3 автомобиля - в Костроме, 6 машин - в
Орле и одна - в Калуге. Одновременно диспетчеру поступили
заявки на 5 автомобилей во Владимире, на 3 автомобиля в
Санкт-Петербурге и на 6 автомобилей в Москве. Расстояния
между городами известны и приведены в таблице.
1
2
3
Машины
Клиенты Наличие
Владимир Санкт - Москва (машин)^
1
2
3
4
5
6
7
Петербург
Иваново 119 971 287 4
Кострома 214 1008 324 3
Орел 508 1024 340 6
Калуга 326 535 135 1
Заявки
(машин)
1
5 3 6

Составить такой план перегона порожних автомобилей
из мест их расположения к клиентам, чтобы суммарный пробег
всех автомобилей, а следовательно, и издержки фирмы были
минимальными.
Ответ.
Оптимальный план перегона автомобилей: во Владимир

  • 4 машины из Иваново и 1 из Костромы; в Санкт-Петербург –
    2 машины из Орла и одна из Калуги; в Москву - 2 из Костромы
    и 4 из Орла. Суммарный пробег всех автомашин составит 5281
    км.

3.7.4 Задачи, сводящиеся к транспортным.

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

Пример. Необходимо распределить специалистов трёх
профилей (соответственно, 60,30 и 40 человек) на 4 вида работ.
Потребность в специалистах, соответственно, 20, 40, 25 и 45.
Cij – эффективность использования специалиста i-го профиля
на j-й работе.

1

1

1

1

1

1

1

1

1

1
2
3


5 7 0 9
1
4 0 8 6
1
2
7 5 2 0
C
1
2
Решение. Задача похожа на транспортную, но требуется
найти не минимум , а максимум. Поэтому...
1
20 40 25 45
1
2
40
5 7 0 9
1
2
30
4 0 8 6
1
2
60
7 5 2 0
1
  
1
  
1
  
1
Ответ.
1
40
1
5 7 0 9
1
5
1
2
6
25
1
4 0 8
1
2
2 0
40
1
2
5
20
1
7
1
  
1
  
1
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Задача.
Менеджер - координатор аудиторской фирмы должен
распределить аудиторов для работы на следующий месяц.
Имеются заявки от 10 клиентов на 75 аудиторов. В 4 конторах
фирмы имеется 90 аудиторов, 15 "лишних" аудиторов можно
отправить на плановую учебу. Аудиторы различаются по ква-
лификации и опыту работы. Прежде чем приступить к аудиту
конкретной фирмы, они должны затратить определенное время
на подготовку и консультации. Менеджер-координатор, учиты-
вая опыт работы аудиторов каждой конторы, оценил время, не-
обходимое "среднему" аудитору каждой конторы для подготов-
ки к аудиту конкретного клиента. Результаты - в таблице.
Конторы Клиенты Запасы
1 2 3 4 5 6 7 8 9 10

ГААПвилл (^8 21 15 13 9 17 18 7 26 9 35)
Финанстаун 14 18 17 19 12 6 0 15 24 13 20
ИСАбург 9 15 18 16 16 15 11 13 21 19 25

1
Нью-Баланс 11? 14 7 23 9 6 18? 7 10

Заявки (^4 9 2 12 7 6 9 3 18 5)
Распределить аудиторов так, чтобы суммарные времен-
ные затраты на подготовку были минимальны. Знаки вопроса в
некоторых клетках таблицы означают, что аудиторы данной
конторы не имеют опыта аудита в отрасли, к которой относится
данный клиент, и их не должны к нему посылать.
Ответ.
Оптимальное распределение аудиторов












0 0 0 10 0 0 0 0 0 0
0 9 0 0 0 0 0 0 16 0
0 0 0 0 0 6 9 0 2 0
4 0 2 2 7 0 0 3 0 5
Задача.
Мастер должен расставить 4 рабочих для выполнения 4 типо-
вых операций. Из данных хронометрирования известно, сколь-
ко минут в среднем тратит каждый из рабочих на выполнение
каждой операции. Эти данные представлены в таблице.
Работы Работники
A B C D
1 15 20 18 24
2 12 17 16 15
3 14 15 19 15
4 11 14 12 3
Как распределить рабочих по операциям, чтобы суммар-
ные затраты рабочего времени были бы минимальны?
Составить математическую модель задачи и решить ее с
помощью MS Excel.
Ответ. Распределение рабочих по операциям имеет вид












0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
, минимальные суммарные временные затраты
составят 48 мин.
Задача.
Мастер цеха должен назначить на сборку изделия, тре-
бующую выполнения шести различных операций, шесть рабо-
чих. В силу разной квалификации рабочие затрачивают на вы-
полнение операций различное время. Результаты их тестирова-
ния приведены в таблице. Следует также учесть, что рабочие 3
и 4 не умеют выполнять операцию No2, а рабочий 6 не может
выполнять операцию No6. Кроме того, имеется 7 рабочих, сле-
довательно, один из них не будет задействован в процессе.
Каким образом оптимально распределить рабочих по
операциям, чтобы суммарное время, затрачиваемое на сборку
изделия, было минимальным? Кому из рабочих можно “отдох-
нуть”?
Рабочие Операции
1 2 3 4 5 6
1 23 6 7 12 6 12
2 8 16 11 6 12 11
3 6? 9 8 16 23
4 11? 18 15 15 12
5 12 17 12 11 7 15
6 4 12 11 8 17?^
7 5 10 8 15 7 14

1
Ответ. Оптимальное распределение рабочих по опера-

циям имеет вид

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
0 0 1 0 0 0
1
1 0 0 0 0 0
1
0 0 0 0 1 0
1
0 0 0 0 0 1
1
0 0 0 0 0 0
1
0 0 0 1 0 0
1
0 1 0 0 0 0
1
, минимальные суммарные

временные затраты составят 43 мин., отдыхать будет третий
рабочий.
Задача.
Фирма, занимающаяся продажей оборудования для ком-
пьютерных сетей, имеет 10 специалистов по маркетингу и 10
техников-программистов, которых необходимо объединить в
пары (техник - менеджер по маркетингу) - команды по продаже
оборудования, соответствующего нуждам конкретного клиента.
Менеджер по работе с персоналом провел среди них тест Май-
ера-Бриггса и определил индекс взаимной несовместимости
между i-м техником и j-м маркетологом. Индекс варьирует от
20 (выраженная враждебность) до 1 (дружеские отношения).
Результаты представлены в таблице индексов несовместимости.
Составить команды так, чтобы суммарный индекс был
минимальным.

1
2
3
Индексы несовместимости
Марке-
толог
1
2
3
Техник
Ва
ня
1
2
Пе
тя
1
2
Ми
ша
1
2
Ко
ля
1
2
Ва
ся
1
2
Ро
ма
1
2
Ма
йя
1
2
Ви
тя
1
2
Ин
на
1
2
3
4
5
Ге
на
Аня 11 8 4 3 9 17 14 6 12 2
Зоя 7 4 7 11 19 2 10 5 18 9
Маша 13 20 1 12 14 11 16 9 15 14
1
2
Вита-
лий
1
5 8 12 6 1 3 4 7 10 12
1
2
3
4
5
6
Люба 16 7 18 9 13 1 2 17 12 3
Даша 12 3 9 17 5 6 18 2 1 4
Руслан 9 1 13 4 7 20 19 1 19 16
Валя 8 6 17 8 11 4 3 4 13 16
Юля 17 2 19 13 14 19 11 3 17 1
Галя 12 1 7 1 2 5 6 4 1 13
1
2
3
Ответ. Составы команд: Аня - Коля, Зоя - Ваня, Маша -
Миша, Виталий - Вася, Люба - Рома, Даша - Инна, Руслан - Ви-
тя, Валя - Майя, Юля - Гена, Галя - Петя.
4. Модели теории игр
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4.1 Введение.
В практической деятельности часто приходится рассматривать
ситуации, в которых участвуют две или более сторон, имеющих
различные интересы. Подобные ситуации принято называть
конфликтными.
Для того, чтобы анализ конфликтной ситуации оказался воз-
можным, необходимо оставить существенные и исключить
второстепенные факторы, что при благоприятных обстоятель-
ствах позволяет построить модель конфликта, называемую иг-
рой. Такие различного вида модели изучаются при помощи ма-
тематического аппарата теории игр.
Стороны конфликта называются игроками (их два или более). В
условиях конфликта каждый игрок выбирает план действий,
который называется стратегией. Заинтересованность игрока
описывается величиной его выигрыша.

4.2 Матричные игры.

Одним из самых простых и наиболее изученных классов игр
являются матричные игры.

 В игре участвуют два игрока, A и B.

 Игрок A имеет возможные стратегии A 1 ,…Am, игрок B –
стратегии B 1 ,…,Bn.

 Выбор стратегий игроками однозначно определяет исход
игры.

 В ситуации, когда игрок A выбрал стратегию Ak, а игрок B

  • стратегию Bl, выигрыш A равен числу Сkl, выигрыш B ра-
    вен этому же числу с противоположным знаком («антагони-
    стическая игра», «игра с нулевой суммой»).

Таким образом, матричная игра полностью описывается зада-
нием «платёжной матрицы»:

1
2


1

1

1

1

1

1
2


1

1

1

1

1

1

1
m m mn
1
n
1
n
1
c c c
1
c c c
1
c c c
1
C
1
...
1
... ... ... ...
1
...
1
...
1
1 2
1
21 32 2
1
11 12 1

Пример. Два игрока, A и B показывают одновременно друг
другу от одного до трёх пальцев. Если суммарное количество
пальцев чётно, то выигрывает первый, он получает столько оч-
ков, сколько суммарно показано пальцев; если сумма нечётна,
то выигрывает второй на тех же условиях. Выписать платёж-
ную матрицу.

Ответ.

1

1

1

1

1

1

1

1

1

1

1
 
1
2
3


4 5 6
1
3 4 5
1
2
2 3 4
C
1
Рассмотрим эту игру подробнее.
1
2
3
4
5
6
7
8
9
B 1 B 2 B 3
Минимумы
строк
A 1 2 – 3 4 – 3*
A 2 – 3 4 – 5 – 3*
A 3 4 - 5 6 – 5
Максимумы
столбцов
4* 4* 6
1
2
Максимальное число из минимумов строк – верхняя цена игры
(помечена звёздочкой). Минимальное из максимумов столбцов
  • нижняя цена игры. Эти два числа не равны, что означает от-
    сутствие седловой точки
    .

Пример. Пусть теперь платёжная матрица такова:

1

1

1

1

1

1

1

1

1

1

1

1
2
3


1 1
1
2 4
1
2
1 5
C
1
2
3
4
5
6
7
8
9
B 1 B 2
Минимумы
строк
A 1 1 - 5 - 5
A 2 2 4 2*
A 3 - 1 1 - 1
Максимумы
столбцов
2* 4

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

Точки пересечения соответствующих строк и столбцов назы-
ваются седловыми точками, или точками равновесия по Нэшу.

Игроку A имеет смысл применять стратегию A 2 , игроку B –
стратегию B 1. Если любой откажется от указанной стратегии,
то его выигрыш может только уменьшиться. То есть обоим не-
выгодно отклоняться от седловой точки.

4.3 Смешанные стратегии в матричных играх.

Что делать, если верхняя и нижняя цены игры не совпадают, то
есть нет седловой точки? В этом случае можно искать решение
игры в смешанных стратегиях.

Оказывается, что

Пример. Рассмотрим следующую матричную игру:

1

1

1

1

1

1

1

1

1

1
2
3


10 1 10
1
1 1 0 , 1
1
2
5 50 50
C
1
2
3
4
5
Здесь α=5 < β = 10 → нет положения равновесия и решения в
чистых стратегиях. Будем искать решение в смешанных страте-
гиях.
Соответствующие задачи линейного программирования имеют
вид:
1

1

1

1

1

1

1

1

1

1

1

1
  
1
   
1
   
1
   
1
 
1
, , 0
1
1
1
50 0 , 1 10 0
1
50 0
1
5 10 0
1
( ) max
1
1 2 3
1
1 2 3
1
1 2 3
1
1 2 3
1
1 2 3
1
p p p
1
p p p
1
v p p p
1
v p p p
1
v p p p
1
f x v
1

1

1

1

1

1

1

1

1

1

1

1
  
1
   
1
   
1
   
1
 
1
, , 0
1
1
1
10 10 0
1
0 , 1 0
1
5 50 50 0
1
( ) min
1
1 2 3
1
1 2 3
1
1 2 3
1
1 2 3
1
1 2 3
1
q q q
1
q q q
1
v q q q
1
v q q q
1
v q q q
1
g x v
1
2
3
4
5
Решив их любым способом, получаем: p 1 =1/6, p 2 =0, p 3 =5/6,
q 1 =49/54, q 2 =5/54, q 3 =0.
Цена игры в смешанных стратегиях для A: v = −0,91 (игра не-
выгодна)
Типовая задача.
1
2
3
Всякая матричная игра имеет решение (положение равнове-
сия) в смешанных стратегиях. Его можно найти, решив вспо-
могательную задачу линейного программирования.
1
2
3
4
5
Смешанной стратегией игрока A называется выбор им своих
стратегий A 1 ,..,Am случайным образом с некоторыми задан-
ными вероятностями p 1 ,...,pm.
Аналогично определяется смешанная стратегия игрока B –
выбор с вероятностями q 1 ,...,qn.

Фирма “Фармацевт” - производитель медикаментов в регионе.
Известно, что пик спроса на некоторые лекарственные препара-
ты приходится на летний период (препараты сердечно-
сосудистой группы), на другие - на осенний и весенний перио-
ды (антиинфекционные).
Затраты на 1 у.е. продукции за сентябрь-октябрь составили: по
первой группе (препараты сердечно-сосудистые) - 20 р.; по
второй группе (антиинфекционные) - 15 р.
По данным наблюдений за несколько последних лет службой
маркетинга фирмы установлено, что она может реализовать в
течение рассматриваемых двух месяцев в условиях теплой по-
годы 3050 у.е. продукции первой группы и 1100 у.е. продукции
второй группы; в условиях холодной погоды - 1525 у.е. про-
дукции первой группы и 3690 у.е. второй группы.
В связи с возможными изменениями погоды ставится задача -
определить стратегию фирмы в выпуске продукции, обеспечи-
вающую максимальный доход от реализации при цене продажи
40 р. за 1 у.е. продукции первой группы и 30 р. - второй груп-
пы.

Решение.
Фирма располагает двумя стратегиями:
А1 -будет теплая погода;
А2 - погода будет холодная.
Если фирма примет стратегию А1 и в действительности будет
теплая погода (стратегия природы В1), то выпущенная продук-
ция будет полностью реализована и доход составит
3050 ( 40  20 ) 1100 ( 30  15 ) 77500 р.

Если фирма примет стратегию А1, а погода будет прохладной
(стратегия природы В2), то часть препаратов первой группы
останется не реализованной , а доход составит
1525 ( 40  20 ) 1100 ( 30  15 ) 20 ( 3050  1525 ) 16500 р.

1
2
3
4
5
6
7
8
Аналогично, если фирма примет стратегию А2, а природа стра-
тегию В1, доход составит
3050 ( 40  20 ) 1100 ( 30  15 ) 15 ( 3690  1100 ) 8150 р.
Если фирма примет стратегию А2, а природа В2, то доход со-
ставит
1525 ( 40  20 ) 3690 ( 30  15 ) 85850 р.^
Рассматривая фирму и природу в качестве двух игроков, полу-
чаем платежную матрицу
1
2


1
2
3



1
2

8150 85850
1
2
77500 16500
,
max( 16500 ; 8150 ) 16500 р.,
min( 77500 ; 85850 ) 77500 р.^
1
2
3
4
5
6
Таким образом цена игры будет лежать в диапазоне
16500  77500.^
Найдем решение игры.
Пусть p 1 - вероятность применения фирмой стратегии А1, p 2 -
вероятность применения стратегии А2. Составим задачу линей-
ного программирования, соответствующую данной игре:
1

1

1

1

1

1

1

1

1

1

1

1
  
1
  
1
  
1
 
1
, , 0 ;
1
1 ,
1
16500 85850 0 ,
1
77500 8150 0 ,
1
( ) max
1
1 2 3
1
1 2 3
1
1 2
1
1 2
1
p p p
1
p p p
1
v p p
1
v p p
1
f x v
1
2
3
4
5
Решив полученную задачу, например, с помощью MS-Excel,
получим p 1  0 , 56 , p 2  0 , 44 , при этом цена игры 46986 р.
Оптимальный план производства лекарственных препаратов
составит
0 , 56 ( 3050 ; 1100 ) 0 , 44 ( 1525 ; 3690 )( 2379 ; 2240 ).

Ответ. Фирме целесообразно производить в течение сентября и
октября 2379 у.е. препаратов первой группы и 2240 у.е. препа-
ратов второй группы, тогда при любой погоде она получит до-
ход не менее 46986 руб.

Задача.

Найти оптимальные стратегии и цену игры.

1

1

1

1

1

1

1

1

1

1
2
3


2 3 1 4 7 20
1
4 9 3 6 2 1
1
2
3 7 1 1 5 8
A

Ответ.

1
popt 0 ; 6 / 7 ; 1 / 7 ; qopt 0 ; 0 ; 5 / 7 ; 0 ; 2 / 7 ; 0 ;  19 / 7.

Задача.

Торговая фирма разработала несколько вариантов плана про-
дажи товаров на предстоящей ярмарке с учетом меняющейся
конъюнктуры рынка и спроса покупателей. Получающиеся от
их возможных сочетаний показатели дохода представлены в
таблице

План продажи

1
2
3
4
5
Величина дохода, у.е.
К1 К2 К3
П1 8 4 2
П2 2 8 4
П3 1 2 8

Определить оптимальный план продажи товаров.

Ответ. Фирма должна придерживаться стратегии
(20/45;11/45;14/45), при этом она получит доход не менее
196/45 у.е.

1
2
3
4
5
6
7
8
9
10
11
12
13
Задача. Фирма производит пользующиеся спросом детские
платья и костюмы, реализация которых зависит от состояния
погоды. Затраты фирмы в течение августа-сентября на единицу
продукции составили: платья - 7 у.е., костюмы - 28 у.е. Цена
реализации составляет 15 и 50 у.е. соответственно. По данным
наблюдений за несколько предыдущих лет, фирма может реа-
лизовать в условиях теплой погоды 1950 платьев и 610 костю-
мов, а при прохладной погоде - 630 платьев и 1050 костюмов.
В связи с возможными изменениями погоды определить страте-
гию фирмы в выпуске продукции, обеспечивающую ей макси-
мальную прибыль от реализации продукции.
Ответ. 1330 платьев, 817 костюмов, прибыль составит 18266
у.е.