close

Вход

Забыли?

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

?

466.Математический анализ некоторых экономических вопросов

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
МАТЕМАТИЧЕСКИЙ АНАЛИЗ
НЕКОТОРЫХ ЭКОНОМИЧЕСКИХ ВОПРОСОВ
Учебно-методическое пособие для вузов
Составитель
М.Б. Зверева
Издательско-полиграфический центр
Воронежского государственного университета
2009
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Утверждено научно-методическим советом математического факультета
26 марта 2009 г., протокол № 7
Рецензент доктор физико-математических наук Г.А. Курина
Учебно-методическое пособие подготовлено на кафедре математического
анализа математического факультета Воронежского государственного
университета.
Рекомендуется для студентов, обучающихся по специальности «Математика экономического профиля», а также студентов, изучающих курс «Вариационное исчисление и методы оптимизации».
Для специальности 010101 – Математика
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Предварительные сведения
Пусть G – множество из пространства R n .
Множество G называют выпуклым, если вместе с каждой парой точек
x,
y
оно
содержит
отрезок
[x,
y]
их
соединяющий,
где
[ x, y ] = {αx + (1 - α ) y, α Î [0, 1]} .
Простейшими примерами выпуклых множеств на плоскости могут
служить круг, квадрат, треугольник.
Элемент z называют выпуклой комбинацией элементов x1 , x2 , ..., xm ,
если он может быть представлен в виде суммы z = α1 x1 + α 2 x2 + K α m xm ,
где все коэффициенты αi ³ 0 , и
m
åα
i =1
i
= 1.
Множество всех выпуклых комбинаций всевозможных конечных наборов элементов из G называется выпуклой оболочкой G и обозначается
через coG.
Очевидно, отрезок – выпуклая оболочка пары точек (концов), треугольник – выпуклая оболочка трех точек, не лежащих одновременно на
одной прямой. Справедлива следующая теорема (критерий выпуклости).
Множество G выпукло, тогда и только тогда, когда оно совпадает со
своей выпуклой оболочкой, т.е. G = coG .
Пусть G – замкнутое выпуклое множество. Точка x0 называется
крайней точкой для G, если она не является внутренней ни для одного из
отрезков из G. Другими словами, если для любого h Î R n
и любого
e > 0 точки x0 + ε h, x0 - ε h не могут принадлежать G одновременно. Множество крайних для G точек будем обозначать через exG.
Например, если множество G – треугольник, то exG – множество
вершин треугольника.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 1.1. Является ли выпуклым множество G в R 2 , определяемое неравенством x12 £ x2 + 1 ?
Пусть x = ( x1 , x2 ) и y = ( y1 , y2 ) – точки из множества G. Покажем, что
все точки с координатами (α x1 + (1 - α ) y1 ,αx2 + (1 - α) y2 ) , где α Î [0, 1] , т. е.
точки отрезка [x, y], также принадлежат G. Для этого нужно доказать, что
(α x1 + (1 - α) y1 ) 2 £ αx2 + (1 - α) y2 + 1 .
Воспользовавшись неравенствами
x12 £ x2 + 1 , y12 £ y2 + 1 и оценкой 2 x1 y1 £ x12 + y12 £ x2 + y2 + 2, имеем
(α x1 + (1 - α) y1 ) 2 = α 2 x12 + 2α (1 - α) x1 y1 + (1 - α) 2 y12 £
£ α 2 ( x2 + 1) + α(1 - α)( x2 + y2 + 2) + (1 - α) 2 ( y 2 + 1) = α x2 + (1 - α) y2 + 1.
Последнее равенство получается после раскрытия всех скобок и приведения подобных слагаемых. Таким образом, множество G является выпуклым.
Пример 1.2. Является ли выпуклым множество G в R 2 , определяемое неравенством x12 + x22 ³ 1 ?
Точки x = (–1, 0) и y = (1, 0), очевидно, принадлежат множеству G.
Точка (0, 0) может быть представлена в виде
1
1
(0,0) = ( -1,0) + (1 - )(1,0) ,
2
2
т. е. принадлежит отрезку [x, y]. Однако точка (0, 0) не принадлежит множеству G, поскольку 0 2 + 0 2 = 0 < 1 . Значит, множество G не является выпуклым.
Упражнения
1.1. Является ли выпуклым множество G в R 2 , определяемое неравенством:
a) x12 £ x2 - 1;
b) x12 £ x2 2 + 1;
c) x12 + 4 x22 ³ 1;
d) | x2 | £ x1 + 1;
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
e) 2 x1 £ x2 £ x1;
g) 2 x2 £ x1 £
1.2.
f) 0 £ x1 £ 2 x2 £ x1 + 1;
1
x2 ; h) | x1 | ³ x2 ; x22 £ x12 ; x1 £ x22 ;
2
Является ли выпуклым множество G в R 3 , определяемое нера-
венством:
a) x12 + x22 ³ x3 ;
b) | x1 | £ x2 £ x3 ;
1.3. Укажите крайние точки для
a) полушария;
b) круга;
c) множества плоскости R 2 , определяемого системой неравенств
ìa x +a x ³ b,
ï 11 1 12 2 1
ï
ïï a21 x1 + a22 x2 £ b2 ,
í
ï
ï a31 x1 + a32 x2 £ b3 ,
ï x ³ 0, x ³ 0,
ïî 1
2
где коэффициенты заданы в таблице:
№ варианта
1
2
3
4
5
6
7
8
9
10
a11
2
3
5
1
2
3
10
1
3
1
a12
3
2
1
1
1
1
3
1
2
2
b1
6
6
5
1
2
3
30
4
6
2
a21
9
1
–1
–1
1
–6
–2
–3
3
2
a22
–6
–1
1
3
–4
2
5
2
–2
–1
b2
54
1
1
3
4
12
10
6
6
2
a31
7
6
5
8
4
5
8
5
5
7
a32
10
5
10
5
6
4
6
7
6
4
b3
70
30
50
40
24
20
48
35
30
28
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Теорема об экстремуме линейного функционала
и ее приложения в экономике
Пусть L – линейный функционал, действующий из множества R n , т. е.
1) L : R n ® R1
2) для любых чисел a, b и любых элементов x, y из R n
L(a x + b y ) = a L ( x ) + b L ( y) .
Теорема 1. (О представлении линейного функционала.) Всякий лиn
нейный на R n функционал L можно представить в виде L( x) = å ci xi ,
i =1
где ci – вещественные числа, x Î R n .
Пусть G – компактное (ограниченное, замкнутое) множество в R n .
Ставится задача исследования функционала L на экстремум на множестве
G (обозначается extr L ).
G
Точка x0 Î G называется (обозначается x0 ® minL ) точкой минимума
G
функционала L на множестве G, если для всех x Î G справедливо неравенство L( x ) ³ L( x 0 ) .
Точка x0 Î G называется (обозначается x0 ® max L ) точкой максиG
мума функционала L на множестве G, если для всех x Î G справедливо неравенство L( x) £ L( x0 ) .
Точки минимума, максимума называются точками экстремума.
Теорема (Основная). (Об экстремуме линейного функционала.)
Пусть L – линейный функционал, и G – компактное (ограниченное, замкнутое) выпуклое множество в R n . Тогда
min L = min L,
G
exG
max L = max L,
G
exG
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Доказательство. Рассмотрим, для определенности, случай минимума. По теореме Вейерштрасса, линейный функционал достигает своего
минимума на компакте G. Пусть x0 Î G ® min L.
G
Согласно теореме Каратеодори, всякое выпуклое компактное множество в R n представляет собой выпуклую оболочку своих крайних точек,
k
т. е. G = co(exG ). Так как x 0Î G , то x0 = å αi xi , где αi ³ 0 ,
i =1
xi Î exG .
k
åα
i =1
i
= 1,
По определению минимума, для всех i (от 1 до k) верно
L( x 0 ) £ L( x i ) . Предположим, что для всех i неравенство строгое, т.е.
L( x 0 ) < L( x i ) . Тогда
k
k
i =1
i =1
L( x 0 ) = å α i L( xi ) > L( x0 )å αi = L( x 0 ) ,
т. е.
L( x 0 ) > L( x 0 ) ,
что невозможно.
Таким образом, экстремум достигается в крайней точке множества
G. Теорема доказана.
Рассмотрим применения этой теоремы в некоторых экономических
вопросах.
2.1. Линейный случай
В линейном случае множество G может быть описано системой линейных неравенств. Рассмотренные в этом пункте задачи относят к задачам линейного программирования.
Задача 2.1.1. Фирма выпускает 2 вида мороженого: сливочное и шоколадное. Для изготовления мороженого используется два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в таблице.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Расход исходных продуктов
Исходный
продукт
на 1 кг мороженого
сливочное
Запас, кг
шоколадное
Молоко
0,8
0,5
400
Наполнители
0,4
0,8
365
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того,
установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 руб., шоколадного – 14
руб. Какого количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?
Решение. Обозначим через x1 суточный объем (в кг.) выпуска сливочного мороженого; x2 суточный объем выпуска шоколадного мороженого. Величины x1 и x2 нам предстоит найти. Заметим, что по смыслу задачи x1 ³ 0 , x2 ³ 0 . Кроме того, учитывая данные по изучению рынка сбыта, должны выполняться условия x1 - x2 £ 100 , x2 £ 350.
От реализации
сливочного мороженого фирма получит прибыль
16 x1 руб., а от реализации шоколадного мороженого прибыль будет составлять 14 x2 руб. Тогда прибыль фирмы от реализации всей продукции
составит
F = 16 x1 + 14 x2 .
(2.1.1)
Естественно, прибыль предприятия будет тем больше, чем больше
x j , но беспредельно увеличивать объем выпуска нам не дадут ограниченные исходные продукты (ресурсы), из которых изготовляется мороженое.
Действительно, количество молока, которое потребуется для производства
запланированной продукции, составит 0,8 x1 + 0,5 x2 кг и не должно пре8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
взойти имеющийся запас 400 кг молока, т. е. 0,8 x1 + 0,5 x2 £ 400. Аналогично, количество наполнителей, которое потребуется для производства
запланированной продукции, составит 0, 4 x1 + 0,8 x2 кг и не должно превзойти имеющийся запас 365 кг наполнителей, т. е. 0,4 x1 + 0,8 x2 £ 365.
Таким образом, требуется максимизировать функцию F = 16 x1 + 14 x2 ,
при условиях
ì
ï 0,8 x1 + 0,5 x2 £ 400,
ï
ï
ï 0, 4 x1 + 0,8 x2 £ 365,
ï
í x1 - x2 £ 100,
ï
ï x £ 350,
ï 2
ï
ïï x1 ³ 0, x2 ³ 0.
î
(2.1.2)
Функция F называется целевой функцией, система (2.1.2) – системой ограничений. Целевая функция с системой ограничений составляют
математическую модель задачи.
Обозначим через G множество точек плоскости R 2 , удовлетворяющих линейной системе ограничений (2.1.2). Для поиска max F воспользуG
емся основной теоремой.
Согласно теореме 1, функция F представляет собой линейный функционал, действующий из пространства R 2 . Изобразим на плоскости x1 , x2
множество G.
x2
x1
Множество G представляет собой шестиугольник OABDEU. Очевидно, G – выпуклое, замкнутое ограниченное множество. Согласно ос9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
новной теореме, функция F достигает максимального значения в одной из
вершин шестиугольника (exG={O, A, B, D, E, U}). Заметим, что значение F
тем больше, чем больше обе координаты точек из exG. Так как обе координаты точек O, A, U заведомо меньше соответствующих координат точки
B, то F может достигать своего максимального значения лишь в точках B,
D, E. Координаты точки B определяются как пересечение прямых, заданных уравнениями
ì 0,4 x + 0,8 x = 365;
ï
1
2
í
ï
ïî x2 = 350.
Решив последнюю систему, получим, что точка B имеет координаты
B (212, 5; 350). Координаты точки D определяются как пересечение прямых, заданных уравнениями
ì 0,4 x + 0,8 x = 365,
ï
1
2
í
ï 0,8 x1 + 0,5 x2 = 400.
îï
Решив последнюю систему, получим, что точка D имеет координаты
D (312, 5; 300). Координаты точки E определяются как пересечение прямых, заданных уравнениями
ì x = x - 100,
ï 2
1
í
ï 0,8 x1 + 0,5 x2 = 400.
îï
Решив последнюю систему, получим, что точка E имеет координаты
E(
4500 3200
;
) . Вычислив значения F в точках B, D, E имеем:
13
13
F(B) = 8300 F(D) = 9200 F(E) =
116 800
» 8984,6 .
13
Таким образом, максимальное значение, равное 9200, функция F
принимает в точке D. Значит, фирма должна выпускать в сутки 312,5 кг
сливочного мороженого и 300 кг шоколадного мороженого. При этом доход от реализации продукции составит 9200 руб.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 2.1.2. В суточный рацион включают два продукта питания P1
и P2 , причем продукта P1 должно войти в рацион не более 200 ед. Стоимость 1 ед. продукта P1 составляет 2 руб., продукта P2 – 4 руб. Содержание
питательных веществ в 1 ед. продукта, минимальные нормы потребления
указаны в таблице. Определить рацион питания, стоимость которого будет
наименьшей.
Питательные
вещества
Минимальная норма
потребления
A
B
Содержание питательных веществ в 1
ед. продукта
P1
P2
120
0,2
0,2
160
0,4
0,2
Обозначим через x j число единиц продукта P j , которое будет входить в рацион. По смыслу задачи все величины x j должны быть неотрицательными, причем, по условию, x1 £ 200 . Заметим, что при потреблении
x1 единиц продукта P 1 будет затрачена сумма 2x1 , а при потреблении x2
единиц продукта P 2 будет затрачена сумма 4x2 . Тогда сумма, затраченная на приобретение всего рациона, составит
F = 2 x1 + 4 x2 .
(2.1.3)
Так как содержание в рационе питательного вещества A должно
быть не менее чем 120 ед , то получаем неравенство
0, 2 x1 + 0, 2 x2 ³ 120.
Аналогично, так как содержание в рационе питательного вещества B
должно быть не менее чем 160 ед , то получаем неравенство
0, 4 x1 + 0, 2 x2 ³ 160.
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таким образом, мы пришли к задаче: исследовать на минимум функцию F, задаваемую равенством (2.1.3), зависящую от переменных x1 , x2 ,
удовлетворяющих системе ограничений неравенств
ì
ï 0, 2 x1 + 0,2 x2 ³ 120,
ï
ïï 0, 4 x1 + 0,2 x2 ³ 160,
í
ï x1 £ 200,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
(2.1.4)
Обозначим через G множество точек плоскости R 2 , удовлетворяющих линейной системе ограничений (2.1.4). Для поиска min F воспользуG
емся основной теоремой.
Согласно теореме 1 функция F представляет собой линейный функционал, действующий из пространства R 2 . Изобразим на плоскости x1 , x2
множество G.
x2
x1
Отметим, что в отличие от предыдущей задачи, множество G не является ограниченным. Однако заметим, что значение F тем меньше, чем
меньше x1 и x2 . Рассмотрим множество G1 Ì G , ограниченное треугольником ABC, где A (0, 800), B (200, 400), C (200, 800). Очевидно,
min F = min F , поскольку для всякой точки T из G с координатами ( x1 , x2 ) ,
G
G1
расположенной вне G1 , найдется точка N из G1 с координатами ( x1 , x2* ) ,
где x2* < x2 , и следовательно, F(N) < F(T). Но множество G1 – ограниченное, выпуклое, замкнутое. Поэтому, по основной теореме, F принимает
минимальное значение в крайней точке G1 , т. е. либо в точке A, либо в В,
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
либо в C. Так как вторая координата точки C больше соответствующей
координаты точки B, то F не может достигать минимума в С. Вычислив
значения F в точках A и В, имеем
F(A) = 3200, F(B) = 2000.
Таким образом, минимальная стоимость рациона составит 2000 руб.
При этом в рацион должно войти 200 ед. продукта P 1 и 400 ед. продукта P 2 .
Упражнения
ì
ï 2 x1 + 3 x2 £ 6,
ïï
2.1.1. L = 3 x1 + x2 ® max при ограничениях í 2 x1 - 3 x2 £ 3,
ï
ï x ³ 0, x ³ 0.
2
ïî 1
ì x - x ³ 0,
ï 1 2
ïï
2. 1.2. L = 2 x1 - 10 x2 ® min при ограничениях í x1 - 5 x2 ³ -5,
ï
ï x ³ 0, x ³ 0.
2
ïî 1
ì x + 4 x ³ 8,
ï 1
2
ï
ïï x1 £ 4,
2.1.3. L = 2 x1 + 3 x2 ® max при ограничениях í
ï 2 x2 ³ 5,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
ì
ï x1 - x2 £ 3,
ï
ïï -3 x1 + x2 £ 6,
2.1.4. L = 3 x1 + 5 x2 ® max при ограничениях í
ï x2 ³ 4,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
ì 3 x + x ³ 9,
ï 1 2
ï
ïï x1 + 2 x2 ³ 8,
2.1.5. L = 4 x1 + 6 x2 ® min при ограничениях í
ï x1 + 6 x2 ³ 12,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ì
ï 3 x1 + 5 x2 £ 18,
ï
ïï 2 x1 - x2 ³ 0,
í
ï 5 x1 - 3 x2 £ 15,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
2.1.6. L = 4 x2 ® min при ограничениях
ì 5 x + 3 x £ 15,
ï 1
2
ï
ïï 5 x1 + 4 x2 ³ 20,
2.1.7. L = 2 x1 + 3 x2 ® max при ограничениях í
ï x2 ³ 5,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
ì 2 x + 4 x £ 16,
ï 1
2
ï
ïï -4 x1 + 2 x2 £ 8,
2.1.8. L = x1 + x2 ® max(min) при ограничениях í
ï x1 + 3 x2 ³ 9,
ï
ï x ³ 0, x ³ 0.
ïî 1
2
ìa x +a x £ b,
ï 11 1 12 2 1
ï
ï a21 x1 + a22 x2 £ b2 ,
ï
ï
2.1.9 L = c1 x1 + c2 x2 ® max(min) при ограничениях í a31 x1 + a32 x2 £ b3 ,
ï
ïa x +a x £ b ,
ï 41 1 42 2 4
ï
ïï x1 ³ 0, x2 ³ 0.
î
№ варианта
c1
c2
a11
a12
b1
a21
a22
b2
a31
a32
b3
a41
a42
b4
1
2
2
3
3
–1
4
1
5
–1
6
–2
7
1
8
–1
9
3
10
0
1
–1
1
3
–2
2
1
–1
0
2
7
5
–1
12
3
1
7
–1
–3
–1
8
2
1
5
1
–2
6
–2
2
1
56
30
2
60
12
2
42
–2
–6
2
–2
–3
–2
–3
–3
–2
–2
–2
2
6
3
–2
–3
2
1
3
1
3
1
7
6
–6
–6
6
3
6
4
12
14
42
–2
–1
1
–1
–1
–1
3
–2
3
1
1
1
–3
2
1
3
–2
3
–4
–2
0
0
0
0
0
0
0
0
0
0
1
0
0
–1
0
1
0
1
0
–1
0
1
1
0
1
0
–1
0
1
0
6
5
4
–2
5
4
–2
5
6
–2
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.1.10. Фирма выпускает изделия двух типов: A и B. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции задан в таблице. Запасы сырья 1-го вида составляют 21 ед., 2-го вида – 4 ед., 3-го вида – 6 ед. и 4-го вида – 10 ед. Выпуск
одного изделия типа A приносит доход 300 руб., одного изделия типа B –
200 руб. Составить план производства, обеспечивающий фирме наибольший доход.
Изделия
A
B
Сырье
1
2
3
2
1
0
3
0
1
4
2
1
2.1.11. Обработка деталей A и B может производиться на трех станках, причем каждая деталь должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали A – 100 руб., детали B –
160 руб. Исходные данные приведены в таблице.
Станки
1
2
3
Норма времени
на обработку одной детали, ч
A
B
0,2
0,1
0,2
0,5
0,1
0,2
Время работы
станка, ч
100
180
100
2.1.12. Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исходные продукты:
пигмент и олифу. Расходы исходных продуктов и максимальные суточные
запасы указаны в таблице. Изучение рынка сбыта показало, что суточный
спрос на краску для наружных (внутренних) работ никогда не превышает
b 3 т в сутки. Цена продажи 1 т краски для наружных работ – c1 ден. ед.,
для внутренних работ – c 21 ден. ед. Какое количество краски каждого вида
должна производить фирма, чтобы доход от реализации продукции был
максимальным?
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Расход и суточные запасы исходных продуктов
Расход исходных продуктов
на 1 т краски
краска Н
краска B
Исходный
продукт
Пигмент
a 11
a 12
Олифа
a 21
a 22
Суточный
запас, т
b1
b2
Значения коэффициентов условий задачи
№ варианта
c1
c2
a 11
a 12
b1
a 21
a 22
b2
k1
k2
b3
1
3
2
1
3
1
4
2
5
3
6
2
7
1
8
3
9
2
10
4
2
1
4
2
2
1
2
4
3
5
1
2
3
3
1
3
3
1
1
1
2
1
2
1
1
4
1
1
1
2
6
6
12
3
4
24
6
6
7
8
2
1
1
3
4
2
1
2
2
4
1
2
2
2
1
1
1
1
1
3
8
6
6
12
8
8
5
8
10
24
0
1
1
0
1
1
1
0
0
0
1
0
0
1
0
0
0
1
1
1
2
2,5
3,5
4
4
3
1
4,5
6
3
Если по условию задачи спрос на краску для наружных (внутренних)
работ не превышает b 3 т в сутки, то в математической модели задачи следует принять, что коэффициент системы ограничений при неизвестном
значении краски для наружных(внутренних) работ, обозначенный в таблице k1 (k 2 ) равен 1(0), а при неизвестном значении краски для внутренних
(наружных) работ k 2 (k1 ) равен 0 (1).
2.2. Целочисленный случай
Некоторые задачи линейного программирования требуют целочисленного решения. К ним относятся задачи по производству и распределению неделимой продукции (выпуск станков, телевизоров, автомобилей и
т. д.). Универсальный метод решения подобных задач – метод Гомори, ко16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
торый будет приведен ниже, но в простейших ситуациях также можно воспользоваться основной теоремой. Рассмотрим следующий пример.
Задача 2.2.1. Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для
чего принято решение об установке в одном из цехов дополнительного
оборудования, занимающего
19 2
м площади. На приобретение дополни3
тельного оборудования фирма выделила 10 у.е., при этом она может купить оборудование 2 видов. Приобретение одного комплекта оборудования
1-го вида стоит 1 у.е., 2-го вида – 3 у.е. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в
смену на 2 шт., а одного комплекта оборудования 2-го вида – на 4 шт.
Зная, что для установки одного комплекта оборудования 1-го вида требуется 2 м 2 площади, а для оборудования 2-го вида – 1 м 2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.
Решение. Составим математическую модель задачи. Предположим,
что фирма приобретет x1 комплектов дополнительного оборудования первого вида и x2 комплектов оборудования второго вида. По смыслу задачи
x1 и x2 должны быть неотрицательными и, более того, целыми. На приобретение оборудования фирма потратит x1 + 3 x2 условных единиц. Так как
на приобретение оборудования выделено 10 у.е., то должно выполняться
неравенство x1 + 3 x2 £ 10 . Поскольку площадь, занимаемая оборудованием,
должна не превосходить
19
19 2
м , то получаем неравенство 2 x1 + x2 £
. Вы3
3
пуск фирмой продукции составит F = 2 x1 + 4 x2 единиц. Таким образом,
математическая модель задачи будет иметь вид
F = 2 x1 + 4 x2 ® max
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
при ограничениях:
ì
ï 2 x + x £ 19 ,
ï 1 2
ï
3
ïï
í x1 + 3 x2 £ 10,
ï
ï
ï x1 ³ 0, x2 ³ 0,
ï
ïî
(2.2.1)
где x1 и x2 – целые.
Изобразим на плоскости x1 , x2 множество G, задаваемое системой
неравенств (2.2.1). Оно будет представлять собой четырехугольник OA'BC.
x2
x1
Построим целочисленную решетку, проведя прямые через точки
0, 1, 2, 3 и т. д., и отметим те точки, которые попали в OA’BC. Таких точек – 12 штук. Далее можно было бы посчитать значение F на каждой из
таких 12 точек и выбрать среди всех максимальное, но чтобы сократить
расчет, воспользуемся основной теоремой. Обозначим через ОAERK пятиугольник, вложенный в OA’BC, и содержащий в себе все 12 целочисленных точек. Заметим, что вершины ОAERK имеют целочисленные координаты, причем ОAERK – ограниченное, выпуклое, замкнутое множество, а
F – линейный функционал. По основной теореме, максимальное значение
F на множестве ОAERK достигается в одной из вершин пятиугольника,
т. е. в какой-то из пяти точек O, A, E, R, K. Таким образом, мы сократили
с 12 до 5 число точек, на которых следует посчитать значение F.
Из линейности F следует, что значение F тем больше, чем больше
обе координаты точек x1 , x2 , поэтому максимальное значение F может дос18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
тигаться в какой-то из 3 точек E (1, 3), R (2, 2), K (3, 0). Посчитав значение
F в этих точках, имеем
F (E)=14, F (R)=12, F (K)=6.
Таким образом, максимальное значение F равно 14 и достигается при
x1 = 1, x2 = 3 . Значит, фирме следует приобрести один комплект оборудования первого вида и три комплекта оборудования второго вида, что обеспечит ей при имеющихся ограничениях на производственные площади и
денежные средства максимальное увеличение выпуска продукции, равное
14 единицам в смену.
Упражнения
ì
ï 5 x1 + 2 x2 £ 6,
ïï
2.2.1. L = 16 x1 + 9 x2 ® max при ограничениях í x1 + 3 x2 £ 6,
ï
ï x ³ 0, x ³ 0.
2
ïî 1
x1 и x2 – целые.
ì 2 x + x ³ 9,
ï 1 2
ïï
2.2.2. L = 2 x1 + 3 x2 ® min при ограничениях í 3 x1 - 4 x2 ³ 3,
ï
ï x ³ 0, x ³ 0.
2
ïî 1
x1 и x2 – целые.
ì
ï 2 x1 + 3 x2 £ 6,
ïï
2.2.3. L = 3 x1 + x2 ® max при ограничениях í 2 x1 - 3 x2 £ 3,
ï
ï x ³ 0, x ³ 0.
2
ïî 1
x1 и x2 – целые.
ì
ï 4 x1 + 2 x2 £ 7,
ïï
2.2.4. L = 4 x1 + x2 ® max при ограничениях í 3 x1 + 10 x2 £ 15,
ï
ï x ³ 0, x ³ 0.
2
ïî 1
x1 и x2 – целые.
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ì x + x £ 4,
ï 1 2
ï
ïï x1 + 3 x2 £ 9,
2.2.5. L = x1 + x2 ® max при ограничениях í
ï -3 x1 + x2 £ 0,
ï
ï x ³ 0, x ³ 0,
ïî 1
2
где x1 и x2 – целые.
2.2.6. Для приобретения оборудования по сортировке зерна фермер
выделяет 34 у.е. Оборудование должно быть размещено на площади, не
превышающей 60 м 2 . Фермер может заказать оборудование двух видов:
менее мощные машины A стоимостью 3 у. е., требующие производственной
площади 3 м 2 (с учетом проходов) и обеспечивающие производительность
за смену 2 т зерна, и более мощные машины B стоимостью 4 у. е., занимающие площадь 5 м 2 и обеспечивающие за смену сортировку 3 т зерна.
Определить оптимальный вариант приобретения оборудования, обеспечивающий фермеру при данных ограничениях максимум общей производительности сортировки, если он может приобрести не более 8 машин типа В.
2.3. Нелинейный случай
Рассмотрим случай, когда целевая функция представляет собой линейный функционал, а система ограничений не может быть записана в виде системы линейных неравенств.
Пример 2.3.1. Найти экстремумы функции L = 2 x1 + x2 при ограничениях
ì 2
ïï x1 + x22 £ 16,
í
ï x1,2 ³ 0.
ïî
20
(2.3.1)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение. Обозначим через G множество точек, удовлетворяющих
системе неравенств (2.3.1).
Очевидно, G представляет собой часть круга с радиусом 4, которая
расположена в первой четверти, т. е. G – ограниченное, выпуклое, замкнутое множество.
x2
x1
Заметим, что множество крайних точек coG= {( x1 , x2 ) : x12 + x22 = 16,
где x1 ³ 0, x2 ³ 0, и (0,0)} . Функция L – линейный функционал, действующий из пространства R 2 . Согласно основной теореме, L достигает экстремума на coG. Из представления L следует, что минимальное на G значение
L равно нулю и достигается в точке (0, 0). Значит, максимальное значение
достигается в точке с координатами вида ( x1 , 16 - x12 ) , где первая координата неотрицательна и не превосходит 4. Рассмотрим функционал L на
точках с координатами ( x1 , 16 - x12 ) , где 0 £ x1 £ 4 , и вычислим максимальное значение. Имеем L = 2 x1 + 16 - x12 , где 0 £ x1 £ 4 . Производная
L' = 2-
x1 <
x1
16 - x12
обращается в нуль в точке x1 =
8 5
, L ' > 0 при
5
8 5
8 5
и L ' < 0 при x1 >
. Таким образом, максимальное значение
5
5
достигается при
x1 =
8 5
. Подставив это значение в выражение
5
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x2 = 16 - x12 получим, что x 2 =
4 5
. Таким образом, что минимум, рав5
ный нулю, достигается в точке (0, 0); максимум, равный 4 5 – в точке
(
8 5 4 5
,
).
5
5
Пример 2.3.2. Найти экстремумы функции L = x1 + 3 x2 при ограничениях
ì x x £ 8,
ï 1 2
ï
ï x1 £ 6,
ï
í
ï x2 £ 4,
ï
ï x ³ 0.
ï 1, 2
î
(2.3.2)
Решение. Обозначим через G множество точек, удовлетворяющих
системе неравенств (2.3.2).
x2
x1
В отличие от предыдущего случая, множество G не является выпуклым. Так как обе координаты x1, 2 неотрицательны, то минимальное значение, равное нулю, функционал L достигает в точке (0, 0). Обозначим через
G' пятиугольник OABCD. Очевидно, G Ì G ' . Рассмотрим сначала задачу
исследования функционала L на максимум на множестве G'. Так как L –
линейный функционал, действующий из пространства
R 2 , а G' –
ограниченное, выпуклое, замкнутое множество, то согласно основной теореме L достигает максимума в одной из точек O (0, 0), A (0, 4), B(2, 4),
C (6, 4/3), D (6, 0). Так как обе координаты точки A меньше соответствующих координат точки B, а обе координаты точки D меньше соответствую22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
щих координат точки C, то максимальное на G' значение функционал L
может достигать либо в точке B, либо в точке C. Так как L(B)=14, L(C)=10,
то максимальное значение достигается в точке B (2, 4). Но точка B принадлежит также множеству G, вложенному в G'. Поэтому максимальное значение функционала L на множестве G равно 14 и достигается при
x1 = 2, x2 = 4 .
Упражнения
Дана задача с линейной целевой функцией и нелинейной системой
ограничений. Найти экстремумы функции, при этом с 1-го по 5-й вариант
выполнения работ принять математическую модель задачи вида
L = c1 x1 + c2 x2
при ограничениях:
ì 2
ïï x1 + x2 2 £ b1 ,
í
ï x1,2 ³ 0,
ïî
с 6-го по 10-й вариант – вида
L = c1 x1 + c2 x2
при ограничениях:
ì
ï x1 x2 £ b1 ,
ï
ïx £b,
ï 1 2
í
ï x2 £ b3 ,
ï
ï x ³ 0.
ï 1,2
î
Значения коэффициентов целевых функций и систем ограничений
№ варианта
c1
c2
b1
b2
b3
1
2
2
1
3
–1
4
2
5
–3
6
2
7
3
8
–2
9
2
10
–1
3
2
–2
1
–1
3
2
–1
1
–2
16
36
25
4
9
3
2
5
4
2
–
–
–
–
–
4
6
5
7
8
–
–
–
–
–
5
7
4
5
6
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Симплексный метод
Задачей линейного программирования называется задача исследования на экстремум функции
n
F( x) = å c j x j ® max(min)
(3.1)
j =1
при условиях
n
åa x
ij
j =1
j
£ (³ , =)bi
x j ³ 0,
(3.2)
j = 1, K, n,
i = 1, K, m.
Функция F(x) называется целевой функцией, а условия (3.2) – системой ограничений. Решение, доставляющее максимум (минимум) целевой
функции, называется оптимальным решением.
Задачи линейного программирования могут быть записаны в трех
формах в зависимости от постановки.
1.
Стандартная форма записи:
n
n
F( x) = å c j x j ® max
F( x) = å c j x j ® min
j =1
j =1
n
n
å aij x j £ bi
åa x
j =1
j =1
x j ³ 0,
j = 1, K, n,
i = 1, K, m.
Каноническая форма записи:
F( x) = å c j x j ® max(min)
j =1
åa x
j =1
ij
j
= bi
x j ³ 0,
j = 1, K, n,
i = 1, K, m.
³ bi
j = 1, K, n,
i = 1, K, m.
n
n
j
x j ³ 0,
или
2.
ij
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Общая форма записи.
В ней для отдельных ограничений могут присутствовать как знаки
равенства, так и знаки неравенства.
Любая форма записи приводится к любой другой. Например, чтобы
перейти от стандартной задачи к канонической необходимо ввести новые
переменные, а затем в зависимости от знака неравенства либо прибавить
( £ ) либо вычесть ( ³ ) их из каждого неравенства.
Пример.
1. F = 2 x1 + 3 x2 ® max
ì x + 3 x £ 18,
ï 1
2
ï
ïï 2 x1 + x2 £ 16,
í
ï x2 £ 5,
ï
ï x £ 7.
ïî 1
2. F = 4 x1 + 6 x2 ® min
ì 3 x + x ³ 9,
ï 1 2
ïï
í x1 + 2 x2 ³ 8,
ï
ï x + 6 x ³ 12.
2
ïî 1
x j ³ 0 (j = 1, 2)
x j ³ 0 (j = 1, 2)
Введем
дополнительные
неотрицательные
переменные
x3 ³ 0, x4 ³ 0, x5 ³ 0, x6 ³ 0 . Получим новую систему ограничений
ì x + 3 x + x = 18,
ï 1
2
3
ì 3 x + x - x = 9,
ï
ï 1 2
3
ïï 2 x1 + x2 + x4 = 16,
ïï
í
í x1 + 2 x2 - x4 = 8,
ï x2 + x5 = 5,
ï
ï x + 6 x - x = 12.
ï
2
5
ïî 1
ï x + x = 7.
ïî 1 6
x j ³ 0 (j = 1, ..., 6)
x j ³ 0 (j = 1, ..., 6)
Симплексный метод является универсальным методом решения задач линейного программирования. Практические расчеты при решении реальных задач симплексным методом выполняются в настоящее время с
помощью компьютеров. Однако если расчеты осуществляются в ручную,
то удобно использовать симплексные таблицы.
Будем для определенности считать, что решается задача на максимум. (Задача на минимум сводится к задаче на максимум умножением целевой функции на (–1).)
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм симплексного метода
1. Математическая модель задачи должна быть канонической. Если
она неканоническая, то ее надо привести к каноническому виду.
n
F( x) = å c j x j ® max при ограничениях
j =1
ì
ï a11 x1 + a12 x2 + ... + a1n xn £ b1 ,
ï
ïï a21 x1 + a22 x2 + ... + a2 n xn £ b2 ,
í
ï ........................................
ï
ï a x + a x + ... + a x £ b .
ïî m1 1 m 2 2
mn n
m
(3.3)
x j ³ 0 (j = 1, ..., n).
Чтобы привести стандартный вид к каноническому введем m штук (по количеству неравенств в системе (3.3)) дополнительных неотрицательных
переменных xn +1 , xn + 2 , xn+ m . Получим следующую систему:
ì a x + a x + ... + a x + x = b ,
ï 11 1 12 2
1n n
1
n +1
ï
ïï a21 x1 + a22 x2 + ... + a2 n xn + xn + 2 = b2 ,
í
ï ....................................................
ï
ï a x + a x + ... + a x + x = b .
ïî m1 1 m 2 2
mn n
n+ m
m
(3.4)
Переменные системы (3.4), которые могут быть выражены через все
остальные, называются базисными.
В данном случае это xn +1 , xn + 2 ,
xn+ m . Переменные x1 , x2 , xn (через которые могут быть выражены базисные) называются свободными. Заметим, что можно считать то, что переменные xn +1 , xn + 2 , xn + m входят в целевую функцию F с нулевыми коэффициентами.
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Данные задачи заносим в первую симплексную таблицу:
Переменные
Базис
Свободные
члены (b)
x1
x2
…
xn
xn+1
…
xn+ m
xn+1
b1
a11
a12
…
a1n
1
…
0
xn+ 2
b2
a21
a22
…
a2n
0
…
0
…
…
…
…
…
…
…
…
…
xn+ m
bm
am1
am 2
…
amn
0
…
1
F( x )
Δ1
D2
…
Δn
Δ n+1
Последняя
строка
таблицы
называется
O.O.
… Δ n+m
оценочной
строкой.
F( x ) = F( x1 = x2 = ... xn = 0, xn+1 = b1 , xn+ 2 = b2 ,... xn+ m = bm ). Вектор x называется опорным решением исходной задачи. В рассматриваемой ситуации
F( x ) = 0. Заметим, что опорное решение должно быть неотрицательным,
т. е. все компоненты вектора x должны быть неотрицательными, и базисным, т. е. все свободные переменные должны быть равными нулю. Величины Δ j называются оценками и считаются как
m
Δ j = å ci aij - c j .
i =1
В данной ситуации Δ1 = -c1 , Δ2 = -c2 , ..., Δn = -cn , Δ n+1 = ... = Δ n+ m = 0 .
3. Проверяем опорное решение на оптимальность.
1. Если в оценочной строке все оценки Δ j ³ 0 , то достигнут максимум, равный F( x ). Базисные переменные принимают значения, записанные во втором столбце, остальные переменные равны нулю.
2. Если хотя бы одна оценка Δ j £ 0 , но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи
прекращаем, т. к. тогда Fmax = ¥ .
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Если хотя бы одна оценка отрицательная, а при соответствующей
переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению.
4. Переход к другому опорному решению.
Наибольшая по модулю отрицательная оценка Δ i < 0 определяет
разрешающий столбец
S. Составляем оценочные отношения (заполняя
столбик О.О.) по правилам: делим построчно столбец b на столбец S, полагая результат деления равным
¥ , если bi и ais имеют разные знаки;
¥ , если bi = 0 и ais <0;
¥ , если ais =0;
0, если ais >0 и bi = 0 ;
bi
если bi и ais имеют одинаковые знаки.
ais
Далее определяем минимум оценочных отношений (среди ненулевых).
Если конечного минимума нет, то задача не имеет конечного максимума. Если
минимум конечен, то выбираем строку q, на которой он достигается (любую,
если их несколько) и назовем ее разрешающей строкой. На пересечении разрешающей строки и столбца находится разрешающий элемент aqs .
Переход к следующей таблице осуществляется по правилам:
а) в крайнем левом столбце записываем новый базис: вместо переменной xq записываем переменную xs . Остальные переменные базиса остаются нетронутыми;
б) новую строку под номером q получаем из разрешающей делением
всех ее элементов на разрешающий элемент aqs ;
в) в столбцах, соответствующих базисным переменным, проставляем: 1 против «своей» базисной переменной, 0 против «другой» базисной
переменной; 0 в оценочной строке для всех базисных переменных;
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
г) все остальные элементы таблицы aij ' вычисляем по правилу прямоугольника:
aij ' = aij -
ais aqj
bi ' = bi -
aqs
aisbq
aqs
Оценки Δ j можно считать по приведенным выше формулам или
по правилу прямоугольника. Получаем новое опорное решение, которое
снова проверяем на оптимальность и т. д.
Задача 3.1. Найти максимум функции F = 5 x1 + 2 x2 + x3 при условиях
ì x + 3 x - x £ 6,
ï 1
2
3
ïï
í x2 + x3 £ 4,
ï
ï 3 x + x £ 7,
îï 1 2
где xi ³ 0 .
Решение. Перепишем систему ограничений в каноническом виде.
Для этого введем неотрицательные переменные x4 , x5 , x6 . Имеем
ì x + 3 x - x + x = 6,
ï 1
2
3
4
ïï
í x2 + x3 + x5 = 4,
ï
ï 3 x + x + x = 7.
6
îï 1 2
Заполним первую симплексную таблицу
Базис
x4
x5
x6
Свободные
члены (b)
Переменные
О.О.
x1
x2
x3
x4
x5
x6
6
1
3
–1
1
0
0
6
4
0
1
1
0
1
0
¥
7
® min
3
7
0
3
Разрешающий
элемент
–5
Разрешающий столбец
1
0
0
0
1
–2
–1
0
0
0
29
Разрешающая строка
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Так как в оценочной строке имеются отрицательные оценки, то
опорное решение не оптимально, поэтому осуществляем переход к новой
таблице.
Базис
Свободные
члены (b)
x4
11
3
Переменные
x2
x3
x5
x5
x6
0
8
3
–1
1
0
0
1
1
4
Разрешающая
строка
¥
-
1
3
x5
4
0
1
1
Разрешающий
элемент
x1
7
3
1
1
3
0
0
0
1
3
0
1
3
–1
Разрешающий
столбец
0
0
5
3
35
3
О.О.
x1
¥
Так как в оценочной строке имеются отрицательные оценки, то решение не оптимально, поэтому осуществляем переход к новой таблице.
Базис
Свободные
члены (b)
x4
x3
x1
x2
x3
x5
x5
x6
23
3
0
11
3
0
1
1
2
3
4
0
1
1
0
1
1
0
0
0
0
0
0
7
3
47
3
x1
Переменные
1
0
1
3
2
3
О.О.
1
3
8
3
Так как в оценочной строке все оценки неотрицательны, то при
7
47
.
x1 = , x2 = 0, x3 = 4 достигнуто максимальное значение, равное
3
3
Упражнения.
Решите
упражнения
методом.
30
2.1.1–2.1.12
симплексным
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4. Метод Гомори
Этот метод является универсальным методом решения задач линейного программирования, требующим целочисленные решения. В общем
виде математическая модель задачи целочисленного программирования
может быть представлена в виде
n
F( x) = å c j x j ® max(min)
j =1
при ограничениях
ì a x + a x + ... + a x + x = b ,
ï 11 1 12 2
1n n
1
n +1
ï
ïï a21 x1 + a22 x2 + ... + a2 n xn + xn+ 2 = b2 ,
í
ï ....................................................
ï
ï a x + a x + ... + a x + x = b ,
mn n
n+ m
m
îï m1 1 m 2 2
где xi неотрицательные и целые.
Оптимальное решение задачи, найденное симплексным методом,
часто не является целочисленным. Его можно округлить до ближайших
целых чисел. Однако такое округление может дать решение, не лучшее
среди целочисленных решений, или привести к решению, не удовлетворяющему системе ограничений. Поэтому для нахождения целочисленного
решения нужен особый алгоритм. Такой алгоритм предложил Гомори и
состоит он в следующем.
Симплексным методом находят оптимальное решение задачи. Если
решение целочисленное, то задача решена. Если же оно содержит хотя бы
одну дробную координату, например xi , то накладывают дополнительное
ограничение по целочисленности, которое имеет вид
å{a *}x
j
ij
j
³ {bi *},
(4.1)
где фигурной скобкой обозначена дробная часть числа, aij * и bi * –
преобразованные исходные величины aij и bi , значения которых взяты из
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
последней симплексной таблицы. Если в оптимальном решении исходной
задачи дробные значения принимают несколько переменных, то дополнительное неравенство (4.1) определяется наибольшей дробной частью. Затем вычисления продолжают до получения нового решения. Если и оно
является нецелочисленным, то вновь накладывают дополнительное ограничение по целочисленности. Вычисления продолжают до тех пор, пока не
будет получено целочисленное решение или показано, что задача такого
решения не имеет.
Задача 4.1. Решим задачу 2.2.1 методом Гомори. Итак, решим задачу
F = 2 x1 + 4 x2 ® max
ì
ï 2 x + x £ 19 ,
ï 1 2
ï
3
ïï
í x1 + 3 x2 £ 10,
ï
ï x ³ 0, x ³ 0,
2
ï 1
ï
ïî
где x1 и x2 – целые.
Решение. Найдем сначала симплексным методом оптимальное решение задачи без условия целочисленности. Система ограничений в канонической форме может быть записана в виде
ì
ï 2 x + x + x = 19 ,
ï 1 2
3
í
3
ï
ï x1 + 3 x2 + x4 = 10.
ïî
Приведем все полученные симплексные таблицы.
Базис
b
x1
x2
x3
x4
x3
19
3
2
1
1
0
0
1
0
0
x4
10
1
0
–2
3
разрешающий
элемент
–4
32
О.О.
19
3
10
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Базис
b
x3
3
x2
Базис
x3
x2
x1
5
3
разрешающий
элемент
x2
x3
0
1
1
0
0
0
x3
3
5
1
5
2
5
10
3
40
3
1
3
2
3
b
x1
x2
1
0
9
5
41
15
218
15
0
1
0
0
Получили, что максимальное значение, равное
x4
-
1
3
1
3
4
3
x4
1
5
2
5
6
5
О.О.
9
5
10
О.О.
218
, достигается при
15
9
41
x3 = , x2 = . Оптимальное решение содержит две дробные компоненты.
5
15
Найдем дробные части чисел
9 41
и
. Напомним, что дробной частью чис5 15
ла f (обозначается {f}) называется разность между f и целой частью f (обозначается [f]), т. е. {f} = f–[f]. Целой частью числа f называется наибольшее
целое число, не превосходящее f. Имеем
9 9
4
{ } = -1= ,
5 5
5
Так как
41 41
11
{ }= - 2 = .
15 15
15
4 12 11
= > , то вводим дополнительное ограничение, пользу5 15 15
ясь первой строкой последней симплексной таблицы:
3
1
9
{1}x1 + {0}x2 + { }x3 + {- }x4 ³ { } .
5
5
5
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3 3
1
1
4 9 9
4
Так как {1}={0}=0, { } = , {- } = - + 1 = , { } = - 1 = , то по5 5
5
5
5 5 5
5
следнее неравенство может быть переписано в виде
3
4
4
x3 + x4 ³
5
5
5
или
3
4
4
x3 + x4 - x5 = .
5
5
5
Введем это ограничение в таблицу. Имеем:
Базис
x3
x2
x5
b
9
5
41
15
4
5
x1
x2
1
0
0
1
0
0
x3
3
5
1
5
3
5
x4
1
5
2
5
4
5
Разрешающий
элемент
x5
О.О.
0
3
0
¥
–1
4
3
Базис
b
x1
x2
x3
x4
x5
x3
1
1
0
0
–1
1
x2
3
0
1
0
x3
4
3
0
0
1
14
0
0
0
2
3
4
3
2
3
1
3
5
3
2
3
О.О.
-
Получили целочисленное решение x3 =1, x2 =3. При этом значение
целевой функции равно 14.
Упражнения. Решите упражнения 2.2.1–2.2.6 методом Гомори.
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Список литературы
1. Акулич И.Л. Математическое программирование в примерах и
задачах / И.Л. Акулич. – М. : Высш. шк., 1993.
2. Грицюк С.Н. Математические методы и модели в экономике /
С.Н. Грицюк, Е.В. Мирзоева, В.В. Лысенко. – Ростов н/Д : Феникс, 2007.
3. Красс М.С. Основы математики и ее приложения в экономическом образовании / М.С. Красс, Б.П. Чупрынов. – М. : Дело, 2002.
4. Курина Г.А. Методические указания по теме «Симплексный метод» для студентов технических специальностей ВЛТИ // Г.А. Курина,
И.В. Сапронов. – Воронеж : ВЛТИ, 1989.
5. Покорный Ю.В. Оптимальные задачи : [учебное пособие] /
Ю.В. Покорный. – М. : Ин-т компьютер. исслед. ; Ижевск : Регуляр. и хаотич. динамика :, 2008 .
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
1. Предварительные сведения .................................................................3
2. Теорема об экстремуме линейного функционала
и ее приложения в экономике ...........................................................................6
2.1. Линейный случай.......................................................................7
2.2. Целочисленный случай ........................................................... 16
2.3. Нелинейный случай................................................................. 20
3. Симплексный метод ........................................................................... 24
4. Метод Гомори..................................................................................... 31
5. Список литературы ............................................................................ 35
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
МАТЕМАТИЧЕСКИЙ АНАЛИЗ
НЕКОТОРЫХ ЭКОНОМИЧЕСКИХ ВОПРОСОВ
Учебно-методическое пособие для вузов
Составитель
Зверева Маргарита Борисовна
Редактор Л.М. Носилова
Подписано в печать 23.06.09. Формат 60×84/16. Усл. печ. л. 2,2.
Тираж экз. Заказ 1130.
Издательско-полиграфический центр
Воронежского государственного университета.
394000, г. Воронеж, пл. им. Ленина, 10. Тел. 208-298, 598-026 (факс)
http://www.ppc.vsu.ru; e-mail: pp_center@ppc.vsu.ru
Отпечатано в типографии Издательско-полиграфического центра
Воронежского государственного университета.
394000, г. Воронеж, ул. Пушкинская, 3. Тел. 204-133
1/--страниц
Пожаловаться на содержимое документа