Деева Е.М. Методические указания по решению типовых задач по дисциплине Линейная алгебра и линейное программирование
Подождите немного. Документ загружается.
21
границ, верхней и нижней (глобальный максимум и глобальный минимум).
Приведенные утверждения относительно выпуклых множеств и функций,
условий существования экстремума позволяют делать выводы о свойствах тех
или иных задач оптимального программирования, что является основой
разработки и применения математических методов их решения. Например,
симплекс-метод решения задачи линейного программирования использует, в
частности, «свойство выпуклости» этой задачи: не существует локального
экстремума, отличного от глобального.
Часть 2. Основные методы решения типовых
экономико-математических задач
Тема 1. Основы линейного программирования
Пример 1. Задача о смесях. Стандартом предусмотрено, что октановое
число автомобильного бензина А-76 должно быть не ниже 76, а содержание
серы в нем — не более 0,3 %. Для изготовления такого бензина на заводе
используется смесь из четырех компонентов. Данные о ресурсах смешиваемых
компонен тов, их себестоимости и их октановом числе, а также о содержании
серы приведены в табл. 2.1.
Таблица 2.1
Компонент автомобильного бензина
Характеристика
№ 1№ 2 № 3 № 4
Октановое число
68 72 80 90
Содержание серы, %
0,35 0,35 0,3 0,2
Ресурсы, т
700 600 500 300
Себестоимость, ден.
ед./т
40 45 60 90
Требуется определить, ско лько тонн каждого компонен та следует
использовать для получения 1000 т автомоби льного бензина А-76, чтобы его
себесто имост ь была минимальной.
Решение. Для решения этой зад ач и сформулируем ее эконо м и к о-
математическую мо дел ь, т. е . сф о р м ули р уе м зада ч у мате мат иче ски
(Приложение, форм ула 1 ).
Введем необходи мые обозн ачения: пус т ь
x
j
(j = 1, 2, 3, 4) —
колич ество в смеси компо н ента с номером
j.
С уче т о м этих
22
обозначений имеем за да ч у (критерий опти мально сти — «минимум
себестоимо сти »):
min f
()
X
= 40x
1
+ 45x
2
+ 60x
3
+ 90x
4
,
при ограничениях:
x
1
+ x
2
+ x
3
+ x
4
= 1000,
68x1
+ 72x2 + 80x3 + 90x4 ≥ 76
·1000,
0,35x1 + 0,35x2 + 0,3x3 + 0,2x4 ≤ 0,3
·1000,
x
1
≤
700,
x
2
≤ 600,
x
з ≤ 500,
x
4
≤
300,
xj
≥ 0,
j = 1, 2, 3, 4.
Функциональное ограничение (2.1) отражает необходиость п олучения
заданно го количества смеси (1 000 т); (2.2) и (2.3) - ограничения по
октаново м у числу и содержанию серы в смеси; остальные - ограничения на
имеющиеся объемы соответствующих ресурсов (компонентов). Прямы е
ограничения очевидны и принципиально важны для выбора метода решения.
Полученная математическая задача - задача лине йного программирован ия .
Она может быть решена симплекс -методо м, который рассмотрен в данном
разделе ниже (Часть 2, Тема 2). В результате получа ется оптимальное
решение
X = (х*
1
,х*
2
,х*
3
,х*
4
) : x*
1
= 571 т,
x*2=0, x*3 = 143т, x*4=286т.
Подставляя найденное решение в целевую функцию, имеем
F
()
*
X
= 40 ·571 + 45 · 0 + 60 · 143 + 90 · 286 =57 160,0 (ден. ед.).
Таким образом, оптимальному решению
()
*
X
будет отвечать минимальная
себестоимость в 57160,0 ден. ед.
(2.2)
(2.3)
(2.1)
23
Тема 2. Симплексный метод решения задачи линейного
программирования
Пример 2. Для производства продукции типа П
1
и П
2
предприятие использует
два вида сырья: С
1
и С
2
. Данные об условиях привед ены в табл. 2.2.
Таблица 2.2
Расходы сырья на
единицу продукции,
кг/ед.
Сырье
П
1
П
2
Количество
сырья, кг
С
1
С
2
1
1
3
1
300
150
Прибыль, тыс.
руб./ед. прод.
23 -
Составить план производства по критерию «максимум прибыли».
Решение. Обозначим объем производства продукции П
1
через x
1
, продукции
П
2
через x
2
. С учетом этих обозначений математическая модель задачи имеет
вид
max f
()
X
= 2x
1
+ 3x
2
при ограничениях
x
1
+ 3x
2
≤ 300,
x
1
+ x
2
≤ 150,
x
1
≥ 0, x
2
≥0.
Приведем эту зад ачу к каноническому виду (Приложение 1, формула 1), введя
дополнительные переменные x
3
и x
4
:
max f
()
X
= 2x
1
+ 3x
2
+ 0x
3
+ 0x
4
А
1
А
2
А
3
А
4
В
,
150
300
1
0
0
1
1
3
1
1
4321
=
+
+
+
xxxx
или x
1
+ 3x
2
+ x
3
= 300,
x
1
+ x
2
+ x
4
= 150,
x
j
≥ 0, или j
=
4,1
.
24
Задач а обла дает исходн ым опорн ым планом (0, 0, 300, 150), и ее можно
решить симплек с-методом; решение ведется в симплекс-таблицах
(табл..2.3).
В исходной симплекс-таблице строка оценок
∆
j
= z
j
—
c
j
определяется по формуле 2 (Приложение):
∆
1
=
z
1
– c
1
= 0 · 1 + 0 · 1 – 2 =
—
2,
∆
2
=
z
2
– c
2
= 0 · 3 + 0 · 1 – 3 =
—
3.
Исходн ый оп орный план (0, 0, 300, 150) не является оптимальным, так как
среди оценок ∆
j
имеются отрицательные оценки.
Таблица 2.3
2300Номер
сим-
плекс-
табли-цы
Базис
c
j
c
i
План
В
А
1
А
2
А
3
А
4
Q
←
А
3
А
4
0
0
300
150
1
1
3
1
1
0
0
1
100
1500
j
c
j
z
j
−=∆
0
—
2
—
3
00
2
А→
4
А←
3
0
100
50
1/3 1
0
1/3
- 1/3
0
1
300
75I
j
∆
300 - 1 0 1 0
—
А
2
1
А→
3
2
75
75
0
1
1
0
0,5
- 0,5
- 0,5
-1,5
—
II
j
∆
—
375 0 0 0,5 1,5
—
Переход к но вому опорному плану осуществим, введя в базис вектор А
2
,
имеющий отрицательную минимальную оценку. Определя ем векто р,
выходящий из базиса (Приложение, форм ула 4):
,100
1
150
,
3
300
min =
=Q
т. е. вектор А
3
следует вывести из базиса. Главным направляющим элементом
является а
1,2
= 3 (выделен рамочкой). Переход к следующей симплекс-
таблице осуществляем с помощью преобразований Жордана-Гаусса.
2/3
25
Второй опорный пл а н (0, 1 00, 0, 50) не оптимальный; переход к
следующе м у опорному плану осуществим, ввод я в базис вектор А
1
и выводя
вектор А
4
. В р ез ульта те получаем оптимальн ый план (75, 75, 0, 0), т. е.
предприятие получит максим ум прибыли в размере 375,0 тыс. руб., если
вып усти т 75 единиц продукции первого вид а и 75 единиц прод укции второго
вида.
Тема 3. Симплекс-метод с искусственным базисом (М-метод)
Пример 3. Найти максим ум целевой функции
()
321
23max xxxf ++=Χ
при условиях
2x
1
+ x
2
= 8,
x
1
+ x
2
+ x
3
=6,
x
1
≥
0, x
2
≥ 0, x
3
≥ 0.
Решение. Матрица условий содержит только один единичный вектор,
добавим еще один искусственный вектор (искусственную неотрицательную
переменную у
1
в первое ограничение):
Р
1
=
0
1
.
Получим следующую М-задачу: найти максимум целевой функции
()
321
23max xxxf ++=Χ
—
Мy1
при условиях
2x
1
+ x
2
+ y
1
= 8,
x
1
+ x
2
+ x
3
=6,
x
1
≥
0, x
2
≥ 0, x
3
≥ 0, y
1
≥ 0.
М-задачу решаем симплекс-методом. Начальный опорный план (0, 0, 6, 8),
решение проводим в симплекс-таблицах (табл. 2.4).
26
Таблица 2.4
321
—
М
Номер
симп-
лекс-
таблицы
c
j
c
i
Ба-
зис
В
А
1
А
2
А
3
Р
1
Q
—
M
1
P←
8 2 0 1 4
1А
3
6 11106
0
—
j
∆
—
8М+6
—
2М
—
2
—
М
—
1 00
—
3
1
1
A→
А
3
4
2
1
0
0,5
0,5
0
1
—
I
—
j
∆
140 00
——
В начальной таблице наименьшее ∆
j
(Приложение, формула 2)
соответствует вектору А
1
—
он вво дится в базис, а искусственный вектор Р
1
из базиса выводится, так как ему отвечает наименьшее
Q
(Приложение,
формула 4). Сто лбец, соответствующий Р
1
,
из дальней ших симплексных
таблиц вычерк и вается. Полученный новый опорн ый план является опор ны м
планом исходной за да ч и . Для него все
∆
j
≥ 0, поэтому он и явл я ется
оптимальным. Таким об разом, получен оптимальны й план исходной задач и
(4, 0, 2) и ма кси ма льн ое значе н и е целевой функции
()
14
*
=Χf
.
Тема 4. Нелинейное динамическое программирование
Пр имер 4. Найти экстре мум функции
Z = x
1
x
2
+ x
2
x
3
при ограничениях
x
1
+ x
2
=2,
x
2
+ x
3
=2.
Ре шение.
Составляем ф ункци ю Лагранжа (Приложение, формула 7)
() ()()
,2
322
2
21132212
,
1
,
3
,
2
,
1
−++−+++= xxxxxxxxxxxF
λλλλ
дифференцируем ее по переменным x
1,
x
2,
x
3
,
λ
1,
λ
2
и полученные
выражения прирав ни ва е м к нулю:
1
27
=−+
=−+
=+
=+++
=+
.02
32
,02
21
,0
22
,0
2131
,0
21
xx
xx
x
xx
x
λ
λλ
λ
Из первого и третьего уравнений следует, что λ
1
= λ
2
=
—
x
2
, поэтому
x
1
—
2х
2
+ х
3
= 0,
x
1
+ х
2
= 2,
х
2
+ х
3
=2,
откуда 1
0
3
0
2
0
1
=== xxx и Z
0
= 2. Поскольку, например, точка (0; 2; 0)
принадлежит допустимой области и в ней Z = 0, то делаем вывод, что
точка (1; 1; 1) — точка глобального максимума.
Тема 5. Балансовые модели
Пример 5. Для трехотраслевой экономической системы заданы матрица
коэффициенто в прямых материальных затрат и векто р конечной
продукции:
.
003
001
002
;
2,01,03,0
0,05,02,0
4,01,03,0
=
= YA
Найти коэффициенты полных материальных затрат и вектор валовой
продукции, заполнить схему межотраслевого материальног о баланса.
Решение.
1. Определим матрицу коэффициентов полных материальных затрат по
второму (приближенному) способу (Приложение, формула 20), учитывая
косвенные материальные затраты до 2-го порядка включительно. Запишем
матрицу коэффициентов косвенных затрат 1-го порядка
,
16,010,017,0
08,027,016,0
20,012,023,0
2,01,03,0
0,05,02,0
4,01,03,0
2,01,03,0
0,05,02,0
4,01,03,0
2)1(
=
⋅
== AA
матрицу коэффициентов косвенных затрат 2-го порядка:
28
.
100,0083,0119,0
080,0159,0126,0
132,0103,0153,0
16,010,017,0
08,027,016,0
20,012,023,0
2,01,03,0
0,05,02,0
4,01,03,0
)1()2(
=
⋅
== AAA
Таким образом, матрица коэффициентов полных материальных затрат
приближенно равна
.
460,1283,0589,0
160,0929,1486,0
732,0323,0683,1
32
=+++≈ AAAEB
2. Определим матрицу коэффициентов полных материальных затрат с
помощью формул обращения невырожденных матриц (первый способ)
(Приложение, формула 19).
а) Находим матрицу (Е
—
А):
(Е
—
А) = .
8,01,03,0
0,05,02,0
4,01,07,0
2,01,03,0
0,05,02,0
4,01,03,0
100
010
001
−−
−−
−−
=
−
б) Вычисляем определитель матрицы:
.196,0
8,01,03,0
0,05,02,0
4,01,07,0
=
−−
−−
−−
=− АЕ
в) Транспонируем матрицу (Е
—
А):
()
.
8,00,04,0
1,05,01,0
3,02,07,0
−
−−
−−
=
′
− АЕ
г) Находим алгебраические дополнения для элементов матрицы
()
:
′
− АЕ
;40,0
8,00,0
1,05,0
2
)1(
11
=
−
−=А ;12,0
8,04,0
1,01,0
3
)1(
12
=
−
−−
−=А
;17,0
1,05,0
3,02,0
4
)1(
31
=
−
−−
−=А ;20,0
0,04,0
5,01,0
4
)1(
13
=
−
−
−=А
;10,0
1,01,0
3,07,0
5
)1(
32
=
−−
−
−=А ;33,0
5,01,0
2,07,0
6
)1(
33
=
−
−
−=А
;16,0
8,00,0
3,02,0
3
)1(
21
=
−−
−=А .44,0
8,04,0
3,07,0
4
)1(
22
=
−
−
−=А
29
.08,0
0,04,0
2,07,0
5
)1(
23
=
−
−
−=А
Таким образом, присоединенная к матрице (Е
—
А) матрица имеет вид
()
.
33,010,017,0
08,044,016,0
20,012,040,0
=− АЕ
д) Используя формулу 19 (Приложение) находим матрицу коэффициентов
полных материальных затрат:
()
.
684,1510,0867,0
408,0245,2816,0
020,161 2,0041,2
1
=
−
−= АЕВ
Как отмечено выше, элементы матрицы В, рассчитанные по точным
формулам обращения матриц, больше соответствующих элементов матрицы,
рассчитанной по второму приближенному способу без учета косвенных
материальных затрат порядка выше 2-го.
3. Найдем величины валовой продукции трех отраслей (вектор Х), используя
формулу 18 (Приложение):
.
6,729
1,510
3,775
300
100
200
684,1510,0867,0
408,0245,2816,0
020,161 2,0041,2
=
⋅
== ВYХ
4. Для определен ия элементов первого квадранта материальн ого
межотраслевого баланс а вос п о ль зуем ся форм улой, вытекающей из
формулы
15
( Приложение)
:
x
ij
= a
ij
X
j
.
Из этой формулы следует, что для
получения первого столбца первого квадра нта нужно элементы первого
столбца заданной матрицы
А умножить на величину
X
1
= 775,3; эл ем ен т ы
второго сто лб ца матрицы А умножить на Х
2
=
510,1; элем е н т ы тр етьего
стол бца матрицы А умножить на Х
3
= 729,6.
Составляющие третьего
квадра нта (ус ловн о чистая проду к ц ия) нахо дя тся с учет ом
формулы 14 (б) (Приложение) как разность ме ж ду объемами вал о в о й
продукци и и сум мам и эле мен тов соответст в у ю щих столбцо в найден ного
первого квадранта. Четвертый квадрант в наше м примере сост оит из
одного показателя и служ ит, в частнос ти, для ко н трол я правильности
расчета: сум ма элемен тов второго квад ра нта дол жн а в сто имостн о м
материальном балансе совпадать с сум мой элементов третьего кв адранта.
Результаты расчета представлены в табл. 2.5.
30
Таблица 2.5
Межотрас левой бал а нс производства и распределения продукции
Потребляющие отрасли
Производящие
отрасли
1 23
Конечная
продукция
Валовая
продукция
1
2
3
232,6
155,1
232,6
51,0
255,0
51,0
291,8
0,0
145,9
200,0
100,0
300,0
775,3
510,1
729,6
Условно чистая
продукция
155,0 153,1 291,9 600,0
—
Валовая
продукция
775,3 510,1 729,6
—
2015,0
Пример 6. Пусть в дополнение к исходны м данным пример а 5 заданы
затра ты живого труд а (тр уд о вые ресурс ы) в трех отрасля х:
L
1
= 1160, L
2
=
460, L
3
=
875 в некоторых един ицах измер ения труд о вых затрат. Треб уе т ся
определить коэффициенты пря мой и пол н о й тр удо е м кос ти и соста вить
межотраслевой ба ланс затр ат тр уд а.
1. Воспользовавшись формулой 14, в (Приложение) и результатами
при мера 1, находим коэффициенты прям ой трудоемкости:
;5,1
3,775
1160
1
==
t
;9,0
1,510
460
2
==
t
.2,1
6,729
875
3
==
t
2. По фор муле №1 4(г), в кото рой в ка ч е ст ве матрицы
В берется матр ица
коэффициента по лных матер иал ьн ых за т рат, найденна я в приме ре 1,
наход им коэффициенты по лной трудое мко с т и:
() ( )
.92,3;55,3;84,4
684,1510,0867,0
408,0245,2816,0
020,1612,0041,2
2,1;9,0;5,1 =
⋅=Т
3. Умножая первую, вторую и третью строки первого и второго квандрантов
межотраслевого материального баланса, построенного в примере 1, на
соответствующие коэффициенты прямой трудоемкости, получаем схему
межотраслевого баланса труда (в трудовых измерителях) (табл. 2.6).