ББК 65.050я73
Д57
Рецензенты:
кандидат физико-математических наук, доцент Е. В. Манохин
(Тульский филиал Финансового университета при Правительстве РФ);
кандидат педагогических наук, заместитель директора по учебновоспитательной
работе О. Б. Микуляк
(Тульский филиал Российской академии народного хозяйства
и государственной службы)
Д57
Добрынина, И. В.
Оптимизация в управлении: Учеб.-метод. пособие / И. В. Добрынина.
– Тула: Изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2013. – 120 с.
ISBN 978-5-87954-818-1
Учебно-методическое пособие содержит изложение теоретического, практического
материалов, задания для самостоятельной работы и предназначено для
изучения дисциплины «Оптимизация в управлении» магистерской программы
«Математические методы в управлении и образовании» направления 050100.68
«Педагогическое образование».
Данное издание может быть рекомендовано бакалаврам направления
010500.62 «Математическое обеспечение и администрирование информационных
систем» для изучения дисциплины «Исследование операций», а также всем
студентам для освоения
курса «Оптимизация в управлении» элективного
модульного блока «Бизнес-математика».
ББК 65.050я73
Учебное издание
Добрынина Ирина Васильевна
ОПТИМИЗАЦИЯ В УПРАВЛЕНИИ
Учебно-методическое пособие
Печатается в авторской редакции.
Художественное оформление – Е. А. Свиридова.
Подписано в печать 09.07.2013 г. Формат 60×90/16. Бумага офсетная. Печать трафаретная.
Усл. печ. л. 8,75. Тираж 100 экз. Заказ 13/054. «С» 1504.
Издательство Тульского государственного педагогического университета
им. Л. Н. Толстого. 300026, Тула, просп. Ленина, 125.
Отпечатано в Издательском ц ентре ТГПУ им. Л. Н. Толстого.
300026, Тула, просп. Ленина, 125.
ISBN 978-5-87954-818-1
© И. В. Добрынина, 2013
© ТГПУ им. Л. Н. Толстого, 2013
2
Стр.2
ВВЕДЕНИЕ
Целью освоения дисциплины «Оптимизация в управлении» является
формирование у студентов количественного обоснования оптимальных
решений по организации управления.
Дисциплина «Оптимизация в управлении» включена в вариативную часть
профессионального цикла ООП и относится к дисциплинам по выбору.
Изучение данной дисциплины студентами базируется на освоении
дисциплины базовой и вариативной частей
математического и
естественнонаучного цикла бакалавриата «Основы математической обработки
информации», дисциплин вариативной части профессионального цикла
бакалавриата по линейной алгебре и аналитической геометрии,
математическому анализу, теории вероятностей.
К началу изучения дисциплины «Оптимизация в управлении» студенты
должны знать основы теории вероятностей, систем линейных уравнений,
уметь находить производные функций одной и нескольких переменных,
изображать геометрические фигуры по их аналитическому заданию, владеть
основными математическими методами работы с информацией, градиентным
методом решения оптимизационных задач.
Освоение данной дисциплины необходимо для качественного выполнения
диссертации,
магистерской
успешного
освоения
дисциплины
профессионального цикла «Математические методы в экономике и
управлении».
Оптимизация в управлении – наука, занимающаяся разработкой и
практическим применением методов наиболее эффективного управления
различными организационными системами.
Управление любой системой реализуется как процесс, подчиняющийся
определенным закономерностям. Знание этих законов помогает определить
условия, необходимые и достаточные для осуществления данного процесса
принятия решений, установить зависимость между параметрами процесса. Для
этого все параметры, характеризующие процесс и внешние условия, должны
быть количественно определены, измерены. Поэтому конечная цель
–
количественное обоснование принимаемых решений по организации
управления.
При решении конкретной задачи управления применение методов
дисциплины предполагает:
а) построение математических, экономических или статистических
моделей для задач принятия решения в сложных ситуациях или условиях
неопределенности;
б) изучение взаимосвязей, определяющих впоследствии принятие
решений, и установление критериев эффективности, позволяющих оценивать
преимущество того или иного варианта действия.
4
Стр.4
КОНСПЕКТЫ ЛЕКЦИЙ
1. ЛИНЕЙНОЕ И ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ
1.1. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
В наиболее общем виде задача (модель) линейного программирования записывается
следующим образом: требуется найти экстремум (максимум или минимум) линейной
целевой функции: f(x1, х2,…, хn) = a1х1+ a2 х2+…+ anхn
+
c x c x + + c1 x
+
11 1
21 1
12 2
22 2
c x c x + + c x {}, ,
x ≥0,
c x c x + + c x
m1 1 + m2 2
................................... .............
, ,
…
…
…
j
где ci,j , bi
2
n n
n n
{}
{}
, ,
j =1,2,…,n
(i=1,2,…,m; j=1,2,…,n) — заданные постоянные величины.
Задача линейного программирования (ЗЛП) задана в канонической форме, если в системе
ограничений заданы только равенства и в стандартной, если неравенства.
Геометрический метод решения задачи линейного программирования
Данный метод применяется, в основном, при решении ЗЛП с двумя переменными.
Теорема 1. Множество решений неравенства с двумя переменными a1x1+a2 x2≤b является
одной из двух полуплоскостей, на которые вся плоскость делится прямой a1x1+a2 x2=b, включая и эту
прямую, а другая полуплоскость с той же прямой есть множество решений неравенства a1x1+a2 x2≥b.
Обобщая данную теорему на случай n переменных, имеем: Множество всех решений
линейного неравенства с n переменными является одним из полупространств, на которые все
пространство делится плоскостью или гиперплоскостью, включая и эту плоскость
(гиперплоскость).
Теорема 2. Множество решений совместной системы т линейных неравенств с двумя
переменными
a 11x1+a1 2 x2≤b1
a 21x1+a2 2 x2≤b2
………….
a n1x1+an 2 x2≤bn
является выпуклым многоугольником (или выпуклой многоугольной областью).
Теорема 3. Множество всех допустимых решений совместной системы m линейных
уравнений с n переменными (m
Стр.5
Базисным решением системы m линейных уравнений с n переменными называется решение,
в котором все n-m неосновных переменных равны нулю. Базисное решение является
допустимым, если все его компоненты неотрицательны. Допустимое базисное решение
называется оптимальным, если целевая функция на нем принимает свое оптимальное
значение.
Теорема 5. Каждому допустимому базисному решению задачи линейного программирования
соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника
решений соответствует допустимое базисное решение.
Симплексный метод решения ЗЛП
Задача. Найти решение ЗЛП
max
при ограничениях
3x1 + 5x ≤ 60,
2
3x1 + 4x ≤ 34,
x ≤ 8,
2
2
x ≥ x ≥ 0 ,
1 0, 2
Решение. Приведем задачу к каноническому виду, введя дополнительные
неотрицательные переменные x3,, x4,, x5. Получим систему ограничений
12 3
12 4
25
++ =
++ =
xj≥0, j=1,2,…,5
+=
35 60,
34 34,
8,
xx x
xx x
xx
Решаем систему симплексным методом поэтапно.
Введем основные (базисные, связанные) и неосновные (свободные, принимающие
нулевые значения) переменные. Базисные переменные выразим через неосновные.
1 шаг. Основные переменные x3, x4, x5; неосновные переменные x1, x2.
2
x3 = −60 3x1 − x5 ,
x = −34 3x1 − x4 ,
8
4
x5 = − x2
z = 2x1 + x3 2
Первое базисное решение: X1 (0;0;60;34;8) – допустимое. Соответствующее значение
линейной функции z1=0.
Переводим в основные переменную x2, которая входит в выражение линейной функции с
наибольшим положительным коэффициентом. Находим максимально возможное значение
переменной x2, которое «позволяет» принять система ограничений, из условия минимума
соответствующих отношений:
x =
4 ,8
5 , 34
2 min 60
= 8
т.е. разрешающим (выделенным) является третье уравнение. При x2=8 в этом уравнении x5=0,
и в неосновные переходит переменная x5.
2 шаг. Основные переменные x2, x3, x4; неосновные переменные x1, x5
x = − x5
4
x3 = − x1 + x5 5
x = −2 3x1 + x4 5
z = +24 2x1 − x3 5
20 3
8
2
линейной функции z2=24. Переводим в основные переменную x1,
3
x =
3
3 , 2
1 min , 20
∞
=
а в неосновные x4.
6
Первое базисное решение: X2 (0;8;20;2;0) – допустимое. Соответствующее значение
2 ,
2
Данный метод рассмотрим на примере.
z = 2x1 + →3x2
Стр.6
3 шаг. Основные переменные x1, x2, x3; неосновные переменные x4, x5.
x1 = −
x2
x3
z =
= + +
= −
3
2
18
3
25 1
X3 (
max
−
3
2
3
1
8
x +
x5
4
x4
x −
4
3
4
3
1
x5
x5
x 5 .
3
2 ;8;18;0;0);
z = =z
3
3 25 1
z
3 25=
Базисное решение X3 оптимальное для задачи.
(
), так как в выражении линейной функции отсутствуют неосновные
переменные с положительными коэффициентами.
Двойственные задачи
Основными задачами теории линейного программирования являются стандартные и
канонические задачи на минимум и максимум.
Стандартная задача минимизации.
C. Найти решение системы
αi1y1+…+αinyn≥βi
(i= m,1 )
y1≥0, …, yn≥0,
которое минимизирует линейную форму γ1y1+…+γnyn.
Стандартная задача максимизации.
α1kzk+…+αmkzk≤γk, (k= n,1 ),
переменные задачи C* и наоборот.
Каноническая задача минимизации.
K. Найти решение системы
Задачи C и C* называются взаимно двойственными.
Заметим, что основным переменным задачи
αi1y1+…+αinyn=βi (i= m,1 )
y1≥0, …, yn≥0,
которое минимизирует линейную форму γ1y1+…+γnyn.
Задача, двойственная к задаче K:
K*. Найти решение системы
α1kzk+…+αmkzk≤γk,
(k= n,1 ),
(II)
которое максимизирует линейную форму β1z1+…+βmzm.
Теорема 1. Если обе взаимно двойственные задачи допустимы, то обе задачи имеют
решения и значения этих задач совпадают. Если хотя бы одна из задач недопустима, то ни
одна из задач не имеет решений.
Теорема 2. Компоненты оптимального решения двойственной задачи равны абсолютным
значениям коэффициентов при соответствующих значениях переменных линейной функции
исходной задачи, выраженной через неосновные переменные ее оптимального решения.
1. 2. МОДЕЛИ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
решение (план) X (x1
Задача линейного программирования формулируется следующим образом: найти такое
,x 2
,…,x n
), при которой линейная функция
(1)
(2)
z1≥0,…, zm≥0,
которое максимизирует линейную форму β1z1+…+βmzm.
Условия (1) и (2) называются линейными ограничениями задач C и C* соответственно.
С соответствуют дополнительные
(I)
7
Стр.7
z =∑c x j
j=1
n
j
(1)
принимает наибольшее (наименьшее) значение при ограничениях
∑
n
a x b i =
ij
j=1
x j ≥ 0, j = 1,2,...,n ;
x - целые числа
j
Методы целочисленной оптимизации можно разделить на три основные группы:
1) методы отсечения;
2) комбинаторные методы;
3) приближенные методы.
Методы отсечения
Один из алгоритмов решения задачи линейного целочисленного программирования (1)(4),
предложенный Гомори, основан на симплексном методе и использует достаточно
простой способ построения правильного отсечения.
Пусть задача линейного программирования (1)-(3) имеет конечный оптимум, и на
последнем шаге ее решения симплексным методом получены следующие уравнения,
выражающие основные переменные
x x1, 2
x
m+1,..., xm i+ , x n оптимального решения
1
i
2
2
i
x1 = − 1 1m m 1
x = −
im m 1
...
,..., xi ,..., x m
2 1m m 1
+ x + − − 1n nx ,
+ x + − −
...
..................................................
,
+1x + − −
...
mm m 1
...
in n
x
xm
=
m −
+1x + − −
2n nx ,
...................................................
xi = −
mn nx .
так, что оптимальным решением задачи (1)-(3) является X
например,
iim++ ...−− −
} m
11 { }in
xxn ≤ 0,
* (
1 , 2
,...,
i ,...
m ,0,...,0), в котором,
- нецелая компонента. В этом случае легко доказать, что неравенство
{ } {
(6)
сформированное по i-му уравнению системы (5), обладает всеми свойствами правильного
отсечения.
Для решения задачи целочисленного линейного программирования (1)-(4) методом
Гомори используется следующий алгоритм:
1) Симплексным методом решить задачу (1)-(3) без учета условия целочисленности. Если
все компоненты оптимального плана целые, то он является оптимальным и для задачи
целочисленного программирования (1)-(4). Если первая задача (1)-(3) неразрешима (т. е.
не имеет конечного оптимума или условия ее противоречия), то и вторая задача (1)-(4)
также неразрешима.
2) Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с
наибольшей целой частью и по соответствующему уравнению системы (5) сформировать
правильное отсечение (6).
3) Неравенство (6) введением дополнительной неотрицательной целочисленной
переменной преобразовать в равносильное уравнение и включить его в систему
ограничений (2).
4) Полученную расширенную задачу решить симплексным методом. Если найденный
оптимальный план будет целочисленным, то задача целочисленного программирования
(1)-(4) решена. В противном случае вернуться в пункт 2 алгоритма.
Если задача разрешима в целых числах, то после конечного числа шагов (операций)
оптимальный целочисленный план будет найден.
8
(5)
через неосновные переменные
j = i , 1,2,...,m;
(2)
(3)
(4)
β
β
α
α
β
β
β
β
β
β
α
α
α
αα
α
α
α
ββ
Стр.8
Если в процессе решения появится уравнение (выражающее основную переменную через
неосновные) с нецелевым свободным членом и целыми остальными коэффициентами, то
соответствующее уравнение не имеет решения в целых числах. В этом случае и данная
задача не имеет целочисленного оптимального решения.
Задача. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует
распилить на заготовки двух видов: длиной 1,2 м и длиной 0,9 м, причем заготовок каждого
вида должно быть получено не менее 50 шт. и 81 шт. соответственно. Каждое бревно можно
распилить на указанные заготовки несколькими способами:
1) на 1 заготовку по 1,2 м и 2 заготовки по 0,9 м;
2) на 2 заготовки по 1,2 м;
3) на 3 заготовки по 0,9 м.
Найти число бревен, распиливаемых каждым способом, с тем, чтобы заготовок любого
вида было получено из наименьшего числа бревен.
Решение. Обозначим через x1, x2, x3 число бревен, распиливаемых соответственно 1-м,
2-м и 3-м способами. Из них можно получить 2x1 + x2 заготовок по 1,2 м и 2x2+3x3 заготовок
по 0,9 м. Общее количество бревен обозначим z. Тогда математическая модель задачи
примет вид:
z x= + + →3x
1
при ограничениях:
2x1 + ≥ 50
2x + 3x3 ≥ 81
x2
2
x j ≥ 0, =j
1,2, 3
xj - целые числа.
Введя дополнительные переменные
равносильной системе уравнений:
x2
2
1,
2
2x1 + − = 50
2x + 3x3 − = 81
x x ,..., x ≥ 0
x4
x5
5
Решая полученную каноническую задачу (без условия целочисленности) симплексным
методом, на последнем, 3 шаге решения, найдем следующие выражения основных
переменных и линейной функции через неосновные переменные (рекомендуем получить их
самостоятельно):
3 шаг. Основные переменные x1, x2; неосновные переменные x3, x4, x5.
x1 =
z =
т. е.
z
2
4
4 3
x =
4
45 1
+
2
40 1
4
3
+
4
1
4
min 45 1=
x3 +
−
2
3
x3 +
2
1
2
1
x −
4
x3 +
4
2
1
x +
4
1
x5
4
1
x 5 ,
при оптимальном решении X3 (4
4
3 ;40
2
1 ;0;0;0).
Получили, что две компоненты оптимального решения
x
4
1 4 3=
и
x
2
2 40 1=
не
удовлетворяют условию целочисленности (4’’), причем большую целую часть имеет
компонента x2. В соответствии с п. 2 алгоритма решения задачи целочисленного
программирования по повторному уравнению, содержащему эту переменную x2, составляем
дополнительно ограничение (6):
2
40 1
−
2
3
x3
− −
2
1
x5 ≤ 0 .
Найдем дробные части
2
40 1 =
2
1
;
2
3 =
Запишем последнее неравенство в виде
9
2
1
;
−
2
1
= +−
2
1 1
=
2
1
.
x5
x
4 0≥
,
x
5 0≥
(2’’)
(3’’)
(4’’)
приведем систему неравенств к
(5’’)
x2
min
(1’’)
Стр.9
2
1
уравнение:
2
1
−
2
1
x3 −
2
1
x5 + = 0
x6
(7’’)
Выразим из (7’’) дополнительную переменную x6 и полученное уравнение введем в
систему ограничений, которую мы имели на последнем, 3 шаге, решения задачи (1’’)-(3’’)
(без условия целочисленности). Имеем:
4 шаг. Основные переменные x1, x2, x6 ; неосновные переменные x3, x4, x5.
z =
x1 =
2
4
4 3
x =
6
4
45 1
+
2
40 1
4
3
x = − +
2
1
+
4
1
x3 +
−
2
1
2
3
x3 +
2
1
x −
4
x3 +
x3 +
2
1
4
2
1
2
1
x +
4
1
x5
x5
4
1
x 5
решая эту расширенную задачу симплексным методом (предлагаем студентам выполнить
самостоятельно), получим на последнем, 5 шаге:
5 шаг. Основные переменные x1, x2, x3; неосновные переменные x4, x5; x6.
z =
т. е.
z
x1 =
x = +39 2x5 − x3 6
x3 = − + x2 6
2
5 1
2
1
2
45 1
+
2
1
2
min 45 1=
x5
x +
4
2
1
x ,
6
при оптимальном решении X5 (5
2
1 ;39;1;0;0;0).
Полученное оптимальное решение расширенной задачи (1’’)-(3’’), (6’’), вновь не
удовлетворяет условию целочисленности (4’’). По первому уравнению с переменной x1,
получившей нецелочисленное значение в оптимальном решении (5
2
1 ), составляем второе
дополнительное ограничение (6):
{}
2
5 1
− −
2
1
x − 1 x5
4
− −
которое приводим к виду
2
1
−
2
1
x −
4
2
1
x ≤ 0
6
(8’’)
С помощью дополнительной переменной x7≥0 приводим это неравенство к
равносильному уравнению, которое включаем в систему ограничений, полученную на
последнем, 5 шаге, решения расширенной задачи (1’’)-(3’’), (6’’) симплексным методом.
Имеем:
6 шаг. Основные переменные x1, x2, x3, x7; неосновные переменные x4, x5; x6.
z =
x1 =
x = +39 2x5 − 3x6
x3 = − + x2 6
2
5 1
2
1
2
45 1
+
2
1
x5
x7 = − +
2
1
4
2
1
x +
x +
4
2
1
x 6
2
1
x6
+
2
1
x − +x5
4
2
3
x6
2
3
x6 ≤ 0
+
2
1
x − +x5
4
2
3
x6
x5
−
2
1
x3 −
2
1
x5 ≤ 0
Введя дополнительную переменную x6 0≥
(6’’)
, получим равносильное неравенству (6’’)
10
Стр.10