Мат_модели
.pdfФедеральное государственное образовательное учреждение высшего
профессионального образования
ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ
Кафедра «Математика и финансовые приложения»
В.М. Гончаренко
Математические методы и модели исследования операций
Руководство к решению задач
Для студентов института
«Математические методы в экономике»
Москва 2006
Федеральное государственное образовательное учреждение высшего
профессионального образования
ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ
РОССИЙСКОЙ ФЕДЕРАЦИИ Кафедра «Математика и финансовые приложения»
УТВЕРЖДАЮ
Ректор Финансовой Академии
____________М.А. Эскиндаров «____» ______________2006 г.
В.М. Гончаренко
Математические методы и модели исследования операций
Руководство к решению задач
Рекомендовано Ученым советом по специальности «Математические методы в экономике» (протокол №3 от 22 ноября 2006 г.)
Одобрено кафедрой «Математика и финансовые приложения»
(протокол №4 от 8 ноября 2006 г.)
МОСКВА 2006 ГОД
УДК 51(073) ББК 22.1
Б87
Гончаренко В.М. Математические методы и модели исследования операций. Руководство к решению задач. Для студентов института «Математические методы в экономике». М.: Финансовая академия при Правительстве РФ, кафедра «Математика и финансовые приложения», 2006. — 27 с.
Рецензент: С.А. Зададаев, к.ф.-м.н, доцент.
Пособие является руководством к решению задач по курсу «Математические методы и модели исследования операций», читаемому студентам института «Математические методы в экономике» во втором семестре. Содержит большое количество разобранных примеров и задач для самостоятельного решения по основным темам, изучаемым в курсе: линейное программирование и теория двойственности, целочисленное программирование, выпуклое и динамическое программирование. Руководство может быть использовано при проведении практических занятий по курсу, а также для организации самостоятельной работы студентов и подготовки к курсовому экзамену.
Гончаренко Василий Михайлович
Компьютерный набор, верстка: Гончаренко В.М. Формат 60x90/16. Гарнитура Таймс.
Усл. 3,125 п.л. Изд. №______2006. Тираж 120 экз. Заказ № ______________
Отпечатано в Финансовой академии при Правительстве РФ
125468, Ленинградский пр-т, 49
Полное или частичное воспроизведение или размножение каким-либо способом настоящего издания допускается только с письменного разрешения Финансовой академии при Правительстве РФ.
© Финансовая академия при Правительстве РФ, 2006.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
§1. Каноническая и стандартная форма
задачи линейного программирования
Задачей линейного программирования называется задача оптимизации вида
f = c1x1 + c2 x2 +K+ cn xn + c0 → max (min)
a11x1 + a12 x2 +K+ a1n xn * b1, |
|
|
||||||||||||||||||
a |
21 |
x |
+ a |
22 |
x |
2 |
+K+ a |
x |
* b |
, |
|
|||||||||
|
|
1 |
|
|
|
|
|
|
|
2n n |
|
2 |
|
|
||||||
........................................ |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
x |
+ a |
m2 |
x |
+K |
+ a |
x |
n |
* b , |
|
||||||||
|
m1 |
1 |
|
|
|
|
2 |
|
|
|
|
mn |
|
m |
|
|||||
x |
|
≥ 0, x |
|
≥ |
|
0,K, x |
n |
≥ |
0. |
|
|
|
|
|||||||
1 |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
где «*» обозначает |
|
|
|
« ≥», |
|
|
« ≤» |
|
или |
|
«=». |
При этом условия типа |
||||||||
ai1x1 +ai2 x2 +K+ain xn *bi , |
|
|
i =1,K, m |
называются нетривиальными ограниче- |
||||||||||||||||
ниями; условия x j ≥ 0 , |
|
|
j =1,K, n |
– тривиальными ограничениями (они мо- |
||||||||||||||||
гут отсутствовать), а |
|
|
f = c1x1 +c2 x2 +K+cn xn +c0 |
– целевой функцией. Сис- |
тема ограничений задает в пространстве Rn выпуклое допустимое множество X , а любая точка x = (x1, x2 ,K, xn ) X называется допустимым решением задачи линейного программирования. Допустимое решение, на котором целевая функция достигает оптимального значения, называется оптимальным решением задачи линейного программирования.
Если система ограничений состоит только из уравнений и тривиальных неравенств, то говорят, что задача имеет каноническую форму, если же в системе ограничений имеются только неравенства, то говорят о стандартной форме задачи линейного программирования. В зависимости от метода решения, задачу необходимо привести к канонической или стандартной форме.
3
Пример 1. Привести к канонической форме задачу линейного программирования
z = 4x1 +2x2 −13x3 +2x4 − x5 → max
x1 −7x2 + x3 − x4 ≤ 9,5x1 +8x2 − x3 + x5 =10,
12x1 +8x2 +2x3 −3x4 + x5 ≥11,xi ≥ 0,i =1,K,5.
Решение. Согласно входящим в ограничения неравенствам, можно ввести балансовые переменные x6 ≥ 0, x7 ≥ 0 , такие, что эти условия при-
водятся к виду
x1 −7x2 + x3 − x4 + x6 = 9,
12x1 +8x2 +2x3 −3x4 + x5 − x7 =11,
и исходная задача переписывается в канонической форме
z = 4x1 +2x2 −13x3 +2x4 − x5 → max
x1 −7x2 + x3 − x4 + x6 = 9,5x1 +8x2 − x3 + x5 =10,
12x1 +8x2 +2x3 −3x4 + x5 − x7 =11,
xi ≥ 0,i =1,K,7.
Пример 2. Привести к стандартной форме задачу линейного программирования
z = 2x1 + x2 +3x3 + x4 → max
x1 +2x2 +5x3 − x4 = 4,x1 − x2 − x3 +2x4 =1,
xi ≥ 0,i =1,K,4.
Решение. Рассмотрим систему нетривиальных ограничений
x1 +2x2 +5x3 − x4 = 4,x1 − x2 − x3 +2x4 =1,
и выделим (методом Гаусса) базисные и свободные переменные:
1 |
2 5 −1 |
|
4 |
~ |
1 2 |
5 −1 |
|
4 |
~ |
1 |
0 1 |
1 |
|
2 |
|||||
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 2 |
|
|
|
|
1 |
−1 −1 2 |
|
1 |
|
|
|
0 |
−3 |
−6 3 |
|
−3 |
|
|
0 |
−1 |
|
1 |
|
|
|
|
|
|
|
Итак, получаем систему
4
x1 + x3 + x4 = 2,x2 +2x3 − x4 =1,
из которой выражаем базисные неизвестные
2 − x3 − x4 = x1 ≥ 0,1−2x3 + x4 = x2 ≥ 0,
и исключаем их из целевой функции
z = 2x1 + x2 +3x3 + x4 = 2(2 − x3 − x4 ) +(1−2x3 + x4 ) +3x3 + x4 = −x3 +5 .
Получим задачу в стандартной форме, равносильную исходной:
z = −x3 +5 → max
x3 + x4 ≤ 2,2x3 − x4 ≤1,x3 ≥ 0, x4 ≥ 0.
Задачи для самостоятельного решения
Найти каноническую форму следующих задач линейного программирования
|
z = −2x1 + 7x2 +3x3 − x5 → max |
z = −9x1 + 2x2 −5x3 − x4 → max |
|||||||||||||
|
x |
+ x |
− x |
− x |
≥15, |
|
|
17x |
+ x |
+ 4x |
= 31, |
|
|||
|
1 |
3 |
4 |
5 |
|
|
|
|
|
1 |
3 |
5 |
|
|
|
1. |
− x1 +3x2 − x3 + 4x5 ≤10, |
|
2. 12x1 +13x2 +14x3 −15x4 ≥18, |
||||||||||||
|
2x +5x − |
42x |
+ 6x |
≥ 34, |
|
x |
+ |
4x +11x |
−6x |
≤ 6, |
|||||
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
|
2 |
3 |
|
5 |
|
|
x |
≥ 0,i =1,K,5. |
|
|
x |
≥ |
0, x |
≤ 0, x |
4 |
≥ 0. |
|
||||
|
i |
|
|
|
|
|
|
|
1 |
|
3 |
|
|
|
|
|
|
|
|
|
|
z = 3x1 − x4 + x5 → min |
|
|
|
|
|
|
|||
|
|
|
|
|
|
−3x1 − x2 −5x3 + 4x6 ≤ 22, |
|
|
|
|
|||||
|
|
|
|
|
3. 2x1 +3x3 − 4x4 + 7x5 |
=18, |
|
|
|
|
|||||
|
|
|
|
|
|
|
−5x4 |
+ 2x5 −6x6 ≥ 27, |
|
|
|
|
|||
|
|
|
|
|
|
3x2 |
|
|
|
|
|||||
|
|
|
|
|
|
x ≥ 0, x |
≥ 0, x ≥ 0, x |
≤ 0. |
|
|
|
|
|||
|
|
|
|
|
|
1 |
2 |
4 |
6 |
|
|
|
|
|
|
Привести задачи линейного программирования к стандартному виду:
z= x1 −2x2 −2x3 −3x4 → max
4.x1 −2x2 −3x3 +3x4 = 0,x1 − x2 + 2x3 −3x4 = −3,
xi ≥ 0, i =1,K,4.
z =3x2 + x4 →max |
z =3x1 −x2 +x3 +x4 →max |
5. x1 − x2 +3x3 − x4 = −3, |
6. x1 +x2 −x3 −2x4 =2, |
4x1 −3x2 +3x3 +2x4 = −2, |
−5x1 −4x2 −3x3 −3x4 =2, |
x ≥0,i =1,K,4. |
x ≥0,i =1,K,4. |
i |
i |
5
§2. Графический метод решения задач линейного программирования
Если задача линейного программирования задана в стандартной форме в R2 , то для ее решения используют графический метод, который состоит в следующем.
1.Строится допустимое множество X , заданное системой ограничений, как пересечение полуплоскостей, определяемых каждым из входящих в эту систему неравенств. Если X – пустое множество, то задача решений не имеет.
2.Если X – непустое множество, то рассматриваются линии уровня целевой функции f = c1x1 + c2 x2 + c0 . Они определяются как прямые
вида c1x1 +c2 x2 = const с общим вектором нормали n = (c1,c2 ), определяю-
щим направление роста функции f . Смещая линии уровня в направле-
нии вектора n , находим первую точку x* = (x1*, x2* ) пересечения такой ли-
нии с множеством X . Тогда fmin = f (x* ) является минимальным значени-
ем функции f на X . Аналогично, если x* = (x1*, x2* ) – последняя точка пе-
ресечения линии уровня с множеством X , то fmax = f (x* ) – максимальное значение функции f на X . Если при перемещении линии уровня в на-
правлении n последняя имеет пересечения с X при сколь угодно большом значении константы, то fmax = +∞. Если же, наоборот, линии уровня имеют пересечения с X при сколь угодно большом по модулю отрицательном значении постоянной, то fmin = −∞.
Пример 3. Решить графически следующую задачу линейного программирования
6
z =3x1 + x2 −10 → max
7x1 + x2 ≥ 29,3x1 + 2x2 ≤ 25,
4x1 − x2 ≤15,xr ≥ 0.
Решение. Построим допустимую область X , т.е. множество на плоскости, определяемое системой
7x1 + x2 ≥ 29,3x1 +2x2 ≤ 25,
4x1 − x2 ≤15,xr ≥ 0.
Для этого построим сначала прямые l1 : 7x1 + x2 = 29 , l2 : 3x1 +2x2 = 25 и l3 : 4x1 − x2 =15 на плоскости (x1, x2 ), а затем найдем их точки пересечения.
Точку пересечения прямых l1, l2 находим как решение системы уравне-
ний
7x |
+ x |
= 29, |
|
|
|
1 |
2 |
|
|
3x1 + 2x2 = 25, |
|
Аналогично находим, что l2 ∩l3 = B(5;5) ,
x2
l2
l1
A
n
O
l1 ∩l2 = A(3;8)
l1 ∩l3 =С(4;1) .
l3
B
C
x1
7
Каждая из прямых разбивает плоскость на две полуплоскости, а каждое неравенство, входящее в систему ограничений, задает одну из полуплоскостей. Для того чтобы установить, какая из полуплоскостей определяется неравенством, необходимо взять произвольную («пробную») точку, не лежащую на прямой и проверить, удовлетворяет ли она соответствующему неравенству. Если неравенство выполнено, то неравенство определяет полуплоскость, содержащую «пробную» точку, а если неравенство не выполняется, то его решением является другая полуплоскость. Решением системы неравенств будет пересечение соответствующих плоскостей. В нашем случае это треугольник ABC . Построив вектор нормали n = (3;1) , убеждаемся, что решением задачи на максимум является точка B(5;5) и z(B) = 3 5 +5 −10 =10 .
Ответ. zmax = z(B) =10 .
Пример 4. Решить графически следующую задачу линейного программирования
z = 2x1 + x2 +3x3 + x4 → max
x1 +2x2 +5x3 − x4 = 4,x1 − x2 − x3 +2x4 =1,
xi ≥ 0,i =1,K,4.
Решение. Формально задача является, вообще говоря, задачей линейного программирования в пространстве R5 . Но ее можно свести к задаче на плоскости R2 , приведя к стандартной форме, как это было сделано в примере 2 § 1. Таким образом, имеем задачу
z = −x3 +5 → max
x3 + x4 ≤ 2,2x3 − x4 ≤1,x3 ≥ 0, x4 ≥ 0.
Строим на плоскости прямые l1 : x3 + x4 = 2, l2 : 2x3 − x4 =1 , находим их точку пересечения и в качестве допустимого множества получаем
8
x4
l1 |
l2 |
A
B
O
n |
C |
x3 |
четырехугольник OABC с угловыми точками O(0,0), A(0,2), |
B(1,1) и C( |
1 |
,0). |
2 |
|||
Вектор нормали имеет координаты n = (−1,0) и мы видим, |
что оптималь- |
ным множеством, на котором достигается максимальное значение функ-
ции |
z |
является |
|
отрезок |
|
OA , |
т.е. |
множество |
X * = (1 −t) A +tB = (1 −t)(0,0)+t(0,2)= (0,2t),t [0,1]. Отсюда находим |
|
|||||||
|
|
x = 2 − x − x |
4 |
= 2 − 2t, |
|
|
||
|
|
1 |
3 |
|
|
|
||
|
|
x2 =1 − 2x3 + x4 =1 + 2t. |
|
|
||||
|
Ответ. |
zmax = z(X * )= 5 при X * = (2 − 2t,1 + 2t,0,2t),t [0,1]. |
|
|||||
|
Пример 5. Решить задачу линейного программирования |
|
||||||
|
|
z = −x1 + x2 + 4 → min (max) |
|
|
||||
|
|
x |
− x |
+ x = 3, |
|
|
|
|
|
|
1 |
2 |
3 |
|
|
|
|
|
|
− 2x1 + x2 + x4 = 2, |
|
|
||||
|
|
|
≥ 0. |
|
|
|
|
|
|
|
x |
|
|
|
|
|
графическим методом.
Решение. Выразим базисные неизвестные x3 , x4 из ограничений
x3 = 3 − x1 + x2 ≥ 0,x4 = 2 + 2x1 − x2 ≥ 0,
и получаем задачу в стандартной форме
9