close

Вход

Забыли?

вход по аккаунту

?

Vasilchuk Metody optim18

код для вставкиСкачать
В. Ю. ВАСИЛЬЧУК, Л. В. КОНОВАЛОВА,
С. И. ПРОКОФЬЕВА
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
Министерство образования и науки
Российской Федерации
Санкт-Петербургский государственный
архитектурно-строительный университет
В. Ю. ВАСИЛЬЧУК, Л. В. КОНОВАЛОВА,
С. И. ПРОКОФЬЕВА
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
Учебное пособие
Санкт-Петербург
2018
0
1
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
УДК 519.85
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
ВВЕДЕНИЕ
Рецензенты: канд. физ.-мат. наук, доцент В. Г. Пак (СПбГПУ);
канд. физ.-мат. наук, доцент Г. И. Синкевич (СПбГАСУ)
Васильчук, В. Ю.
Методы оптимальных решений: учеб. пособие / В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева; СПбГАСУ. – СПб.,
2018. – 88 с.
ISBN 978-5-9227-0876-0
Учебное пособие посвящено задачам теории линейной оптимизации.
Включает необходимые сведения из линейной алгебры и аналитической геометрии, графический и аналитический способы решения задач линейной
оптимизации, теорию двойственности линейных оптимизационных задач,
транспортную задачу. Особое внимание уделено наглядным геометрическим
представлениям решений, простым алгоритмам нахождения решений и их
практическим приложениям. Теоретический материал подкреплен примерами и решениями задач экономического содержания. Также предлагаются задачи для самостоятельного решения.
Предназначено для студентов всех специальностей и всех форм обучения.
Табл. 19. Ил. 10. Библиогр.: 5 назв.
Рекомендовано Учебно-методическим советом СПбГАСУ в качестве
учебного пособия.
ISBN 978-5-9227-0876-0
© В. Ю. Васильчук, Л. В. Коновалова,
С. И. Прокофьева, 2018
© Санкт-Петербургский государственный
архитектурно-строительный университет, 2018
2
Математика – наука, дающая методы познания окружающего
нас мира. Вряд ли можно указать сферу практической деятельности, где не применяются сейчас методы математического исследования. В конце XIX и в начале XX вв. развитие математики происходило главным образом под влиянием запросов физики и механики. Человеческое общество решало задачу создания мощной
техники, искало источники больших энергий. Однако большое количество создаваемой техники, огромные накопленные запасы
энергоносителей и сырья потребовали ответов на вопросы: как
управлять созданной техникой, как использовать накопленную
энергию, как рационально расходовать добытое сырье? Оказалось,
что эти проблемы не менее актуальны, чем проблемы собственно
создания техники и получения энергии. Таким образом, усложняющаяся жизнь выдвинула на передний план проблемы организации
и управления. В связи с этим возникла потребность в новых математических методах и теориях, позволяющих решать эти важные
экономические проблемы.
Так постепенно к началу XX в. роль «поставщика» новых задач в математике стала переходить от физики и техники к экономике. Если раньше математический аппарат преимущественно использовался как инструмент расчета, то теперь ставилась задача
принятия решения, выбора наиболее эффективного варианта, при
котором может быть достигнут наилучший результат. Такие задачи
привели к созданию новых математических дисциплин: линейного
программирования, теории игр, теории массового обслуживания
и других. В частности, впервые постановка задачи линейного программирования прозвучала в 1930 г. в работе советского экономиста А. Н. Толстого в виде предложения по составлению такого плана перевозки груза между пунктами, чтобы общий пробег транспорта был наименьшим. Основы математического аппарата для
решения задач линейного программирования были созданы в 1939 г.
выдающимся российским ученым, академиком Леонидом Витальевичем Канторовичем (19.01.1912–07.04.1986).
3
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Целью настоящего учебного пособия является ознакомление
студентов с современными методами оптимизации на основе прежде всего методов линейного программирования [2, 3] для формирования необходимых компетенций, для применения полученных
знаний и навыков при решении задач теории игр [1], теории оптимального управления и различных прикладных экономических задач.
Основной задачей оптимизации будем называть следующую
задачу о нахождении условного экстремума функции нескольких
переменных:

 f ( x )  max, min;
 
n
 x  D, D  R .

Здесь аргументом функции f является вектор x с n вещественными компонентами, принадлежащий некоторой области D в n -мерном вещественном пространстве R n . Простейший частный случай
подобной задачи при n  1 – это нахождение экстремума функции
на отрезке:
 f ( x)  max, min;

x  [a, b].

Из основного курса математического анализа известно, что
если функция f непрерывна на отрезке [a, b] , то данная задача
имеет решение. В самом деле, по теореме Вейерштрасса непрерывная на отрезке функция достигает своего максимума и своего минимума, а значит, существуют такая точка c  [a, b] и такая точка
d  [a, b] , что
f (c)  min f ( x), f (d )  max f ( x).
x[ a ,b ]
Введение
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
программирования), когда линейными являются как функция f ,
так и соотношения, задающие область D . Заметим, что задача об
экстремуме линейной функции f ( x)  kx  m на отрезке [a, b] является задачей линейного программирования, так как отрезок [a, b]
можно задать двумя простейшими линейными неравенствами:
x  a, x  b . Задача имеет решение, поскольку линейная функция
непрерывна и ее экстремумы, очевидно, всегда достигаются на границе отрезка в точках a и b . Как уже указывалось выше, задачи
линейной оптимизации часто возникают в различных экономических, инженерных и физических моделях, поэтому они представляют собой хорошо изученную область математики, изложенную
в работах, например, Л. В. Канторовича (которому за приложение
данных задач к экономике была присуждена Нобелевская премия
в 1975 г.). Продолжением задач линейной оптимизации являются
задачи нелинейной оптимизации [3], выпуклого анализа, а также
в какой-то мере задачи оптимального управления.
Данное учебное пособие в основном посвящено задачам линейной оптимизации. Для того чтобы оно было самодостаточным,
первый его раздел посвящен фактам из геометрии, линейной алгебры и математического анализа, необходимым в изложении последующих разделов. Кроме того, пособие включает некоторое количество задач и упражнений для самопроверки усвоения материала
в конце каждого подраздела.
x[ a ,b ]
К сожалению, решение основной задачи оптимизации существует не всегда даже в одномерном случае. Например, не существует экстремума у функции f ( x)  tg x на интервале   / 2;  / 2 ,
поскольку она на нем не ограничена. Очевидно, чтобы основная задача оптимизации в общем имела решение, необходимо ограничить
класс функций f , а также аккуратнее задать область D .
Традиционно из всех задач оптимизации принято выделять задачи линейной оптимизации (иначе называемые задачами линейного
4
5
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
Глава 1. НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ГЕОМЕТРИИ,
ЛИНЕЙНОЙ АЛГЕБРЫ И МАТЕМАТИЧЕСКОГО
АНАЛИЗА, ПРИМЕНЯЕМЫЕ В РЕШЕНИЯХ ЗАДАЧ
ОПТИМИЗАЦИИ
Например, для нахождения вершины A нашего четырехугольника надо решить систему линейных уравнений AB и AD :
1.1. Уравнения прямых, системы линейных уравнений
На плоскости в системе координат X 1OX 2 прямые можно задать аналитически (т. е. в виде уравнений), например в виде уравнения прямой с угловым коэффициентом:
x2  kx1  b,
где k – угловой коэффициент; b – отрезок, отсекаемый прямой на
оси OX 2 .
Кроме того, прямую можно задать в виде общего уравнения
прямой (линейного уравнения):
Ax1  Bx2  C  0,
где константы A, B не равны нулю одновременно.
В задачах линейной оптимизации часто приходится строить
многоугольники на плоскости X 1OX 2 , ограниченные заданными
прямыми, и находить их вершины, решая системы линейных уравнений (сокращенно СЛАУ).
Пример 1.1. Построить
x2
(рис. 1.1) на плоскости X 1OX 2
8
A
четырехугольник ABCD, ограниченный прямыми:
3
D
AB : x1  x 2  8  0;
3
B
O
–4
8
BC : 4 x1  5 x 2  32  0;
CD : 7 x1  3 x 2  9  0;
x1
AD : 3 x1  x 2  3  0.
C
Рис. 1.1
6
 x1  x2  8;
 x1  (3x1  3)  8;  4 x1  3  8; 

 x2  3 x1  3;
5
 4 x1  5;  x1   1,25;  x2  3  1,25  3  6,75;  A(1,25; 6,75).
4
1.2. Линейные неравенства
Линейные неравенства вида x2  kx1  b, x2  kx1  b или
Ax1  Bx2  C  0, Ax1  Bx2  C  0 задают полуплоскости (какие
именно, зависит от соотношения знаков констант k , А и B и знаков
неравенств «≤» и «≥»), граница которых – это прямая x2  kx1  b
или Ax1  Bx2  C  0.
Пример 1.2. Лежит ли точка M (1;  1) в полуплоскости, заданной неравенством
4 x1  5 x2  32  0 ?
Построим границу этой полуплоскости (рис. 1.2) – прямую АВ:
x2
A : x2  0  x1  8;
B : x1  3  x2  4.
–1
O
–4
Как определить, какую полуплоскость (левую верхнюю или
правую нижнюю) задает данное
неравенство? Можно, например,
выразить из неравенства переменную x2 :
4
32
x2  x1  .
5
5
7
3
1
8
A
M
B
Рис. 1.2
x1
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Из него по знаку неравенства «≤» ясно, что мы имеем нижнюю полуплоскость.
Другой способ: можно проверить, удовлетворяет ли данному
неравенству какая-либо точка, например O(0; 0). Подставим ее координаты в неравенство, получим:
4  0  5  0  32  32  0.
Очевидно, что исходное неравенство в этой точке не выполняется, поэтому точка O(0; 0) не лежит в искомой полуплоскости.
Также координаты точки M (1;  1) не удовлетворяют исходному неравенству
4  1  5  (1)  32  23  0.
Поэтому точка M не лежит в полуплоскости, которая задана исходным неравенством.
1.3. Области на плоскости
Система нескольких линейных неравенств на плоскости
X 1OX 2 может задавать:
а) ограниченный многоугольник;
б) неограниченную область;
в) пустое множество.
Пример 1.3. Система неравенств:
x1  0,


x2  0,


 x1  x2  2  0,
2 x1  x2  14  0,
(а )
(б )
(в )
(г )
задает (рис. 1.3) ограниченный четырехугольник ABCD .
Преобразуем неравенство (в): x2  x1  2 и убеждаемся, что
оно задает нижнюю полуплоскость относительно прямой AD , что
8
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
показано штриховкой снизу
(см. рис. 1.3). Преобразованное
неравенство (г): x2  2 x1  14
тоже задает нижнюю полуплоскость от прямой АВ.
x2
D
(а)
B
4
x1
7
Рис. 1.3
(б )
(в )
x2 (a)
G
задает неограниченную область
G на плоскости (рис. 1.4).
(в)
3
2
Пример 1.5. Система неравенств:
 x1  x2  8  0,
 7 x  3 x  9,
 1
2

x1  0,


x2  0
2
C
(0; 0)
Пример 1.4. Система неравенств:
3 x1  x2  3  0,
 x  x  2,
 1 2

 x1  x2  2  0,
 x1  0, x2  0
A
6
O
–1
–2
(а )
(б )
x1
2
Рис. 1.4
x2
8
(б)
задает пустое множество и не
имеет геометрического образа
на плоскости X 1OX 2 , т. е.
не имеет решений, поскольку
в первой координатной четверти верхняя полуплоскость (а)
и нижняя полуплоскость (б) не
пересекаются (рис. 1.5).
(a)
3
3
O
8
–4
Рис. 1.5
9
x1
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
1.4. Функции нескольких переменных
равно 0. Действительно, в нашем примере вектор
Линейные функции нескольких переменных, рассматриваемые
в задачах линейной оптимизации, имеют вид
n

F ( x )  F ( x1 , x 2 , ..., x n )  c1 x1  c 2 x 2  ...  c n x n   ci xi ,
AB  ( xB  x A ; yB  y A )  (2; 4)

и вектор с  (4; 2) перпендикулярны:

( AB, c )  2  4  4  2  0;
где ci – заданные числа ( i  1, ..., n ).
Уравнение
c1x1  c2 x2  ...  cn xn  h
i 1
задает гиперплоскость в n-мерном пространстве R n . В случае n  3
уравнение
c1x1  c2 x2  c3 x3  h
задает плоскость в пространстве R 3 , а в случае n  2 уравнение
c1x1  c2 x2  h

задает прямую на плоскости, причем вектор с  (c1, c2 ) перпендикулярен прямой.
Пример 1.6. Построим (рис. 1.6) прямую AB, заданную урав
нением 4 x1  2 x2  8 , и вектор с  (4; 2).
Возьмем на прямой AB
точки A(2; 0) и B(0; 4) . Для
x2
проверки перпендикулярности
прямой и вектора можно
4 B
вспомнить два факта из курса

аналитической
геометрии
с

(
4
;
2
)
2
и
векторной
алгебры:
A

а) векторы x  ( x1; x2 )
O
x
1

2 4
и y  ( y1; y2 ) перпендикулярны тогда и только тогда, когда
их скалярное произведение
 
Рис. 1.6
( x , y )  x1 y1  x2 y2
10
б) две прямые y  k1x  b1 и y  k2 x  b2 перпендикулярны тогда и только тогда, когда их угловые коэффициенты удовлетворяют
условию
1
k1k2  1 или k2   .
k1
В нашем примере прямая AB имеет уравнение x2  2 x1  4
и угловой коэффициент k1  2. Другая прямая OC , где точка
1
C  (4; 2) , имеет угловой коэффициент k2  . Условие перпенди2
1
кулярности выполняется: k1k2  (2)   1.
2
Как известно из курса математического анализа, для функции
n


F ( x )   ci xi вектор с  (c1 , c2 , ..., cn ) , состоящий из частных проi 1

изводных функции F (x )
F
F
F
 c1 ,
 c2 , ...,
 cn ,
x1
x2
xn

называется градиентом функции F (x ) и его направление является
направлением наискорейшего роста функции.
Пример 1.7. Из курса аналитической геометрии известно, что
поверхности уровня для функции

F ( x )  c1x1  c2 x2  c3 x3 ,

удовлетворяющие уравнениям F ( x )  h (при различных h ), являются плоскостями. Коэффициенты ci при переменных xi образуют
вектор – нормаль:
11
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
N  (c1; c2 ; c3 ) ,

который выше был назван с . Этот вектор направлен перпендикулярно плоскости (поверхности уровня)
c1x1  c2 x2  c3 x3  h.
Заметим также, что, по определению поверхности уровня,

функция F (x ) во всех точках данной плоскости постоянна и равна
h . В двумерном случае уравнения

F ( x )  c1x1  c2 x2  h

задают линии уровня – прямые, на которых функция F (x ) также
постоянна, а в многомерном случае – гиперплоскости уровня.
1.5. Некоторые факты из курса линейной алгебры
Для квадратной матрицы A второго порядка ее определитель
det A задается формулой
a
a
det A  11 12  a11a22  a12 a21.
a21 a22
Для квадратной матрицы A третьего порядка ее определитель
задается формулой
a11
a12
det A  a21 a22
a31
a32
a13
a23  a11a22 a33  a12 a23a31  a21a32 a13 
a33
 a13a22 a31  a12 a21a33  a11a23a32 .
Для прямоугольной матрицы A размера m  n с элементами
aij i 1,..,m; j 1,...,n матрица AT размера n  m с элементами
a 
T
ji j 1,..., n; i 1,.., m
называется транспонированной к матрице A , если
имеет место равенство
aTji  aij ,
Глава 1. Необходимые сведения из геометрии, линейной алгебры и математического…
т. е. строки и столбцы исходной и транспонированной матриц меняются местами. Операция транспонирования матриц обладает
следующими свойствами:
( AT )T  A; ( AB)T  BT AT .
Если матрица A квадратная (размера n  n ), то имеет место
равенство
det A  det AT .
Кроме того, для квадратных матриц A и B имеет место равенство
det AB  det A  det B,
а для случая прямоугольных матриц A и B согласованных размеров ( A размера m  n и B размера n  m ) имеет место равенство
det AB  det BA.

Любую линейную функцию F ( x ) , определенную в n-мерном
пространстве R n ,
n

F ( x )  c1 x1  c2 x2  ...  cn xn   ci xi
i 1

 
можно записать в виде скалярного произведения F ( x )  (c , x ) , где


c – заданный вектор c  (с1; ...; cn ) . Любую билинейную функцию
 
F ( x , y ) , определенную в nm-мерном пространстве R n  R m ,
n m
 
F ( x , y )    aij xi y j
i 1 j 1
можно записать в виде скалярного произведения
 
 
F ( x , y )  ( x , Ay ),
где А – матрица размера n  m с элементами aij i 1,..,n; j 1,...,m , причем имеет место равенство
 
 
( x , Ay )  ( AT x , y ).
j  1, ..., n, i  1, ..., m,
12
13
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 2. ГРАФИЧЕСКИЙ И СИМПЛЕКСНЫЙ МЕТОДЫ
РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ
2.1. Математические модели экономических задач
Задача 2.1. Задача о диете
Для успешного откорма животных на ферме в их еженедельном рационе необходимо иметь белков (Б) не менее 33 единиц, жиров (Ж) – не менее 23 единиц и углеводов (У) не менее 12 единиц.
У фермера есть возможность приобретать три вида кормов. Один
килограмм кормов I, II, III видов содержит белки, жиры и углеводы
в количествах, приведенных в табл. 2.1.
Таблица 2.1
Стоимость
1 кг корма
(у. е.)
300
250
200
Б Ж У
I 4
II 3
III 2
3
2
1
1
1
2
Фермеру потребуется составить наиболее дешевый рацион,
при котором животные получали бы необходимое количество белков, жиров и углеводов. Для решения этой проблемы фермер должен определить, какое количество кормов I, II, III вида он должен
закупить, чтобы обеспечить животных.
Глава1.2.Необходимые
Графическийсведения
и симплексный
методылинейной
решенияалгебры
задач линейной
оптимизации
Глава
из геометрии,
и математического…
4 x1  3x2  2 x3  33 .
Аналогичные неравенства запишем для жиров и углеводов:
3 x1  2 x2  x3  23,
x1  x2  2 x3  12.
Итак, мы получили следующую задачу:
F  300 x1  250 x2  200 x3  min
при следующих ограничениях:
4 x1  3 x2  2 x3  33,
 3 x  2 x  x  23,
2
3
 1
 x1  x2  2 x3  12,

x1  0,

x2  0,


x3  0.

(2.1)
Математически задача формулируется следующим образом:
найти неотрицательные значения переменных x1 , x2 , x3 , удовлетворяющих системе линейных неравенств (2.1), при которых линейная функция
F  300 x1  250 x2  200 x3
достигает минимального значения.
При этом общее количество белков в трех видах кормов
должно удовлетворять условию:
Задача 2.2. Задача планирования товарооборота
При продаже товаров А и В используется три вида ресурсов:
рабочее время – R1 , полезная площадь торгового зала – R 2 и упаковочный материал R3 . Торговое предприятие обеспечено этими
ресурсами в количествах соответственно 19, 13, 15 единиц. Количества ресурсов, необходимых для продажи единицы каждого товара,
даны в табл. 2.2.
Требуется составить план продажи товаров А и В, обеспечивающий максимальный товарооборот.
14
15
Решение. Обозначим через x1 , x2 , x3 – количество килограммов кормов I, II, III вида, которые купит фермер, а через F – затраты фермера. Фермер хочет минимизировать свои затраты. Запишем
это условие следующим образом:
F  300 x1  250 x2  200 x3  min .
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Таблица 2.2
R1
Товар
А В
2 3
R2
2
1
13
R3
0
3
15
Цена
(у. е.)
7
5
Ресурс
Запасы
ресурсов
19
Решение. Обозначим через x1 и x2 запланированный объем
продажи товаров А и В. По смыслу эти величины неотрицательны:
x1  0 , x2  0 . Общее количество единиц ресурса R1 , используемое
в соответствии с табл. 2.2, удовлетворяет неравенству
2 x1  3 x2  19.
Для ресурсов R2 и R3 получаем аналогичные неравенства
2 x1  x2  13 и 3 x2  15. При этом товарооборот составит 7 x1  5 x2
(у. е.), обозначим его через F.
Таким образом, задача математически формулируется так:
найти неотрицательные значения переменных x1 и x2 , удовлетворяющие системе линейных неравенств
2 x1  3 x2  19,

 2 x1  x2  13,
 3 x  15,
2

x1  0, x2  0, при которых линейная функция F  7 x1  5 x2 достигает максимума:
F  7 x1  5 x2  max .
Задача 2.3. Задача планирования производства
Цех выпускает трансформаторы двух видов. На каждый
трансформатор I вида расходуется 5 кг трансформаторного железа
16
Глава1.2.Необходимые
Графическийсведения
и симплексный
методылинейной
решенияалгебры
задач линейной
оптимизации
Глава
из геометрии,
и математического…
и 3 кг проволоки, а на каждый трансформатор II вида расходуется 3 кг
трансформаторного железа и 2 кг проволоки. У цеха имеется 480 кг
железа и 300 кг проволоки. От реализации одного трансформатора
I вида цех получает прибыль в размере 1200 рублей, а от реализации одного трансформатора II вида – 1000 рублей. Требуется построить такой план выпуска трансформаторов обоих видов из имеющихся ресурсов, чтобы прибыль от их реализации была максимальной.
Решение. Обозначим через x1 и x2 количество выпускаемых
трансформаторов соответственно первого и второго видов. Так как
цех имеет 480 кг железа, то количество железа, израсходованное на
изготовление x1 трансформаторов I вида и x2 трансформаторов
II вида, не должно превышать 480 кг, т. е.
5 x1  3 x2  480.
Рассуждая аналогично, получим второе неравенство
3 x1  2 x2  300.
Кроме того, количества трансформаторов не могут выражаться отрицательными числами, т. е. x1  0 , x2  0 . При этом прибыль
(в тыс. р.) составит:
F  1,2 x1  x 2 .
Математически задача формулируется так: найти неотрицательные значения переменных x1 и x2 , удовлетворяющих системе
линейных неравенств
5 x1  3 x2  480,

3 x1  2 x2  300,
при которых линейная функция F  1,2 x1  x2 достигает максимума:
F  1,2 x1  x2  max .
Итак, с математической точки зрения в каждой из трех экономических задач требуется найти неотрицательные значения неизвестных, при которых линейная функция достигает своего наиболь17
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
шего или наименьшего значения. Причем неизвестные должны
удовлетворять системе неравенств. Задачи такого рода исследуются
в разделе прикладной математики, который называется «линейное
программирование». Линейное программирование – математическая дисциплина, разрабатывающая методы нахождения наибольшего или наименьшего значения линейной функции нескольких
переменных при условии, что последние удовлетворяют конечному
числу линейных неравенств и уравнений.
2.2. Постановка задачи линейного программирования
Рассмотрим линейную функцию от n переменных:

F ( x )  c0  c1 x1  c2 x2  ...  cn xn ,
где c0 , c1 , c2 , ..., cn – заданные числа, x1 , x2 , ..., xn – переменные,

а x  ( x1 , x2 , ..., xn ) – вектор с компонентами из переменных. Функ
цию F (x ) будем называть целевой функцией. Введем систему линейных уравнений (и неравенств), которой удовлетворяют переменные x1 , x2 , ..., xn :
 a11 x1  a12 x2  ...  a1n xn  b1 ,

...

a x  a x  ...  a x  b .
mn n
m
 m1 1 m 2 2
(2.2)
j  1, ..., n.
(2.3)
Поставим следующую задачу: найти максимум или минимум

функции F (x ) , т. е.

F ( x )  c0  c1 x1  c2 x2  ...  cn xn  max(min),
при условии, что переменные x1 , x2 , ..., xn удовлетворяют системам
ограничений (2.2) и (2.3). Рассматриваемую задачу будем называть
18
задачей линейного программирования. Любое неотрицательное решение системы (2.2) будем называть допустимым решением (или
допустимым планом), т. е. допустимое решение – это вектор

x  ( x1 , x2 , ..., xn ) , удовлетворяющий системе (2.2) и условиям (2.3).
Множество всех допустимых решений будем называть допустимой
областью.

Допустимое решение, при котором функция F (x ) достигает
максимума (или минимума), называется оптимальным решением
(оптимальным планом) и является решением задачи линейного программирования. Если система ограничений (2.2) состоит из неравенств и не содержит равенств, то задачу будем называть общей задачей линейного программирования. Если система ограничений (2.2)
состоит только из уравнений и не содержит неравенств, то задачу будем называть основной задачей линейного программирования.
Таким образом, общая задача линейного программирования на
максимум имеет следующую математическую форму:

F ( x )  c0  c1 x1  c2 x2  ...  cn xn  max,
(2.4)
 a11 x1  a12 x2  ...  a1n xn  b1 ,

...

a x  a x  ...  a x  b ,
mn n
m
 m1 1 m 2 2
x j  0,
Систему (2.2) будем называть системой ограничений. В задачах с экономическим содержанием часто вводятся дополнительные
ограничения на знак переменных:
x j  0,
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
j  1, ..., n.
(2.5)
(2.6)
Основная задача линейного программирования на максимум
имеет следующую математическую форму:

F ( x )  c0  c1 x1  c2 x2  ...  cn xn  max,
 a11 x1  a12 x2  ...  a1n xn  b1 ,

...

a x  a x  ...  a x  b ,
mn n
m
 m1 1 m 2 2
x j  0,
j  1, ..., n.
19
(2.7)
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Из теории систем линейных уравнений известно, что если система (2.7) имеет бесконечное множество решений, то часть переменных можно выразить через оставшиеся, которые будут являться
независимыми переменными. В этом случае существуют решения
системы (2.7), у которых эти независимые переменные равны нулю.
Такие решения, если они являются допустимыми (т. е. удовлетворяют и (2.7) и (2.6)), мы назовем базисными. Переменные, выражающиеся через остальные, также назовем базисными переменными,
а переменные, через которые они выражаются, – свободными.
Систему уравнений (2.7) будем называть канонической системой, если она удовлетворяет следующим условиям:
– матрица А, составленная из коэффициентов при неизвестных, содержит столбцы, из которых можно составить единичную
подматрицу;
– правые части системы неотрицательны, т. е. bi  0,
i  1, ..., m.
Пример 2.1. Рассмотрим систему уравнений:
 a11 x1  a12 x2  x3  b1 ,

a21 x1  a22 x2  x4  b2 ,
a x  a x  x  b ,
 31 1 32 2 5 3
(2.8)
где b1  0, b2  0, b3  0,
 a11 a12

A   a21 a22
a
 31 a32
1 0 0

0 1 0 .
0 0 1 
Матрица A содержит единичную подматрицу, и правые части
системы неотрицательны. Следовательно, система (2.8) является
канонической. При этом переменные x3 , x4 , x5 , соответствующие
столбцам единичной матрицы, являются базисными, остальные переменные x1 и x2 являются свободными. Переменные x3 , x4 , x5 выражаются через x1 и x2 :
20
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
 x3  b1  (a11 x1  a12 x2 ),

 x4  b2  (a21 x1  a22 x2 ),
 x  b  (a x  a x ).
31 1
32 2
 5 3

Очевидно, что решение x  (0, 0, b1 , b2 , b3 ) – это базисное допустимое решение канонической системы (2.8).
Основную задачу линейного программирования будем называть канонической задачей, если система ограничений (2.7) является канонической и целевая функция (2.4) содержит только
свободные переменные.
2.3. Графический метод решения общей задачи
линейного программирования
Если число неизвестных n  2 , то общую задачу (2.4)–(2.6)
можно решить графически. Пусть математическая формулировка
общей задачи имеет вид

F ( x )  c0  c1x1  c2 x2  max(min),
(2.9)
 a11 x1  a12 x2  ()b1 ,

...

a x  a x  ()b ,
m2 2
m
 m1 1
x1  0,
x2  0.
(2.10)
(2.11)
Графический способ состоит в следующем.
1. Строим область допустимых решений, которая представляет собой пересечение всех полуплоскостей, которые по отдельности
являются решениями неравенств, входящих в систему ограничений
(2.10), (2.11). Если эта область является пустым множеством (как
в примере 1.5), то наша задача не имеет решения.
Напомним, что область решений линейного неравенства
ai1 x1  ai 2 x2  bi , как указывалось в примере 1.2, – одна из двух полуплоскостей, на которые прямая ai1 x1  ai 2 x2  bi делит всю координатную плоскость. Для того чтобы определить, какая из двух ко21
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
ординатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Если оно удовлетворяется, то область решений – полуплоскость, содержащая эту точку. В противном случае
областью решений является полуплоскость, не содержащая данную
точку.
2. Строим вектор градиента целевой функции

F ( x )  c0  c1x1  c2 x2 :
grad F 
F  F 
i
j,
x1
x2
в нашем случае получается:


grad F  с1i  с2 j .

3. Строим линии уровня нашей целевой функции F (x ) (прямые, перпендикулярные вектору градиента), пересекающиеся с областью допустимых решений. Если поставлена задача на максимум,
то при построении семейства линий уровня мы перемещаемся по

направлению градиента (так как в этом направлении функция F (x )
возрастает). Если поставлена задача на минимум, то мы двигаемся
в направлении, противоположном градиенту.
4. Из семейства линий уровня, пересекающихся с областью
допустимых решений, двигаясь в нужном направлении согласно
предыдущему пункту, выбираем крайнюю прямую, т. е. такую, что
любая другая линия семейства, сдвинутая в нужном направлении
на любое сколь угодно малое расстояние, уже не будет пересекать
область допустимых решений. Если область допустимых решений
ограничена, то такая крайняя прямая всегда существует. Если область допустимых решений не ограничена, то возможна ситуация,
когда такой прямой не существует: в случае задачи на максимум –
если градиент образует острый угол с любым направлением, в котором область не ограничена, в случае задачи на минимум – если
направление, противоположное градиенту, образует острый угол
с любым направлением, в котором область не ограничена. В этой
ситуации решений у задачи нет.
22
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
5. Крайняя прямая может пересекать допустимую область
в одной точке, тогда решение задачи единственное и совпадает
с координатами этой точки. Также крайняя прямая и допустимая
область могут иметь в качестве пересечения отрезок (отрезок границы допустимой области) или луч, тогда решений бесконечное
множество – это все точки данного отрезка или луча.
Пример 2.2. Решить общую задачу линейного программирования:

F ( x )  3 x1  2 x2  max,
 x1  x2  2  0,
3 x  2 x  6  0,
2
 1

x
x
2
 1
2  2  0,

x2  3,

 x1  0, x2  0.
Решение. Строим область допустимых решений задачи (рис. 2.1).
Для этого пронумеруем условия ограничения. В прямоугольной декартовой системе координат X 1OX 2 строим
прямые:
x1  x2  2  0,
(l1 )
3x1  2 x2  6  0, (l2 )
2 x1  x2  2  0, (l3 )
x2  3.
(l4 )
x2
(l1)
(l3)
B
(l2)
(l4)
2
4
x1
(*)
Рис. 2.1
Заштриховываем нужные полуплоскости и строим область
допустимых значений. 

Находим grad F  3i  2 j .
Построим линию уровня 3 x1  2 x2  h , возьмем, например
,
h  0 тогда линия уровня имеет вид
3
x2   x1. (*)
2
23
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Так как мы решаем задачу на отыскание максимума целевой
функции, то линию уровня (*) параллельно перемещаем в направлении градиента до точки выхода ее из области допустимых решений. В данном случае точка В – точка выхода. Она является точкой
пересечения прямых ( l2 ) и ( l4 ), ее координаты находим, решая систему уравнений:
3 x1  2 x2  6  0, 3 x1  2  3  6,  x1  4,



x2  3,

 x2  3,
 x2  3.
Получим В(4; 3). Вычисляем значение целевой функции в этой
точке.
F ( B )  3  4  2  3  18.

Ответ: оптимальное решение задачи xmax  (4; 3) , Fmax 
= F (B)  F (4; 3)  18.
Пример 2.3. Решить общую задачу линейного программирования:

F ( x )  3 x1  7 x2  max,
 5 x1  x2  0,
 x  x  5,
2
 1
 x2  3,
2 x  3 x  0,
2
 1
 x1  0, x2  0.
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
Определяем
полуплоскоx2 (l1)
сти, соответствующие системе
(l2)
7
ограничений. Построим область
допустимых решений. Находим
вектор градиента
функ целевой

(l3)
3
ции grad F  3i  7 j и одну из
А
линий
уровня
при
h0
(*)
3
x1
3 x1  7 x2  0 : x2   x1. (*)
3
7
(l4)
Линию уровня (*) параллельно перемещаем в направлении градиента. Поскольку в этом
Рис. 2.2
направлении область допустимых
решений не ограничена, линия
уровня уходит в бесконечность. Задача не имеет решения вследствие неограниченности целевой функции.
Замечание 2.1. Если решать задачу на минимум при тех же
ограничениях:

F ( x )  3 x1  7 x2  min,
то нужно было бы найти точку входа в область, т. е. точку А. Очевидно, что точка А есть точка пересечения прямых ( l2 ) и ( l3 ).
Найдем ее координаты, решая систему уравнений:
 x1  x2  5,  x1  5  3,  x1  2,



 x2  3,
 x2  3,
 x2  3.
Получим А(2; 3). Следовательно, оптимальное решение задачи

xmin  (2; 3) и Fmin  3  2  7  3  27.
Решение. Строим область допустимых решений (рис. 2.2).
В прямоугольной декартовой системе координат X 1OX 2 строим
прямые:
5 x1  x2  0, (l1 )
x1  x2  5,
(l2 )
x2  3,
(l3 )
2 x1  3 x2  0. (l4 )
Пример 2.4. Решить общую задачу линейного программирования:
24
25

F ( x )  4 x1  2 x2  min,
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
 4 x1  x 2  0,
 2 x  x  6,
2
 1
 x1  2 x 2  16 ,

x1  4,

 x1  x 2  0,

 x1  0, x 2  0 .
Решение. Строим область допустимых решений (рис. 2.3). В прямоугольной декартовой системе координат X 1OX 2 строим прямые:
4 x1  x 2  0,
(l1 )
2 x1  x2  6,
(l2 )
x1  2 x2  16 , (l3 )
x1  4,
(l4 )
x1  x2 .
(l5 )
Построим область допустимых

 решений. Находим градиент
целевой функции grad F  4i  2 j и одну из линий уровня
4 x1  2 x2  0 : x2  2 x1. (*)
x2
(l2)
Линию (*) перемещаем
параллельно в направлении
grad F . Очевидно, что прямая
(*) параллельна прямой (l2),
следовательно, входом является отрезок АВ. Таким образом, задача на минимум имеет бесконечное множество
решений, являющихся точками отрезка АВ. Например,
точка А (2; 2) и точка В (1; 4)
являются решениями:
(l5)
(l3)
B
2
A
(l1) (*)
(l4)
x1
Рис. 2.3
F ( A)  4  2  2  2  12; F ( B)  4  1  2  4  12.
Ответ: Fmin  12 , оптимальных решений бесконечно много –
ими являются координаты точек, принадлежащих отрезку АВ.
26
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1.

F ( x )  4 x1  4 x2  min,
 4 x1  x2  0,
2 x  2 x  6,
2
 1
 x1  2 x2  16,

x1  4,

 x1  x2  0,

 x1  0, x2  0.
Ответ: все точки отрезка [ A; B ] , где А(1,5; 1,5), В(0,6; 2,4), являются оптимальными решениями, т. е. задача имеет бесконечное
множество решений, Fmin  12.

F ( x )  4 x1  2 x2  max,
 4 x1  x2  0,
2 x  2 x  6,
2
 1
 x1  2 x2  16,

x1  4,

 x1  x2  0,

 x1  0, x2  0.

Ответ: оптимальное решение xmax  (4; 6) , Fmax  28 .
2.

F ( x )  7 x1  5 x2  max,
2 x1  3 x2  19,
 2 x  x  13,
 1
2

 3 x2  15,
 x1  0, x2  0.

Ответ: оптимальное решение xmax  (5; 3) , Fmax  50 .
3.
27
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений

F ( x )  10 x1  6 x2  max,
 3 x1  x2  19,
2 x  5 x  40,
 1
2

5 x1  4 x2  41,
 x1  0, x2  0.

Ответ: оптимальное решение xmax  (5; 4) , Fmax  74 .
4.

F ( x )  1,2 x1  x2  max,
5 x1  3 x2  480,

3 x1  2 x2  300,
 x  0, x  0.
 1
2

Ответ: оптимальное решение xmax  (0; 150) , Fmax  150 .
5.

F ( x )  2 x1  x2  max,
 x1  1  x2 ,
 x  2  4x ,
2
 1
 3 x1  2 x2  6,
4 x  5 x  20,
2
 1
 x1  0, x2  0.

 10 4 
Ответ: оптимальное решение xmax   ;  , Fmax  8 .
 3 3
6.

F ( x )  2 x1  x2  min,
 x1  x2  1,
  x  4 x  2,
2
 1
x
x

3
2
 1
2  6,
4 x  5 x  20,
2
 1
 x1  0, x2  0.

Ответ: оптимальное решение xmin  0,8; 1,8 , Fmin  3,4 .
7.
28
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
8.

F ( x )  x1  x2  max,
2 x1  3 x2  6,
 x 1 x ,
2
 1
 x1  2 x2  2,
 x  x  5,
2
 1
 x1  0, x2  0.
Ответ: все точки отрезка [ A; B ] , где А(2; 3), В(4; 1), являются
оптимальными решениями, Fmax  5. Задача имеет бесконечное
множество решений.

F ( x )  x1  x2  min,
2 x1  3 x2  6,
 x  x  1,
 1 2
 x1  2 x2  2,
 x  x  5,
2
 1
 x1  0, x2  0.

Ответ: оптимальное решение xmin  0,6; 1,6  , Fmin  2,2 .
9.

F ( x )  6 x1  2 x2  min,
 3 x1  x2  3,
 x  x  1,
 2 1

2 x2  0,5 x1  1,
 x1  0, x2  0.

Ответ: оптимальное решение xmin  (0; 1/2) , Fmin  1.
10.
29
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
2.4. Решение канонической задачи линейного
программирования симплекс-методом
Симплекс-метод применяется для решения канонической задачи и позволяет за конечное число шагов найти оптимальное решение, переходя от одного базисного допустимого решения к другому и улучшая при этом значение целевой функции.
Продемонстрируем идею этого метода при решении конкретного примера.
Пример 2.5.

F ( x )   x4  x5  max,
 x1  x4  2 x5  1,
 x  2 x  x  2,
 2
4
5

 x3  3 x4  x5  3,
 xi  0, i  1, ..., 5.
Убедимся, что задача является канонической (см. пример 2.1).
Составим матрицу из коэффициентов при неизвестных:
1 0 0 1  2


A  0 1 0  2 1 .
0 0 1 3
1 

Глава 2. Графический и симплексный методы решения задач линейной оптимизации
 x1  1  x4  2 x5 ,

 x2  2  2 x4  x5 ,
 x  3  3x  x ,
4
5
 3
F ( x )   x4  x5  max .
(2.12)
Целевая функция выражена только через свободные переменные.
Теперь мы легко найдем первое базисное решение системы ограничений (2.12). Мы его получим, положив свободные переменные равными нулю, а базисные переменные определяются из системы (2.12).

x1  (1; 2; 3; 0; 0).

Является ли это решение оптимальным? Найдем F ( x1 ) :

F ( x1 )  0. Зададимся вопросом: можно ли увеличить целевую

функцию? Да, можно, так как F ( x )   x4  x5 . Обе свободные переменные равны нулю, а x5 входит в целевую функцию со знаком
«плюс». Следовательно, если мы увеличим x5 , то увеличится и значение целевой функции. На сколько ее можно увеличить? Увеличить x5 мы можем так, чтобы при этом все базисные переменные
оставались неотрицательными. В системе ограничений (2.12) во
второе и третье уравнения x5 входит со знаком «минус». Значит, x5
мы можем увеличить настолько, чтобы x2 и x3 оставались неотрицательными. Тогда получим следующую систему неравенств:
Матрица содержит столбцы, из которых можно составить единичную подматрицу. Свободные члены в системе ограничений все
неотрицательные.
 x2  2  x5  0,  x5  2,

 x5  2

 x3  3  x5  0,  x5  3,
( x4  0 , так как это свободная переменная).
Первый этап
Переменная x5 может увеличиться до 2. Итак, x5  2 и становится новой базисной переменной, при этом x2  0 и x2 переходит
в свободные переменные. Теперь базисные переменные x1 , x3 , x5 ,
а свободные x2 , x4 . У нас изменились базисные переменные, значит,
нам необходимо систему ограничений преобразовать так, чтобы в левой части системы ограничений (2.12) находились базисные переменные. Из второго уравнения системы (2.12) выразим x5 :
Базисными переменными являются x1 , x2 и x3 , так как они соответствуют столбцам единичной подматрицы. Тогда переменные
x4 и x5 будут свободными. Выразим базисные переменные через
свободные:
x5  2  x2  2 x4 .
30
31
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Подставляя это выражение в первое и третье уравнение системы (2.12), получим
x1  1  x4  2(2  x2  2 x4 )  5  2 x2  3 x4 ,
x3  3  3x4  (2  x2  2 x4 )  1  x2  5 x4 .
Итак, система ограничений (2.12) получила вид
 x5  2  x2  2 x4 ,

(2.13)
 x1  5  2 x2  3 x4 ,
 x  1  x  5x .
2
4
 3

Целевую функцию F (x ) также надо выразить через свободные переменные:

F ( x )   x4  x5   x4  2  x2  2 x4 ,

F ( x )  2  x2  x4  max.
Второй этап
Мы вновь получили каноническую задачу и переходим

ко второму шагу решения. Находим второе базисное решение x2 .
Мы его получаем, положив свободные переменные x2 , x4 равными
нулям, а базисные переменные определяются системой (2.13)


x2  (5; 0; 1; 0; 2), F ( x2 )  2 .
Целевая функция увеличилась. На втором шаге повторяем всю
ту процедуру, которую мы проделали на первом шаге. А именно,
можно ли увеличить целевую функцию? Да, можно, увеличив x4 ,

так как x4 входит в F (x ) со знаком «плюс». Какие ограничения
имеются для увеличения x4 ? В системе (2.13) в третье уравнение x4
входит со знаком «минус», следовательно, x4 можно увеличить до
тех пор, пока x3  0 , т. е.
1
x3  1  5 x4  0  x4  , x2  0.
5
32
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
1
Полагаем x4  , тогда x3  0 . Таким образом, x4 становится
5
базисной переменной, а x3 – свободной. Итак, базисные переменные x1 , x4 , x5 , а свободные переменные x2 и x3 .
Преобразуем систему (2.13) так, чтобы в левых частях уравнений стояли базисные переменные. Из третьего уравнения получим:
x4 
1 x2 x3
  .
5 5 5
Подставляя это выражение в первое и второе уравнения системы (2.13), получим:
x  12 3
2
1 x
x5  2  x2  2  2  3    x2  x3 ,
5
5 5 5  5 5
x  18 7
3
1 x
x1  5  2 x2  3  2  3    x2  x3.
5
5
5
5
5
5


Итак, система ограничений (2.13) получила вид
1 x2 x3

 x4  5  5  5 ,
12 3
2

(2.14)
 x5   x2  x3 ,
5 5
5

 x1  18  7 x2  3 x3.

5 5
5

Целевую функцию F (x ) выразим через свободные переменные:
1 x
x 11 4
1

F ( x )  2  x2   2  3   x2  x3 ,
5 5 5
5 5
5
1
 11 4
F ( x )   x2  x3  max .
5 5
5
Третий этап
Мы вновь получили каноническую задачу с системой ограни
чений (2.14). Найдем третье базисное решение x3 :
33
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Выразим целевую функцию через свободные переменные:

F ( x )  x1  x2  x3  x4 
11
1 12 
  18

x3   ; 0; 0; ;  , F ( x3 )  .
5
5 5
5
Значение целевой функции вновь увеличилось. Можно ли еще
увеличить значение целевой функции? Нет, нельзя, так как все переменные входят в нее со знаком «минус» и при увеличении x2

и x3 значение F (x ) только уменьшится.
11


–
Следовательно, x3 – оптимальное решение, а F ( x3 ) 
5
наибольшее значение целевой функции при данной системе ограничений. Задача решена.
Рассмотрим еще один пример, решим задачу на отыскание
минимума.
Пример 2.6.

F ( x )  x1  x2  x3  x4  min,
 x1  x2  x3  1,


2 x1  x3  x4  1,

 x  0, x  0, x  0, x  0.
2
3
4
 1
 1 1 1 0
 .
A  
 2 0 1 1
Матрица содержит столбцы, из которых можно составить единичную матрицу (второй и четвертый). Свободные члены в системе
ограничений все неотрицательны.
Первый этап
Базисными переменными являются x2 и x4 , свободные переменные x1 и x3 . Выразим базисные переменные через свободные:
34
 x1  (1  x1  x3 )  x3  (1  2 x1  x3 ) 
 4 x1  x3 .


Первое базисное решение x1  (0; 1; 0; 1) , F ( x1 )  0. Можно ли
уменьшить целевую функцию? Да, можно, если увеличить переменную x3 , так как она входит в целевую функцию со знаком «минус». На сколько ее можно увеличить? Переменную x3 можно увеличить так, чтобы все базисные переменные оставались неотрицательными. В системе ограничений (2.15) в первое уравнение x3
входит со знаком «минус». Следовательно, x3 можно увеличить на
столько, чтобы x2 оставалось неотрицательной:
x2  1  x3  0  x3  1
(переменная x1  0 , так как это свободная переменная).
Убедимся, что задача является канонической. Составим матрицу из коэффициентов при неизвестных:
 x2  1  x1  x3 ,

 x4  1  2 x1  x3.
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
(2.15)
Значит, x3  1 и x3 переходит в базис, а x2 становится свободной переменной. Теперь базисные переменные – это x3 и x4 , а свободные – x1 и x2 .
Преобразуем систему ограничений (2.15) в следующую систему:
x3  1  x1  x2 ,



 x4  1  2 x1  1  x1  x2 ;
 x3  1  x1  x2 ,

 x4  2  x1  x2 .
Выразим целевую функцию через свободные переменные:

F ( x )  4 x1  x3  4 x1  (1  x1  x2 ) 
 1  3 x1  x2 .
Второй этап


Второе базисное решение x2  (0; 0; 1; 2) , F ( x2 )  1. Значение
целевой функции уменьшилось. Можно ли еще уменьшить значе35
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений

ние целевой функции? Нет, нельзя, так как F ( x )  1  3 x1  x2 , все
свободные переменные входят со знаком «плюс», а их можно только

увеличивать. Тогда значение F (x ) тоже увеличится. Следовательно,


x2  (0; 0; 1; 2) является оптимальным решением задачи, а Fmin  F(x2 )  
 1 – минимальное значение целевой функции. Задача решена.
2.5. Решение канонической задачи линейного
программирования симплекс-методом с помощью таблиц
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
Последняя (индексная) строка таблицы заполняется по следующему правилу: первый элемент совпадает со свободным членом
целевой функции c0 , остальные элементы строки равны коэффициентам при соответствующих переменных целевой функции, взятых
с противоположным знаком. Из табл. 2.3 получаем первое базисное
допустимое решение:

x1  (0; 0; b1; b2 ; b3 ).
Приведем алгоритм симплекс-метода для задачи максимизации.
Решение канонической задачи можно формализовать и проводить с помощью составления таблиц по определенному алгоритму.
Рассмотрим каноническую задачу на максимум

(2.16)
F ( x )  c0  c1x1  c2 x2  max,
 a11 x1  a12 x2  x3  b1 ,

a21 x1  a22 x2  x4  b2 ,
a x  a x  x  b ,
 31 1 32 2 5 3
xi  0, i  1, ..., 5.
(2.17)
Предполагаем, что b1  0, b2  0, b3  0. Запишем исходную
задачу в симплекс-таблицу (табл. 2.3):
Таблица 2.3
Коэффициенты
целевой функции
Коэффициенты
целевой функции при базисных переменных
0
c0
c1
c2
0
0
0
x1
x2
x3
x4
x5
x3
Столбец
правых частей системы ограничений
b1
a11
a12
1
0
0
0
x4
b2
a21
a22
0
1
0
0
x5
b3
a31
a32
0
0
1
Индексная
строка
c0
 c1
 c2
0
0
0
Базисные
переменные
36
Алгоритм
1. Проверка решения на оптимальность
1.1. Если все элементы индексной строки, кроме первого c0 ,


неотрицательны, то решение x1 – оптимальное и Fmax  F ( x1 ) . Задача решена.
1.2. Если в индексной строке существует хотя бы один отрицательный элемент, кроме первого, а над ним все элементы столбца

отрицательны, то функция F (x ) не ограничена и оптимального решения не существует. Алгоритм прекращает работу.
1.3. Если над каждым отрицательным элементом индексной
строки существует хотя бы один положительный, то исходное решение можно улучшить. Переходим к пункту 2.
2. Выбор ведущей строки, ведущего столбца, ведущего элемента
2.1. Выбираем какой-либо отрицательный элемент индексной
строки (кроме первого), над которым есть хотя бы один положительный элемент. Например, можно взять наибольший по модулю
отрицательный элемент. Столбец, соответствующий выбранному
элементу, будем называть ведущим, и его номер обозначаем j0 .
Переменную, соответствующую ведущему столбцу, вводим в число
базисных.
2.2. В ведущем столбце рассматриваем только положительные
элементы, и вычисляем отношения элементов правых частей системы ограничений к соответствующим положительным элементам
37
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
ведущего столбца. Ведущую строку определяем по наименьшему
из вычисленных отношений, и ее номер обозначаем i0 . Переменную, соответствующую ведущей строке, исключаем из числа базисных.
2.3. Ведущий элемент расположен на пересечении ведущего
столбца и ведущей строки. Обозначим его через  .
3. Составление новой симплекс-таблицы (табл. 2.4)
Пусть, например, a32 – ведущий элемент. Тогда   a32 , i0  3 ,
j0  2 . В табл. 2.3 выделяем ведущую строку и ведущий столбец.
3.1. В ведущей строке новой табл. 2.4 записываем новую базисную переменную x2 (вместо старой x5 ) и соответствующий ей
коэффициент целевой функции c2 .
3.2. Элементы ведущей строки делим на   a32 :
i0 
bi0

,  i0 j 
ai0 j

.
3.3. Элементы остальных строк, кроме последней (индексной),
получаются по формулам
i  bi  aij0
bi0

,  ij  aij  aij0
ai0 j

, i  i0 .
3.4. Вычисляем элементы индексной строки. Первый элемент
вычисляем по правилу
d 0  0  1  0   2  c23  c0 ,
т. е. d0 равен сумме произведений элементов столбца коэффициентов целевой функции при базисных переменных на соответствующие элементы столбца правых частей системы ограничений плюс
коэффициент целевой функции. Правило вычисления остальных
элементов индексной строки имеет вид
d j  0  1 j  0   2 j  c2  3 j  c j ,
38
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
т. е. d j равен сумме произведений элементов столбца коэффициентов целевой функции при базисных переменных на элементы
столбца, соответствующего переменной x j , минус коэффициент
целевой функции.
Таблица 2.4
Коэффициенты целевой функции
Коэффициенты целеБазисные
вой функции при ба- переменные
зисных переменных
x3
0
0
x4
c2
x2
c0
c1
c2
0
0
0
Столбец
правых частей системы ограничений
x1
x2
x3
x4
x5
1
11
0
1
0
15
2
 21
0
0
1
 25
1
0
0
 35 
d2
d3 d 4
d5
3 
Индексная
строка
b3
a32
d0
 31 
a31
a32
d1
1
a32
4. Переходим к пункту 1.
Пример 2.7.

F ( x )  10 x1  6 x2  max,
 3 x1  x2  x3  19,
2 x  5 x  x  40,
 1
2
4

x
x
x


4
2
5  41,
 1
 xi  0, i  1, ..., 5.
Задача является канонической. Переменные x3 , x4 , x5 базисные, а x1 , x2 – свободные. Составим первую симплекс-таблицу
(табл. 2.5).
39
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Таблица 2.5
Коэффициенты
целевой
функции
0
10
6
0
0
0
x1
x2
x3
x4
x5
3
1
1
0
0
Коэффициенты
целевой функции при базисных переменных
Базисные
переменные
0
x3
Столбец
правых частей системы ограничений
19
0
x4
40
2
5
0
1
0
0
x5
41
5
4
0
0
1
Индексная
строка
0
–10
–6
0
0
0
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
месте ведущего элемента. В ведущей строке новой табл. 2.6 записываем новую базисную переменную x1 (вместо старой x3 ) и соответствующий ей коэффициент целевой функции c1  10 . Остальные
элементы ведущего столбца, кроме последнего, с помощью элементарных преобразований превращаем в нули. Для этого к элементам
второй строки табл. 2.5 прибавляем соответствующие элементы
2
первой (ведущей) строки, умноженные на  :
3
2
82


 2
40  19      ; 2  3      0;
 3 3
 3
2
 2  13
 2
5  1     ; 0  1      ;
3
 3 3
 3
Найденное значение соответствует первой строке, которая
и является ведущей. Ведущий элемент находится на пересечении
ведущего столбца и ведущей строки и равен 3. После этого выделим в табл. 2.5 ведущий столбец и ведущую строку (заштрихуем
карандашом или выделим цветным маркером).
Составим новую симплекс-таблицу (табл. 2.6). Переменную
x1 , соответствующую ведущему столбцу, вводим в базис, а переменную x3 , соответствующую ведущей строке, выводим из базиса.
Ведущую строку делим на 3 (ведущий элемент) и получаем 1 на
 2
 2
1  0      1; 0  0      0.
 3
 3
Результаты вычислений записываем во вторую строку табл. 2.6.
Аналогично пересчитываем третью строку. К элементам третьей
строки прибавляем элементы первой (ведущей) строки, умножен5
ные на  :
3
 5  28
 5
41  19      ; 5  3      0;
 3 3
 3
5
 5
 5 7
4  1     ; 0  1      ;
3
 3
 3 3
 5
 5
0  0      0; 1  0      1.
 3
 3
Результаты вычислений записываем в третью строку табл. 2.6.
Далее вычисляем элементы индексной строки. Для нахождения
первого элемента суммируем произведения элементов первого
столбца (коэффициенты целевой функции при базисных переменных) и третьего столбца и прибавляем коэффициент целевой функции c0  0 .
19
82
28
190
10   0   0   0 
.
3
3
3
3
40
41
Так как индексная строка содержит отрицательные элементы,

базисное решение x1  (0, 0, 19, 40, 41) не является оптимальным.
Выберем наименьший отрицательный элемент в индексной строке,
равный  10 . Расположенный над ним столбец – ведущий. Для
определения ведущей строки для всех положительных элементов
ведущего столбца находим наименьшее из отношений соответствующих элементов столбца, содержащего правые части системы
ограничений, и ведущего столбца.
19 40 41 19
min  , ,   .
3 2 5 3
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Для нахождения второго элемента суммируем произведения
элементов первого и четвертого столбцов и отнимаем коэффициент
целевой функции c1  10 :
10  1  0  0  0  0  10  0.
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
Из табл. 2.6 находим второе базисное решение. Значения базисных переменных находятся в столбце правых частей системы
ограничений. Значения свободных переменных равны нулю. Тогда
получаем:
x1 
Аналогично находим остальные элементы индексной строки:
1
13
7
8
10   0   0   6   ;
3
3
3
3
1
10
 5
 2
10   0      0      0  ;
3
3
 3
 3
10  0  0  1  0  0  0  0;
или
Найденные значения записываем в последнюю строку табл. 2.6.
Таблица 2.6
0
Столбец
Коэффициенты
правых чацелевой функБазисные
стей систеции при базиспеременные
мы ограниных переменчений
ных
19
x1
10
3
82
x4
0
3
28
x5
0
3
190
Индексная
строка
3
42
10
x1
1
0
0
0
6
x4 
82
;
3
x5 
28
;
3
x2  0;
x3  0
82 28 
  19
x2   ; 0; 0; ; .
3
3 3

10  0  0  0  0  1  0  0.
Коэффициенты целевой функции
19
;
3
0
x2
x3
1
3
13
3
7
3
8

3
1
3
2

3
5

3
10
3
0
0
x4
x5
0
0
1
0
0
1
0
0
8
Индексная строка содержит отрицательный элемент  . Сле3

довательно, решение x2 не является оптимальным и мы продолжаем решение задачи.
8
Ведущий столбец находится над элементом  , ему соответ3
ствует переменная x2 , которую введем в базис.
19 1 82 13 28 7  28 7
min  : ;
: ;
:   :  4.
 3 3 3 3 3 3 3 3
Полученному значению соответствует третья строка, которая
становится ведущей. Переменная x5 выводится из базиса, а переменная x2 вводится в базис. Ведущую строку и ведущий столбец
табл. 2.6 выделяем штриховкой или цветным маркером. Строим
следующую симплекс-таблицу (табл. 2.7), используя табл. 2.6.
7
Элементы ведущей строки делим на ведущий элемент и по3
лучаем 1 на месте ведущего элемента. Остальные элементы ведущего столбца, кроме последнего, с помощью элементарных преобразований превращаем в нули. Для этого к элементам второй строки прибавляем соответствующие элементы третьей (ведущей)
13 7
13
строки, умноженные на  :   :
3 3
7
43
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
Таблица 2.7
82 28  13 
 13 
      10; 0  0      0;
3
3  7
 7
13 7  13 
2  5   13  17
      0;           ;
3 3  7
3  3  7  7
13
 13 
 13 
1  0      1; 0  1       .
7
 7
 7
К элементам первой строки прибавляем соответствующие
1 7
1
элементы третьей строки, умноженные на  :   :
3 3
7
19 28  1 
 1
      5; 1  0      1;
3
3  7
 7
1 7  1
1  5  1 4
     ;
      0;
3 3  7
3  3  7  7
1
 1
 1
0  0      0; 0  1       .
7
7
7




Приведем вычисления элементов индексной строки:
10  5  0  10  6  4  0  74; 10  1  0  0  6  0  10  0;
7
17
10
 5
10  0  0  0  6  1  6  0; 10   0   6      0  ;
4
7
7
 7
8
 13 
3
 1
10  0  0  1  6  0  0  0; 10      0      6     0  .
7
 7
 7
7
Коэффициенты целевой
функции
0
10
6
0
0
0
Коэффициенты
целевой функции
при базисных
переменных
Базисные
переменные
Столбец правых частей
системы
ограничений
x1
x2
x3
x4
x5
10
x1
5
1
0
0
x4
10
0
0
6
x2
4
0
1
Индексная
строка
74
0
0
0
1
0
0
1
7
13

7
3
7
8
7

Индексная строка не содержит отрицательных элементов, сле

довательно, решение x3 – оптимальное. Целевая функция F ( x )
имеет вид
10
8

F ( x )  74  x3  x5 .
7
7

Следовательно, F ( x3 )  74 . Итак, максимальное значение целевой функции Fmax  74 при заданной системе ограничений. Задача решена.
Найденные значения запишем в последнюю строку табл. 2.7.
Из табл. 2.7 находим третье базисное решение

x3  (5; 4; 0; 10; 0).
44
4
7
17
7
5

7
10
7
45
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1.
2.
3.
4.
5.
Глава 2. Графический и симплексный методы решения задач линейной оптимизации
6.

F ( x )  2 x1  x2  max,
 2 x1  x2  x3  6,
 x  2 x  x  5,
 1
2
4

x
x
x


5  8,
 1 2
 xi  0, i  1, ..., 5.
7.

F ( x )  5 x1  x2  min,
 x1  2 x2  3 x4  2,

 x2  2 x4  1,
 x  0, i  1, ..., 4.
 i
8.

F ( x )  2 x1  x4  max,
 x1  5 x3  2 x4  x5  15,
 x  2 x  x  5,

2
4
5

6 x3  x6  28,

 xi  0, i  1, ..., 6.

F ( x )  x1  x2  min,
 x1  2 x2  x4  2,
 x  x  2 x  1,
 2 3
4

 x3  x4  x5  5,
 xi  0, i  1, ..., 5.

F ( x )  2 x1  x2  max,
 x1  x 2  x3  5,

 x1  x 2  x 4  2,
 x  0, i  1, ..., 4.
 i

F ( x )  x1  x2  x3  x4  x5  x6  min,
 x1  x4  6 x6  9,
3 x  x  4 x  2 x  2,
 1 2
3
6

 x1  2 x3  x5  2 x6  6,
 xi  0, i  1, ..., 6.

F ( x )  x1  x3  min,
 x1  2 x2  x3  1,

 x1  3 x2  x4  2,
 x  0, i  1, ..., 4.
 i

F ( x )  3 x1  2 x2  max,
 x1  2 x2  50,
 x  x  20,
 2 4

 x3  2 x4  30,
 xi  0, i  1, ..., 4.
46
47
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 3. ТЕОРИЯ ДВОЙСТВЕННОСТИ
3.1. Матричная форма записи задач линейного
программирования
Рассмотрим общую задачу линейного программирования
(2.4)–(2.6) из предыдущего раздела:

F ( x )  c0  c1x1  c2 x2  ...  cn xn  max,
 a11 x1  a12 x2  ...  a1n xn  b1 ,

...

a x  a x  ...  a x  b ,
mn n
m
 m1 1 m 2 2
x j  0, j  1, ..., n.
Будем рассматривать только случай c0  0 . Очевидно, что, добавляя или отнимая ненулевую константу от целевой функции, мы
всегда можем свести любую общую задачу к данному случаю, не
изменяя точку оптимального решения. В этом случае согласно
пункту 1.5 целевую функцию можно записать в виде скалярного
произведения векторов:

 
F ( x )  c1x1  c2 x2  ...  cn xn  (c , x ).
Тогда условия на целевую функцию можно всегда переписать
в виде

 

 
F ( x )  (c , x )  max или  F ( x )  (c , x )  min .
Кроме того, не ограничивая общности, можно считать, что
в условиях (2.5) все знаки неравенств смотрят в одну сторону « »,
в противном случае достаточно умножить соответствующее неравенство на «  1». Системы неравенств (2.5) и (2.6) также можно записать в матричном виде
  
Ax  b и x  0 ,
где под неравенствами векторов понимаются покоординатные неравенства:

( Ax )i  bi , i  1, ..., m , x j  0, j  1, ..., n.
48
Глава
3. Теория
двойственности
Глава 2. Графический и симплексный методы решения
задач
линейной
оптимизации
Таким образом, общую задачу линейного программирования
(2.4)–(2.6) всегда можно записать в матричном виде

 
 F ( x )  (c , x )  max,
 

Ax  b ,
(3.1)



x  0.

3.2. Двойственность задач линейного программирования
в симметричной постановке
Назовем взаимно двойственными следующие две общие задачи линейного программирования:
 


 
 Z ( y )  (b , y )  min,
 F ( x )  (c , x )  max,


 
 
Ax  b ,
AT y  c ,
 





x  0;
y  0.


Обращаем внимание на соглашение: задача на максимум ставится с матричными условиями со знаком «  », а задача на мини
мум ставится с матричными условиями со знаком «  »; вектор c ,
определяющий целевую функцию исходной задачи, стоит в правой
части матричных
условий двойственной задачи (то же самое для

вектора b ); матрицы условий A и AT транспонированы друг к дру 
гу; оба вектора x и y неотрицательны.
Очевидно, что взаимно двойственными в смысле указанного
выше определения являются также задачи:
 

 

Z ( y )  (b , y )  max,
 F ( x )  (c , x )  min,
 
 


Ax  b ,
AT y  c ,
 





x  0;
y  0,


т. е. определение симметрично.
49
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 3. Теория двойственности
Пример 3.1. Рассмотрим задачу линейного программирования:

 F ( x )  x1  2 x2  3 x3  min,

2 x1  2 x2  x3  2,


 x1  x2  4 x3  3,

x1  x2  2 x3  6,


2 x1  x2  2 x3  3,

x1  0, x2  0, x3  0.

Задача состоит в нахождении оптимального количества единиц выпуска x1 и x2 продукции обоих видов, при которых прибыль
будет максимальна при заданных ограничениях запасов. Она формулируется в виде
Двойственной к ней является следующая задача:

 Z ( y )  2 y1  3 y2  6 y3  3 y4  max,

2 y1  y2  y3  2 y4  1,

2 y1  y2  y3  y4  2,


 y1  4 y2  2 y3  2 y4  3,

y1  0, y2  0, y3  0, y4  0.

Пример 3.2. (Экономический смысл двойственности.) Рассмотрим задачу об оптимальном выпуске. При выпуске двух видов
продукции P1 и P2 на производстве используют три вида ресурсов
S1 , S2 и S3 , запасы которых составляют 20, 40 и 30 единиц соответственно. Известно, что отпускные цены на продукцию обоих видов
составляют 50 и 40 денежных единиц (у. е.) соответственно, а затраты ресурсов на единицу выпуска заданы в табл. 3.1.
Таблица 3.1
Продукция
Ресурсы
S1
P1
P2
2
5
Запасы
20
S2
8
5
40
S3
5
50
6
40
30
Цены (у. е.)
50

 F ( x )  50 x1  40 x2  max,

2 x1  5 x2  20,

8 x1  5 x2  40,


5 x1  6 x2  30,


x1  0, x2  0.
Тогда двойственная ей задача примет вид

Z ( y )  20 y1  40 y2  30 y3  min,

2 y1  8 y2  5 y3  50,


5 y1  5 y2  6 y3  40,


x1  0, x2  0.
Это задача о минимизации затрат: двойственные оценки
должны быть такими, чтобы общая оценка стоимости сырья, используемого на производство единицы продукции каждого вида,
была не меньше цены единицы продукции данного вида (поэтому
yi называются неявными ценами), при этом минимизируется общая
стоимость сырья, равная сумме произведений запасов сырья на неявные цены.
3.3. Двойственность задач линейного программирования
в несимметричной постановке
Несимметричность в постановке двойственных задач появляется, когда в исходной задаче вместо неравенств « » или « » имеется условие типа равенство «  ». Тогда двойственными являются
задачи
51
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений

 
 F ( x )  ( c , x )  min,
 

Ax  b ,



x0

и

 
 F ( x )  ( c , x )  max,
 

Ax  b ,



x0


 

 Z ( y )  (b , y )  max,
 

AT y  c ,



y  0


 

 Z ( y )  (b , y )  min,

 
AT y  c ,



y  0 .

Символ «  » означает, что знак переменной не фиксирован.
Таким образом, условию типа «равенство» в исходной задаче соответствует переменная нефиксированного знака в двойственной,
и наоборот, переменной нефиксированного знака соответствует
условие типа «равенство».
Пример 3.3. Рассмотрим задачу линейного программирования:

 F ( x )  2 x1  x2  30 x3  max,

2 x1  x2  6 x3  12,


3 x1  5 x2  12 x3  14,


x1  0, x2  0, x3  0.
Двойственной ей является задача

Z ( y )  12 y1  14 y2  min,

2 y1  3 y2  2,

 y1  5 y2  1,


6 y1  12 y2  30,


y1  0, y2  0.
Пусть исходная задача – это задача на минимум:
Глава 3. Теория двойственности
Тогда в ней первое неравенство системы ограничений умножается на –1, чтобы сменить знак неравенства на согласованный
с задачей на минимум знак «  », и двойственная задача будет следующей:

Z ( y )  12 y1  14 x2  max,

 2 y1  3 y2  2,

y1  5 y2  1,


 6 y1  12 y2  30,


y1  0, y2  0.
3.4. Теоремы двойственности
Двойственность задач линейного программирования позволяет
решать их наиболее рациональным способом благодаря ряду свойств
двойственных задач. Самым простым является следующее свойство:


для взаимно двойственных задач F ( x )  min и Z ( y )  max при
 
всех допустимых x и y всегда верно соотношение


max Z ( y )  min F ( x ) .
Докажем его для случая симметричной постановки (для
несимметричной доказательство аналогично). Умножив неравенства системы ограничений первой задачи
n
 aij x j  bi ,
i  1,..., m
j 1
на yi и просуммировав по i , получим:
m
n
m n
m

y
a
x

a
x
y

 i  ij j   ij j i  yibi  Z ( y ).
i 1
j 1
i 1 j 1
i 1

 F ( x )  2 x1  x2  30 x3  min,

2 x1  x2  6 x3  12,


3 x1  5 x2  12 x3  14,


x1  0, x2  0, x3  0.
Аналогично, умножив на x j неравенства системы ограничений второй задачи, получим
52
53
m
n
n

  aij x j yi   x j c j  F ( x ).
i 1 j 1
j 1
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений



Таким образом, F ( x )  Z ( y ) для всех допустимых векторов x

и y , а значит, это же неравенство верно и для решений задач.
Но на самом деле верно гораздо более сильное утверждение,
называемое Первой теоремой двойственности.
Теорема 3.1. Для двух взаимно двойственных задач линейного


программирования F ( x )  min и Z ( y )  max реализуется одна из
следующих альтернатив:


1) у обеих задач и F ( x )  min и Z ( y )  max есть решения


xmin и ymax соответственно, причем


F ( xmin )  Fmin  Z max  Z ( ymax );
2) если одна из целевых функций на своем допустимом множестве не ограничена, то множество допустимых решений

другой пусто, т. е. если F ( x )  , то система ограничений


на y несовместна, а если Z ( y )   , то система ограниче
ний на x несовместна, и, таким образом, решений (конечных)
у обеих задач нет;


3) оба допустимых множества для x и y пусты, и решений
у обеих задач нет.
Альтернативы 2 и 3 позволяют легко доказать отсутствие решений у задачи. Достаточно проверить несовместность ограничений либо прямой, либо двойственной задач. Альтернатива 1 позволяет найти значение целевой функции на решении задачи наиболее
рациональным путем: поскольку Fmin  Z max , то из обеих двойственных задач достаточно решить лишь одну. Выбирается наименее трудоемкая из них, например та, которая содержит меньше
уравнений и неизвестных после приведения к каноническому виду
(если ее можно решить симплекс-методом), или та, которая содержит всего две переменные (она может быть решена графически).
Затем, если необходимо, решается оставшаяся задача. Причем,
кроме уже известного значения целевой функции, ее можно упро54
Глава 3. Теория двойственности
стить, используя условия дополняющей нежесткости, вытекающие
из следующей Второй теоремы двойственности.
Теорема 3.2. Если две взаимно двойственные
задачи с целевы 


 
ми функциями F ( x )  (c , x ) и Z ( y )  (b , y ) и матрицами систем
ограничений A и AT имеют решения, то на этих решениях выполнены следующие соотношения:
 n

yi   aij x j  bi   0, i  1, ..., m;
 j 1

 n

x j   aij yi  c j   0,
 i 1

j  1, ..., n.
Следствием этой теоремы являются следующие условия (дополняющей нежесткости):
1) если в решении двойственной задачи компонента не равна
нулю ( xk  0 или yl  0 ), то в условии, соответствующем номеру этой компоненты, на решении обязательно реализуется
равенство, т. е.
n
 alj x j  bl
или
j 1
n
 aik yi  ck ,
i 1
и тогда данное условие называется закрепленным;
2) если в решении двойственной задачи компонента равна нулю ( xk  0 или yl  0 ), то в условии, соответствующем номеру
этой компоненты, на решении, вообще говоря, равенство не
обязательно реализуется, и тогда данное условие называется
свободным.
Очевидно, что свободные условия, как не реализующиеся на решении задачи, можно отбросить и оставить только закрепленные. Затем добавить к ним в качестве еще одного условия целевую функцию,
приравненную к уже найденному из двойственной задачи значению на
ее решении, и найти решение исходной задачи из получившейся си55
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
стемы линейных уравнений. Причем заранее зная, что данная система
совместна. Кроме того, верно и обратное рассуждение: если на решении двойственной задачи в одном из условий реализуется строгое неравенство, то данное условие является свободным и в решении исходной задачи соответствующая номеру этого условия компонента равна
нулю, а значит, систему линейных уравнений на это решение можно
упростить, обнулив соответствующую переменную.
Пример 3.4. Решим первую пару двойственных задач из примера 3.3:

 F ( x )  2 x1  x2  30 x3  max,

2 x1  x2  6 x3  12,


3 x1  5 x2  12 x3  14,


x1  0, x2  0, x3  0
и

Z ( y )  12 y1  14 y2  min,

2 y1  3 y2  2,

 y1  5 y2  1,


6 y1  12 y2  30,


y1  0, y2  0.
y2
(l1)
2
(l2)
5
y1
9
(l3)
Очевидно,
что
выгоднее сначала решать вторую задачу,
поскольку в ней только две переменные,
а значит, она решается
графически (рис. 3.1).
Построим допустимое
множество и отметим
направление градиента целевой функции.
Глава 3. Теория двойственности

Решением, очевидно, является точка ymin  9; 2  , а соответствующее значение Z min  12  9  14  2  136 . Причем первое неравенство 2 y1  3 y2  2 системы ограничений на этом решении реализуется строго, так как 2  9  3  2  24  2 . Значит, это условие
свободно и в решении первой задачи x1  0. Составим систему линейных уравнений для поиска решений первой задачи из обеих
условий (которые, очевидно, оба закреплены ввиду ненулевых y1
и y2 в решении двойственной задачи), где x1  0 :
 x 2  6 x3  12;
37
38
 x 2  6 x3  12  x3  ; x 2  .

9
3
 5 x 2  12 x3  14
37
38
; x2 
в целе9
3
 Z min (т. е. что мы
Подставим найденное решение x1  0; x3 
вую функцию F , чтобы убедиться, что F max
нашли решение):
38
37 408
F max  2  0   30  
 136.
3
9
3
Следствием теоремы 2.3 является следующее утверждение,
называемое Третьей теоремой двойственности.
Теорема 3.3. Малым изменениям правых частей bi условий
прямой задачи соответствуют изменения F значения целевой
функции на решении, пропорциональные соответствующим значениям yi решения двойственной задачи:
F  bi yi .
Собственно, для свободных условий (когда yi  0 ) утверждение очевидно: малые изменения их правых частей вообще никак не
повлияют на решение, так как ограничения все равно не достигнутся.
Рис. 3.1
56
57
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Глава 3. Теория двойственности
5.
Решить задачу переходом к двойственной задаче:
1.
2.
3.
4.

 F ( x )  9 x1  x2  x3  max,

3 x1  2 x2  x3  1,


 x1  3 x2  4 x3  3,


xi  0, i  1, 2, 3.
6.

 F ( x )  16 x1  28 x2  8 x3  min,

 2 x1  4 x2  4 x3  3,


9 x1  3 x2  2 x3  4,


xi  0, i  1, 2, 3.
7.

 F ( x )  18 x1  x2  5 x3  max,

4 x1  x2  5 x3  1,


3 x1  2 x2  4 x3  4,


xi  0, i  1, 2, 3.
8.

 F ( x )  18 x1  25 x2  8 x3  max,

6 x1  5 x2  11x3  6,


 x1  2 x2  5 x3  1,


xi  0, i  1, 2, 3.
58
9.

 F ( x )  25 x1  8 x2  14 x3  min,

 x1  5 x2  4 x3  2,


5 x1  6 x2  x3  2,


xi  0, i  1, 2, 3.

 F ( x )  42 x1  6 x2  24 x3  min,

5 x1  2 x2  8 x3  1,


2 x1  x2  x3  5,


xi  0, i  1, 2, 3.

 F ( x )  6 x1  18 x2  2 x3  min,

3 x1  x2  4 x3  3,


 7 x1  3 x2  2 x3  1,

 xi  0, i  1, 3, x2  0.

 F ( x )  32 x1  18 x2  50 x3  min,

x1  x2  5 x3  1,


4 x1  2 x2  2 x3  1,


xi  0, i  1, 2, 3.

 F ( x )  2 x1  x2  x3  max,

2 x1  x2  6 x3  12,


 3 x1  5 x2  12 x3  14,

xi  0, i  1, 2, 3.
59
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
10.

 F ( x )  3 x1  5 x2  6 x3  min,

2 x1  5 x2  7 x3  12,


3 x1  2 x2  10 x3  17,


xi  0, i  1, 2, 3.
Глава 3. Теория двойственности
Глава 4. ТРАНСПОРТНАЯ ЗАДАЧА
4.1. Математическая модель и постановка транспортной задачи
Сформулируем задачу линейного программирования, называемую транспортной задачей (ТЗ).
Имеется m пунктов отправления (баз, складов) A1, A2 , …, Am ,
на которых хранятся запасы однородного груза (товара, сырья)
в количествах a1, a2 , …, am . Груз надо вывезти в n пунктов назначения (в магазины или к потребителям) B1, B2 , …, Bn , которые подали заявки на b1, b2 , …, bn единиц груза. Известна стоимость перевозки единиц груза из пункта Ai ( i  1, ..., m ) в пункт B j
( j  1, ..., n ). Она составляет cij денежных единиц (у. е.). Предположим, что стоимость перевозки товара прямо пропорциональна количеству этого товара. Требуется составить такой план перевозки
грузов, при котором:
а) весь груз со складов будет вывезен;
б) все заявки потребителей будут удовлетворены;
в) суммарная стоимость всех перевезенных грузов будет минимальной.
Если сумма всех запасов груза в пунктах отправления равна
сумме потребностей в пунктах назначения, т. е.
m
n
i 1
j 1
 ai   b j ,
то ТЗ называется задачей закрытого типа (ЗТЗ).
Если же
m
n
i 1
j 1
 ai   b j ,
то задачей открытого типа (ОТЗ). Такие задачи ОТЗ мы будем
приводить к задачам ЗТЗ (см. п. 4.2).
Составим математическую модель ТЗ. Пусть xij – количество
груза, которое требуется перевезти из пункта Ai в пункт B j . Эти
60
61
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
неотрицательные переменные xij  0 (в количестве m  n штук)
должны удовлетворять следующим условиям:
n
 x ij  ai , i  1, ..., m;
(4.1)
j 1
m
 xij  b j ,
j  1, ..., n.
i 1
... c1n 

... c2 n 
,
... ... 

... cmn 
m
n
i 1 j 1
(4.3)
i, j
которую надо минимизировать. Заметим, что условие (4.1) выражает необходимость вывезти весь груз со складов Ai . Условие (4.2)
описывает необходимость удовлетворения всех заявок потребителей B j .
Ясно, что в таком виде ТЗ (4.1)–(4.3) является основной задачей
линейной оптимизации (линейного программирования (ЛП)) и может быть решена стандартным симплекс-методом (см. п. 2.3, 2.4),
как и любая задача ЛП. Однако в силу специфики ограничений
(4.1)–(4.2) ее можно решить более простым методом, который является частным случаем симплекс-метода.
62
Матрицу перевозок X  {xij }, i  1, ..., m, j  1, ..., n , часто
называют планом перевозок или планом ТЗ (4.1)–(4.3).
Для удобства записи составляем транспортную табл. 4.1.
Таблица 4.1
Потребности
B1
b1
Запасы
A1
a1
A2
a2
...
…
Am
которая называется матрицей тарифов (или тарифной матрицей).
Введем целевую функцию
F    c ij xij  cij xij  min,
4.2. Основные понятия и факты ТЗ
(4.2)
Эти уравнения являются системой ограничений в ТЗ. Таким
образом, можно сказать, что имеется неизвестная матрица X  {xij }
размера m  n , которая называется матрицей перевозок.
Задана матрица размера m  n
 c11

c
C   21
...

 cm1
Глава
Глава
3. Теория
4. Транспортная
двойственности
задача
...
b2
…
c11
c12
c21
c 22
…
…
c m1
am
B2
cm 2
…
…
…
…
Bn
bn
c1n
c2 n
…
c mn
В левых верхних углах клеток вписываем тарифы перевозок cij .
Неотрицательные матрицы X  {xij }, удовлетворяющие системе (4.1)–(4.2), являются допустимыми планами (решениями) задачи оптимизации (4.1)–(4.3).
План X * из множества допустимых планов, на котором целевая функция (4.3) достигает минимума, называется оптимальным
планом перевозок.
Так как 0  xij  min{ai , b j }, то множество допустимых планов
ограничено. Так как функция (4.3) линейная и поэтому непрерывная, то по теореме Вейерштрасса она достигает своего наименьшего значения на множестве допустимых планов. Мы таким образом
доказали, что существует план перевозок X * , такой что
min F ( X )  F ( X *).
X
Утверждение 4.1. Для того чтобы система ограничений
(4.1), (4.2) была совместна, необходимо и достаточно, чтобы
63
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
m
n
i 1
j 1


m
i 1  j 1

i 1


n

j 1
 ai   b j .
(4.4)
Доказательство
Необходимость.
m
n
   xij   ai ,
n
m
   xij    b j .
j 1 i 1
Поскольку левые части этих равенств равны, то и правые части тоже должны быть равны.
Достаточность. Доказательство здесь не приводим.
Можно переформулировать это утверждение: ЗТЗ имеет хотя
бы одно решение, т. е. по крайней мере один оптимальный план Х*
существует.
Если рассматривать ТЗ открытого типа, то поступают следующим образом. Если
m
n
i 1
j 1
 ai   b j ,
то есть запасов больше, чем требуется вывезти по заявкам, то вводят фиктивного потребителя Bn 1 с потребностями
m
n
i 1
j 1
bn 1   ai   b j .
Если же
m
n
i 1
j 1
 ai   b j ,
то вводят фиктивного поставщика Am 1 с запасом груза
n
m
j 1
i 1
am 1   b j   ai .
64
Глава
Глава
3. Теория
4. Транспортная
двойственности
задача
Стоимость всех фиктивных перевозок можно принять равной
0 (у. е.).
Опорным планом ЗТЗ называется такой допустимый план
X  {xij }, в котором (m  1)  (n  1) компонент равны нулю,
а остальные неотрицательны. Оптимальное решение, как и раньше,
содержится среди опорных решений, которые геометрически совпадают с вершинами выпуклого многогранника допустимых планов ТЗ.
Всего в ТЗ m  n неизвестных xij , а число уравнений в системе
(4.1)–(4.2) равно m  n . Еще предполагается выполнение условия
(4.4). Поэтому в опорном плане ЗТЗ может быть не более m  n  1
отличных от нуля неизвестных.
Если количество ненулевых компонент в опорном плане равно
в точности m  n  1 , то план называется невырожденным, а если
меньше, то вырожденным.
Для нахождения первоначального опорного плана существует
несколько методов, например метод северо-западного угла или метод наименьшего тарифа.
Приведем здесь только метод наименьшего тарифа. Другие
методы описываются, например, в [4].
4.3. Метод наименьшего тарифа
В транспортной таблице сначала заполняются клетки с минимальным тарифом. При этом либо удовлетворяются заявки соответствующего потребителя, либо исчерпывается запас склада (поставщика). Далее клетки заполняются в порядке возрастания тарифов
перевозок.
Пример 4.1. Четыре строительные фирмы B1 , B2 , B3 , B4 нуждаются в строительных материалах соответственно: 100, 50, 160,
130 (ед.). Строительные материалы находятся на трех складах A1 ,
A2 , A3 с запасами соответственно: 80, 160, 200 (ед.). Известна тарифная матрица перевозок:
8 2 4 6


C  {cij }   3 5 4 7 .
 4 10 3 5 


65
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Мы имеем ТЗ закрытого типа, так как сумма грузов и сумма
потребностей равны 440 (ед.).
Составим транспортную таблицу 4.2.
Таблица 4.2
B1
Потребности
Запасы
A1
80
100
B2
50
B3
B4
160
130
8
2
4
6
A2
160
3
5
4
7
A3
200
4
10
3
5
Таблица 4.3
A2
A3
Переходим к клетке ( A3 , B3 ) с тарифом c33 = 3 . В ней ставим
160. В остальных клетках третьего столбца ставим точки. Оставшиеся запасы со складов вывозим в фирму B4 : со склада A1 – оставшиеся 30 ед., со склада A2 – 60 ед., со склада A3 – 40 ед. Тем самым
потребности фирмы B4 , равные 30 + 60 + 40 = 130 ед., удовлетворены. Мы получили начальный опорный план перевозок:
 0 50 0 30 


X 1 = 100 0
0 60 .
 0
0 160 40 

Стоимость такого плана вычисляется по формуле (4.3).
Построим методом наименьшего тарифа опорный план ЗТЗ.
Начинаем заполнять табл. 4.3 с клетки (А1, B2 ) с наименьшим
тарифом c12 = 2 . За счет запасов склада A1 все потребности фирмы
B2 в количестве 50 ед. будут удовлетворены, вписываем в эту клетку (крупно) число 50. Эта клетка считается базисной, так как с других
складов в B2 более ничего не повезем. Ставим в клетках ( A2 , B2 )
и ( A3 , B2 ) точки (вместо нулей). Эти клетки считаем свободными.
Потребности
Запасы
A1
80
Глава 3. Теория двойственности
B1
100
8
160
3
200
4
•
100
•
B2
50
2
50
5
10
•
•
B3
160
4
4
3
•
•
160
B4
130
6
30
7
60
5
40
Следующий по величине тариф, равный 3, стоит в клетках
( A2 , B1 ) и ( A3 , B3 ). Можно выбрать любую из них, например
( A2 , B1 ). Со склада A2 вывезем в B1 все 100 ед. строительных материалов, ставим в этой клетке 100. В других клетках первого столбца
ставим точки, так как все запросы фирмы B1 удовлетворены.
66
F =  cij xij = 3 ⋅ 100 + 2 ⋅ 50 + 6 ⋅ 30 + 7 ⋅ 60 + 3 ⋅ 160 + 5 ⋅ 40 = 1680 (у. е.).
i, j
Заметим, что число заполненных клеток в транспортной табл. 4.3
равно
m + n − 1 = 3 + 4 − 1 = 6.
Замечание 4.1. При построении опорного плана перевозок на
каждом шаге либо исчерпывался запас склада Ai , либо полностью
выполнялись запросы потребителя B j . Но в других примерах может получиться так, что на некотором (не последнем) шаге одновременно будет удовлетворяться запрос потребителя и исчерпываться запас склада. Тогда число заполненных клеток будет меньше, чем m + n − 1 . В этом случае надо записать нулевую перевозку
в ту клетку (в той же строке), которая заполнялась бы, если бы
остаток запаса данного склада не был бы равен нулю. Эта клетка
далее считается базисной.
Пример 4.2. Построим новый опорный план перевозок для
следующей транспортной табл. 4.4.
Следуя методу наименьшего тарифа, начинаем с клетки
( A1 , B2 ) с тарифом c12 = 2 (табл. 4.5). Вывозим с базы A1 все 40 ед.
груза потребителю B2 . Сразу заявка потребителя B2 выполнена,
67
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
поэтому в первой строке надо поставить нулевую перевозку в клетке ( A1 , B3 ) с меньшим тарифом c13 = 3 . Затем в клетку ( A2 , B1 ) с тарифом c21 = 3 ставим 30 ед. Оставшуюся клетку ( A2 , B3 ) заполняем
числом 20 ед.
Таблица 4.4
Потребности B1
Запасы
30
4
A1
40
A2
50
3
B2
B3
40
20
2
3
5
6
A2
50
B1
B2
B3
30
40
20
4
2
3
3
•
30
5
40
•
6
 x11 + x12 + x13 = 110,
 x + x + x = 90,
23
 21 22
 x31 + x32 + x33 = 85,
xij ≥ 0, i = 1, 2, 3,

 x11 + x21 + x31 = 130,
 x12 + x22 + x32 = 60,

 x13 + x23 + x33 = 95,
j = 1, 2, 3.
Таблица 4.6
Таблица 4.5
Потребности
Запасы
A1
40
Глава 3. Теория двойственности
•
20
Получили первый опорный план
 0 40 0 
 ,
X 1 = 
 30 0 20 
стоимость которого
Потребности
Запасы
A1
110
B1
B2
B3
130
60
95
13
15
3
A2
90
10
8
7
A3
85
8
10
12
Целевая функция F ( X ) , численно выражающая величину
суммарной стоимости перевозок, имеет вид
F ( X ) = 13x11 + 15 x12 + 3x13 + 10 x21 + 8 x22 +
+ 7 x23 + 8 x31 + 10 x32 + 12 x33 → min .
4.4. Построение циклов переброски грузов
плану надо перевезти из пункта Ai в пункт B j , т. е. введем матрицу
X = {xij } размера 3× 3 . Тогда следующая задача ЛП описывает ЗТЗ:
Для нахождения оптимального плана ЗТЗ используется несколько методов, например метод потенциалов или метод дифференциальных рент. Мы опишем только первый из указанных методов.
Общая идея метода потенциалов такая же, как и в симплексметоде решения задач ЛП. Сначала находим первый опорный план,
а затем, если надо, последовательно улучшаем его, т. е. переходим
к другому плану, стоимость которого меньше предыдущего. При
этом на каждом шаге одна занятая базисная клетка (базисная переменная) становится свободной, а свободная клетка – занятой.
Итак, пусть построен первый опорный план. В таблице при
этом имеется m + n − 1 занятых клеток, которые соответствуют ба-
68
69
F1 = 2 ⋅ 40 + 3 ⋅ 30 + 6 ⋅ 20 = 290 (у. е.).
При желании решить ТЗ симплекс-методом полезна следующая задача.
Задача 4.1. Составить математическую модель ЗТЗ, заданную
табл. 4.6.
Обозначим через xij количество единиц груза, которые по
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
зисным переменным. Как перейти к другому опорному плану?
Например, необходимо в табл. 4.3 сделать свободную клетку
( A2 , B3 ) занятой (базисной). Для этого надо организовать переброску груза в некотором количестве Z ед. по замкнутому контуру, который называется циклом. Цикл – это замкнутая ломаная, соединяющая несколько клеток таблицы, все звенья которой могут располагаться только перпендикулярно друг другу, вертикально или
горизонтально. Две последовательные вершины цикла лежат либо
в одной строке, либо в одном столбце. Число вершин цикла четно.
Циклом может быть и пересекающаяся ломаная, но точки самопересечения не являются вершинами цикла. В вершине (клетке таблицы) цикла, куда мы перекидываем Z ед. товара, ставим знак
плюс, а у соседней вершины (клетки), из которой мы берем Z ед.
товара, ставим знак минус. В точках самопересечения цикла знаки
«плюс» или «минус» не ставятся.
Примеры различных циклов:
_
+
_
+
+
–
_
+
– +
–
+
_
_
_
+
+
+
В таблице ТЗ цикл обычно отмечается пунктиром. Важно заметить, что составляется цикл, проходящий только через единственную свободную клетку. Все остальные вершины цикла должны проходить через занятые (базисные) клетки. При правильном
построении опорного плана для любой свободной клетки можно
построить лишь один цикл.
Сколько же единиц товара перебрасывается по данному циклу? Количество Z перебрасываемого товара равно наименьшей из
величин, стоящих в отрицательных вершинах цикла. Например,
в следующем цикле из табл. 4.3
60
•
+
–
–
+
160
40
Глава 3. Теория двойственности
надо перебросить груз в количестве
Z = min{60; 160} = 60 ед.
Тогда получим в тех же клетках
60
•
100
100
Если в клетках со знаком минус стоят два (или более) одинаковых числа, то освобождают только одну клетку, а остальные заполняют нулями.
Что произойдет со стоимостью F ( X ) при перераспределении
Z ед. товара по циклу? Величина изменения суммарной стоимости
ΔF перевозок равна
ΔF = Zγ,
где γ – цена цикла, которая вычисляется как сумма тарифов в клетках, входящих в цикл с соответствующими знаками. Например, цена цикла из табл. 4.3
γ = −3 + 4 − 7 + 5 = −1.
Ясно, что при γ > 0 будет ΔF > 0, а улучшение плана, т. е.
уменьшение значения функции F ( X ) произойдет лишь при γ < 0 .
При этом стоимость перевозок уменьшится на величину ΔF . Изложенный далее метод потенциалов позволяет автоматически находить свободные клетки с отрицательной ценой γ < 0 цикла.
4.5. Метод потенциалов
Методом потенциалов находим именно оптимальный план X*
перевозок в ЗТЗ.
Сопоставим каждому складу Ai число α i и каждому потребителю B j – число β j с условием, что равенство
α i + β j = cij
будет выполняться в каждой занятой клетке.
70
71
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Числа α i и β j называются потенциалами складов и потребителей. Поскольку в опорном плане m + n − 1 занятых (базисных)
клеток, то для нахождения потенциалов нужно решить систему из
m + n − 1 уравнений с m + n неизвестными. Поэтому можно значение одного потенциала выбрать произвольно, например α1 = 0 .
Остальные числа α i и β j определяются по цепочке друг за другом
однозначно.
Можно доказать, что разность, называемая оценкой свободной
клетки
γ ij = cij − (α i + β j ) ,
является ценой клетки ( Ai , B j ) в цикле переброски груза.
Ясно, что γ ij < 0 при cij < α i + β j . Если найдется хотя бы в одной свободной клетке γ ij < 0 , то план можно улучшить и он не является оптимальным. Если же во всех свободных клетках γ ij ≥ 0 ,
то построенный план оптимальный.
Алгоритм нахождения оптимального плана ЗТЗ методом
потенциалов
1. Строится первоначальный опорный план перевозок.
2. Для этого плана вычисляются потенциалы α i и β j складов
Ai и потребителей B j для занятых клеток. Обычно их значения заносятся в ту же таблицу ЗТЗ: числа α i выписываются справа в дополнительном столбце, а числа β j записываются в дополнительную
строку в таблице снизу.
3. Вычисляем числовые значения оценок свободных клеток
γ ij = cij − (α i + β j ) . Если для свободных клеток все γ ij ≥ 0 , то построенный план является оптимальным.
4. Если в некоторой свободной клетке ( Ai , B j ) получилось
Глава 3. Теория двойственности
5. Для нового плана повторить пункт 2 и пункт 3. За конечное
число шагов мы построим оптимальный план Х*.
Вернемся к примеру 4.1, в котором был построен первый план
X1 (табл. 4.7):
Таблица 4.7
Потребности
Запасы
A1
80
A2
A3
160
200
Потенциалы
потребителей
B1
B2
100
8
3
4
•
100
•
β1 = 2
B3
50
2
160
4
50
5
10
B4
4
•
3
•
β2 = 2
•
•
160
β3 = 4
130
Потенциалы
складов
6
30
α1 = 0
7
60
α2 = 1
5
40
α 3 = −1
β4 = 6
Вычисляем потенциалы занятых клеток по цепочке, решая
уравнения:
α1 = 0,

 α + β = c = 2  β = 2;
2
 1 2 12
 α1 + β4 = c14 = 6  β4 = 6;

α 2 + β4 = c24 = 7  α 2 = 1;
 α + β = c = 3  β = 2;
1
 2 1 21
 α3 + β4 = c34 = 5  α3 = −1;
 α + β = c = 3  β = 4.
 3 3 33
3
Вычисляем для свободных клеток оценки γ ij = cij − (α i + β j ) :
γ11 = 8 − (0 + 2) = 6 > 0; γ 23 = 4 − (1 + 4) = −1 < 0;
γ13 = 4 − (0 + 4) = 0;
γ 31 = 4 − (2 − 1) = 3 > 0;
γ 22 = 5 − (1 + 2) = 2 > 0;
γ 32 = 10 − (2 − 1) = 9 > 0.
γ ij < 0 , то надо создать цикл переброски груза через эту клетку, построить новый план перевозок X и новую таблицу ЗТЗ.
Поскольку γ 23 < 0 , то построенный план X1 неоптимален. Создаем цикл переброски груза прямоугольной формы с вершиной
в клетке ( A2 , B3 ).
72
73
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Глава 3. Теория двойственности
60
•
+
–
α1 = 0,

α + β = c = 2
 1 2 12
α1 + β4 = c14 = 6

 α3 + β4 = c34 = 5
α + β = c = 3
3
33
 3
c
α
+
β
=
 2
3
23 = 4
α + β = c = 3
 2 1 21
–
+
160
40
В этом цикле надо перебросить
Z = min{60; 160} = 60 ед.
груза из клеток со знаком «–» в клетки со знаком «+». Тогда получим в тех же клетках
60
•
100
100
Таблица 4.8
B1
B2
100
8
A2
160
3
A3
200
4
•
100
•
Потенциалы β = 3
1
потребителей
B3
50
2
50
5
10
B4
160
4
•
•
β2 = 2
•
130
6
4
60
7
3
100
5
β3 = 4
 α3 = −1;
 β3 = 4;
 α 2 = 0;
 β1 = 3.
Для свободных клеток вычисляем оценки γ ij = cij − (α i + β j ) :
γ11 = 8 − (0 + 3) = 5 > 0;
γ 22 = 5 − (0 + 2) = 3 > 0;
γ13 = 4 − (0 + 4) = 0;
γ 31 = 4 − (3 − 1) = 2 > 0;
γ 24 = 7 − (0 + 6) = 1 > 0; γ 32 = 10 − (2 − 1) = 9 > 0.
Составляем новую таблицу ЗТЗ с новым опорным планом перевозок (табл. 4.8):
Потребности
Запасы
A1
80
 β2 = 2;
 β4 = 6;
Потенциалы
складов
30
α1 = 0
•
α2 = 0
100
α 3 = −1
β4 = 6
Поскольку все γ ij ≥ 0 , то улучшить план невозможно, он оптимален. Оставшиеся точки в таблице соответствуют нулевым перевозкам. Можно вычислить только цену цикла:
Поэтому
γ = 4 − 7 + 5 − 3 = −1.
ΔF = Zγ = 60 ⋅ (−1) = −60 (у. е.).
Стоимость прежнего плана F ( X 1 ) = 1680 у. е. уменьшилась на
60 у. е. и
F ( X 2 ) = 1680 − 60 = 1620 (у. е.).
Другой способ вычисления стоимости перевозок – по формуле (4.3):
F ( X 2 ) = 8 ⋅ 0 + 2 ⋅ 50 + 4 ⋅ 0 + 6 ⋅ 30 + 3 ⋅ 100 + 5 ⋅ 0 +
и вычисляем по цепочке потенциалы складов и потребителей α i
и β j по занятым клеткам:
+ 4 ⋅ 60 + 7 ⋅ 0 + 4 ⋅ 0 + 10 ⋅ 0 + 3 ⋅ 100 + 5 ⋅ 100 = 1620.
Ответ: оптимальный план перевозок
30 
 0 50 0


X * = 100 0 60
0 ,
 0
0 100 100 

его стоимость Fmin = 1620 у. е.
74
75
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Пример 4.3. Рассмотрим ТЗ открытого типа. На двух строительных базах A1 и A2 имеется кирпич в количествах a1 = 250 т
и a2 = 350 т. Три строительные фирмы B1 , B2 , B3 прислали заявки
на кирпич в объемах b1 = 190 т, b2 = 150 т, b3 = 170 т.
Известна матрица тарифов перевозок 1 т кирпича в у. е.
 7 9 10 
C = {cij } = 
.
10 7 8 
Сумма запасов кирпича на базах a1 + a2 = 600 т. Сумма потребностей фирм b1 + b2 + b3 = 510 т.
Поскольку
m
n
i =1
j =1
 ai >  b j ,
вводим в табл. 4.9 фиктивного потребителя B4ф с потребностями,
равными
b4 = a1 + a2 − (b1 + b2 + b3 ) = 90 т,
и стоимостями перевозок, равными 0: c14 = c24 = 0 . Теперь ТЗ становится закрытого типа.
Таблица 4.9
Потребности
Запасы
A1
250
7
A2
350
10
Потенциалы
потребителей
B1
B2
B3
190
150
170
190
•
β1 = 7
9
7
10
•
8
150
β2 = 7
•
170
β3 = 8
B4 ф
90
Потенциалы
складов
0
60
α1 = 0
0
30
α2 = 0
β4 = 0
Глава 3. Теория двойственности
0 
190 0
.
X 1 = 
 0 150 170 
Далее вычисляем потенциалы α i и β j строительных баз Ai
и фирм-потребителей B j по занятым клеткам в табл. 4.9:
 α1 = 0;
 α + β = 7  β = 7;
1
 1 1
 α1 + β 4 = 0  β 4 = 0;

α 2 + β 4 = 0  α 2 = 0;
α 2 + β 2 = 7  β 2 = 7;

 α 2 + β3 = 8  β3 = 8.
Для свободных клеток вычисляем γ ij = cij − (α i + β j ) :
γ12 = 9 − (0 + 7) = 2 > 0; γ 21 = 10 − (0 + 7) = 3 > 0;
γ13 = 10 − (0 + 8) = 2 > 0.
Поскольку все γ ij > 0 , то построенный план X 1 оптимален.
Суммарная стоимость перевозок при плане X 1 :
Fmin = F ( X 1 ) = 7 ⋅ 190 + 7 ⋅ 150 + 8 ⋅ 170 = 3740 (у. е.).
Ответ: оптимальный план перевозок
0 
190 0

X * = 
 0 150 170 
имеет стоимость Fmin = 3740 у. е. При этом на базе A1 останется 60 т,
а на базе A2 останется 30 т кирпича.
Методом наименьших тарифов построим первый опорный
план перевозок. Так как тариф min cij = 7 стоит в двух клетках
( A1 , B1 ) и ( A2 , B2 ), можно выбрать любую из них для начала построения. При этом четвертый столбец таблицы информирует, что на
базе A1 останется 60 т, а на базе A2 – 30 т.
Пример 4.4. В трех карьерах A1 , A2 , A3 имеются запасы речного песка в количествах a1 = 13 тыс. т; a2 = 10 тыс. т; a3 = 5 тыс. т.
Три завода B1 , B2 , B3 по производству строительных смесей прислали заявки на b1 = 15 тыс. т; b2 = 8 тыс. т; b3 = 15 тыс. т. Тарифы
перевозок приводятся в матрице
76
77
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Потенциалы α i и β j по занятым клеткам:
 1 7 5


C =  4 4 8 .
 3 2 3


Решение.
3
 ai = 13 + 10 + 5 = 28,
i =1
3
 bi = 15 + 8 + 15 = 38 ,
j =1
поэтому ТЗ открытого типа. Вводим (табл. 4.10) фиктивного поставщика A4ф с нулевыми тарифами c41 = c42 = c43 = 0 и запасом:
3
3
j =1
i =1
A1
A2
A3
A4ф
13
1
10
4
5
3
10
0
Потенциалы
потребителей
Таблица 4.10
B1
B2
B3
15
8
15
Потенциалы
складов
•
α1 = 0
5
α2 = 3
•
α3 = 1
10
α 4 = −5
13
7
2
4
•
•
β1 = 1
2
5
•
3
8
5
3
0
0
•
β2 = 1
β3 = 5
Последовательность построения плана X 1 : x11 = 13 , x12 и x13
ставим точки, так как карьер A1 освобожден; x32 = 5 , в x31 и x33 ставим точки; x21 = 2 , чтобы до конца удовлетворить потребности B1 ;
x22 = 3 для выполнения запроса B2 и x23 = 5 – оставшееся количество
вывозим к B3 ; в четвертой строке x43 = 10 – оставшиеся тонны для
удовлетворения потребностей B3 . Получился первый опорный план.
13

2
X1 = 
0

0
78
0

3 5
.
5 0

0 10 
α1 = 0  β1 = c11 − α1 = 1 − 0 = 1;


α 2 = c21 − β1 = 4 − 1 = 3;


 β 2 = c22 − α 2 = 4 − 3 = 1;

 β3 = c23 − α 2 = 8 − 3 = 5;



α 3 = c32 − β 2 = 2 − 1 = 1;

 α 4 = c43 − β3 = 0 − 5 = −5.

Заметим, что количество занятых
= 4 + 3 − 1 = 6, как у нас и получилось.
a4 =  bi −  ai = 10 тыс. т.
Потребности
Запасы
Глава 3. Теория двойственности
клеток
m + n −1 =
F ( X 1 ) = 83 у. е.
По свободным клеткам вычисляем γ ij = cij − (α i + β j ) :
γ12 = 6 > 0; γ 33 = −3 < 0;
γ13 = 0;
γ 41 = 4 > 0;
γ 31 = 1 > 0;
γ 42 = 4 > 0.
Поскольку γ 33 = −3 < 0 , полученный план X 1 неоптимален.
Организуем цикл переброски груза с вершиной в клетке ( A3 , B3 ).
Он отмечен пунктиром:
3
5
+
–
–
+
5
•
По такому циклу перераспределяем 5 тыс. т и получим в этих
же клетках:
8
0
0
5
•
Строим новую табл. 4.11 с новым планом перевозок X 2 с учетом цикла:
79
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Таблица 4.11
Потребности
Запасы
A1
13
1
A2
10
4
A3
5
3
A4ф
10
0
Потенциалы
потребителей
B1
B2
B3
15
8
15
Потенциалы
складов
13
7
2
4
•
•
β1 = 1
2
0
•
α1 = 0
8
0
α2 = 3
3
5
α 3 = −2
0
10
α 4 = −5
5
•
8
•
•
β2 = 1
β3 = 5
Стоимость плана X 2 :
F ( X 2 ) = 13 + 8 + 32 + 15 = 68 (у. е.).
Стоимость уменьшилась на 15 у. е., и это минимальное ее значение, так как:
γ12 = 6 > 0; γ 32 = 3 > 0;
γ13 = 0;
γ 41 = 4 > 0;
γ 31 = 4 > 0; γ 42 = 4 > 0.
План X2 = X * оптимален, однако потребности завода B3 не удовлетворены на 10 тыс. т, так как в клетке ( A4ф , B3 ) стоит число «10».
Ответ: оптимальный план перевозок
13 0 0 


X * =  2 8 0
 0 0 5


имеет стоимость Fmin = 68 у. е. При этом потребности завода B3 не
удовлетворены на 10 тыс. т.
80
Глава 3. Теория двойственности
4.6. Другие транспортные задачи
В условиях ТЗ иногда возникают какие-либо осложнения или
бывают предварительные договоренности. Такие ТЗ называют «ТЗ
с привилегиями» или «ТЗ с осложнениями». Приведем некоторые
из них.
1. Пусть запрещена перевозка со склада Ai в магазин B j . Тогда в клетке ( Ai , B j ) таблицы ТЗ можно поставить какой-либо тариф М , на порядок превышающий max cij . Далее ТЗ решают как
обычно. Ясно, что в оптимальном плане такая перевозка участвовать не будет: xij = 0 .
2. Пусть со склада Ai в магазин B j обязательно надо доставить не менее α ij единиц груза. Тогда можно сразу запас ai и потребности b j уменьшить на α ij и далее решать ТЗ обычным порядком.
Заметим в заключение, что имеются еще и другие экономические задачи, реально не связанные с транспортными перевозками,
но которые можно свести к такой же модели и решать рассмотренными выше способами [4]. Например, задача о назначениях, в которой для выполнения какой-либо работы нужен только один ресурс
(человек, автомобиль и т. п.), а каждый ресурс может использоваться только на одной работе. Эта задача возникает при назначении людей на должности или на работы, автомашин на маршруты, водителей на автобусы, при распределении групп по аудиториям и т. п.
Еще модель ТЗ может использоваться при оптимизации системы снабжения, где, например, возможны транзитные перевозки
с использованием или без использования оптовых баз.
В ряде случаев при перевозке скоропортящихся продуктов
и боеприпасов к месту боевых действий ТЗ ставится иначе. В таких
ситуациях нужно минимизировать не стоимость перевозок, а время
перевозки грузов. Эту проблему можно изучить, например, в пособии Е. С. Вентцель [5].
81
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
ПРОВЕРЬ СЕБЯ
Задание 4.1. Запасы: 90; 30; 40.
Тарифы:
1 3 4

C = 5 3 1
2 1 4

Ответ:
 70 20 0 0 


X * =  0 0 20 10 ,
 0 10 0 30 


Потребности: 70; 30; 20; 40.
Задание 4.2. Запасы: 300; 280;
120. Тарифы:
2 1

C = 4 2
3 5

Ответ:
 60 240 0 


X * =  0 150 120 ,
 220 0
0 

220. Потребности: 280; 390;
5

2 .
2 
Fmin = 240 у. е.
3

1 .
3 
Fmin = 1440 у. е.
Глава 3. Теория двойственности
Задание 4.4. Запасы: 100; 150;
150. Тарифы:
5 7

C = 8 4
6 9

Ответ:
0 
100 0


X * =  0 150 0 ,
 20
0 150 

6

5 .
7 
Fmin = 2270 у. е.
Задание 4.5. Запасы: 60; 80; 100. Потребности: 40; 80; 50. Тарифы:
6 3 1


C =  3 2 4 .
5 4 7


Ответ:
 0 10 50 


X * =  10 70 0 , Fmin = 400 у. е.
 30 0 0 


Задание 4.3. Запасы: 80; 50; 20. Потребности: 60; 50; 70. Тарифы:
 5 6 4


C =  4 3 4 .
7 5 8


Ответ:
 10 0 70 


X * =  20 30 0 , Fmin = 600 у. е.
 0 20 0 


82
170. Потребности: 120; 150;
83
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. Запасы: 100; 70; 70; 20. Потребности: 120; 80; 60. Тарифы:
2

5
C =
4

6
4 2

5 6
.
6 3

8 1 
2. Запасы: 110; 90; 85. Потребности: 130; 60; 95. Тарифы:
13 15 9 


C = 10 8 7 .
 8 10 12 


3. Запасы: 250; 350. Потребности: 190; 150; 170. Тарифы:
 7 9 10 
C = 
.
10 7 8 
4. Запасы: 13; 10; 5. Потребности: 15; 8; 15. Тарифы:
 1 7 5


C =  4 4 8 .
 3 2 3


5. Запасы: 160; 140; 60. Потребности: 80; 80; 60. Тарифы:
Глава 3. Теория двойственности
6. Запасы: 300; 280; 220. Потребности: 280; 390; 120. Тарифы:
 2 1 3


C =  4 2 1 .
 3 5 3


7. Запасы: 40; 50. Потребности: 30; 40; 20. Тарифы:
 4 2 3
.
C = 
 3 5 6
8. Запасы: 80; 50; 20. Потребности: 60; 50; 70. Тарифы:
 5 6 4


C =  4 3 4 .
7 5 8


9. Запасы: 100; 150; 170. Потребности: 120; 150; 150. Тарифы:
5 7 6


C =  8 4 5 .
6 9 7


10. Запасы: 15; 31. Потребности: 28; 17; 28. Тарифы:
 7 3 4
.
C = 
 8 1 4
 5 4 3


C =  3 2 5 .
 1 6 3


84
85
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Рекомендуемая литература
1. Прокофьева С. И. Основы теории игр : учеб. пособие / С. И. Прокофьева, Э. Е. Пак, Е. К. Ершов; СПбГАСУ. – СПб., 2014.
2. Красс М. С. Математика для экономического бакалавриата : учебник / М. С. Красс, Б. П. Чупрынов. – М. : ИНФРА-М., 2012.
3. Ершов Е. К. Методы оптимизации : учеб. пособие / Е. К. Ершов,
И. И. Кораблева, Э. Е. Пак, С. И. Прокофьева; СПбГАСУ. – СПб., 2015.
4. Акулич И. Л. Математическое программирование в примерах и задачах / И. Л. Акулич. – М. : Высшая школа, 1986.
5. Вентцель Е. С. Исследование операций: задачи, принципы, методология / Е. С. Вентцель. – М. : Дрофа, 1988.
86
Глава 3. Теория двойственности
ОГЛАВЛЕНИЕ
Введение……………………………………………………………………….
Глава 1. Необходимые сведения из геометрии, линейной алгебры
и математического анализа, применяемые в решениях задач
оптимизации………………………………………………………………….
1.1. Уравнения прямых, системы линейных уравнений……………………
1.2. Линейные неравенства……………………………………………….
1.3. Области на плоскости………………………………………………...
1.4. Функции нескольких переменных……………………………….….
1.5. Некоторые факты из курса линейной алгебры……………………..
Глава 2. Графический и симплексный методы решения задач
линейной оптимизации……………………………………………………..
2.1. Математические модели экономических задач…………………….
2.2. Постановка задачи линейного программирования…………………
2.3. Графический метод решения общей задачи линейного
программирования………………………………………………………...
2.4. Решение канонической задачи линейного программирования
симплекс-методом……………………...………………………………….
2.5. Решение канонической задачи линейного программирования
симплекс-методом с помощью таблиц…………………………………..
Глава 3. Теория двойственности…………………………………………..
3.1. Матричная форма записи задач линейного программирования…..
3.2. Двойственность задач линейного программирования
в симметричной постановке………………………………………………
3.3. Двойственность задач линейного программирования
в несимметричной постановке……………………………………………
3.4. Теоремы двойственности…………………………………………….
Глава 4. Транспортная задача……………………………………………..
4.1. Математическая модель и постановка транспортной задачи……...
4.2. Основные понятия и факты ТЗ………………………………………
4.3. Метод наименьшего тарифа………………………………………….
4.4. Построение циклов переброски грузов……………………………...
4.5. Метод потенциалов…………………………………………………...
4.6. Другие транспортные задачи………………………………………...
Рекомендуемая литература…………………………………..………………
87
3
6
6
7
8
10
12
14
14
18
21
30
36
48
48
48
51
53
61
61
63
65
69
71
81
86
В. Ю. Васильчук, Л. В. Коновалова, С. И. Прокофьева. Методы оптимальных решений
Учебное издание
Васильчук Владимир Юрьевич,
Коновалова Лариса Викторовна,
Прокофьева Светлана Ивановна
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
Учебное пособие
Редактор О. Д. Камнева
Корректор К. И. Бойкова
Компьютерная верстка И. А. Яблоковой
Подписано к печати .2018. Формат 60×84 1/16. Бум. офсетная.
Усл. печ. л. 5,1. Тираж 100 экз. Заказ 139. «С» 89.
Санкт-Петербургский государственный архитектурно-строительный университет.
190005, Санкт-Петербург, 2-я Красноармейская ул., д. 4.
Отпечатано на ризографе. 198095, Санкт-Петербург, ул. Розенштейна, д. 32, лит. А.
88
Документ
Категория
Без категории
Просмотров
0
Размер файла
926 Кб
Теги
metod, optim18, vasilchuk
1/--страниц
Пожаловаться на содержимое документа