Федосеев В.В. и др. Экономико-математические методы и прикладные модели
Подождите немного. Документ загружается.
Основы линейного программирования
61
Второй опорный план (0,100, 0,50) не оптимальный; пе-
реход к следующему опорному плану осуществим, вводя в
базис вектор А\ и выводя вектор А\. В результате получаем
оптимальный план (75,75,0,0), т.е. предприятие получит»
максимум прибыли в размере 375,0 тыс. руб., если выпус-
тит 75 единиц продукции первого вида и 75 единиц продук-
ции второго вида. А
Симплекс-метод с искусственным базисом (М-метод).
Применяется в тех случаях, когда затруднительно найти
первоначальный опорный план исходной задачи ЛП, запи-
санной в канонической форме.
М-метод заключается в применении правил симплекс-
метода к так называемой М-задаче. Она получается из ис-
ходной добавлением к левой части системы уравнений в
канонической форме исходной ЗЛП таких искусственных
единичных векторов с соответствующими неотрицательными
искусственными переменными, чтобы вновь полученная
матрица содержала систему единичных линейно-независи-
мых векторов. В линейную форму исходной задачи добав-
ляется в случае ее максимизации слагаемое, представляю-
щее собой произведение числа (-М) на сумму искусственных
переменных, где М — достаточно большое положительное
число.
В полученной задаче первоначальный опорный план
очевиден. При применении к этой задаче симплекс-метода
оценки Ду теперь будут зависеть от «буквы М». Для сравне-
ния оценок нужно помнить, что М— достаточно большое по-
ложительное число, поэтому из базиса будут выводиться в
первую очередь искусственные переменные.
В процессе решения М-задачи следует вычеркивать в
симплекс-таблице искусственные векторы по мере их вы-
хода из базиса. Если все искусственные векторы вышли из
базиса, то получаем исходную задачу. Если оптимальное
решение М-задачи содержит искусственные векторы или
М-задача неразрешима, то исходная задача также неразре-
шима.
Путем преобразований число вводимых переменных, со-
ставляющих искусственный базис, может быть уменьшено
до одной.
62 Глава 2
L. Пример 8. Найти максимум целевой функции: тах/(Х) =
= Зл:, + 2х
2
+
х
3
при условиях
2*i + х
2
= 8,
xi + х
2
+ х
3
= 6,
xi >0,х
2
> 0, x
s
> 0.
Решение. Матрица условий содержит только один
единичный вектор, добавим еще один искусственный вектор
(искусственную неотрицательную переменную у\ в первое
ограничение):
Получим следующую М-задачу: найти максимум целе-
вой функции maxf(X) = Зл^ + 2дг
2
+ х
3
- Му
г
при условиях
2xi + *2 + У\ = 8,
х
х
+ х
2
+ х
3
= 6,
х
х
>0,х
2
> 0, х
3
>0,
У1
> 0.
М-задачу решаем симплекс-методом. Начальный опор-
ный план (0,0,6,8), решение проводим в симплекс-таблицах
(табл. 2.3).
Таблица
2.3
Номер
сим-
плекс-таблицы
0
I
-м
1
-
3
1
-
Ба-
зис
<-Pi
Аз
д
;
A
s
*i
В
8
6
-&М+6
4
2
14
3
А,
1
2 |
1
-2М-2
1
0
0
2
А
г
1
1
-м-\
0,5
0,5
0
1
М
0
1
0
0
0
-м
р^
1
0
0
X
Q
4
6
-
Основы линейного программирования
63
В начальной таблице наименьшее Ау соответствует векто-
ру Ai — он вводится в базис, а искусственный вектор Pi из
базиса выводится, так как ему отвечает наименьшее Q.
Столбец, соответствующий Pi, из дальнейших симплексных
таблиц вычеркивается.
Полученный новый опорный план является опорным
планом исходной задачи. Для него все Aj > 0, поэтому он
является и оптимальным. Таким образом получен оптималь-
ный план исходной задачи (4,0,2), и максимальное значение
целевой функции f(X ) = 14. Л
L Пример 9. Решить ЗЛП: mmf(X) = 10xi - 5х
2
при усло-
виях:
2*1
_
%2
^ 3,
*! + х
2
> 2,
Xi + 2X2 ^ ~1>
х
1>2
>.
0.
Приведем ЗЛП к каноническому виду, перейдя к задаче
«на максимум»: max/jfX) = —Юлгх 4- Ьх
2
при условиях:
2х
х
- х
2
- х
3
= 3,
xi + х
2
- х± = 2,
-xi - 2х
2
+ х
ь
= 1,
х,
> 0, ; - 1^5 .
Для нахождения опорного плана переходим к М-задаче:
maxg(X,Y)
—
-10*! + 5х
2
- М(у
х
+ y
2
) при условиях:
2х
х
- х
2
- х
3
+ у\ = 3,
xi + х
2
- х
4
+ у
2
= 2,
-xi - 2х
2
+ х
ь
= 1,
*1,2,3,4,5 ^ 0, £/
1>2
> 0.
Дальнейшее решение проводим в симплекс-таблицах
(табл. 2.4).
64
Глава 2
Таблица
2.4
«3
ч
Ном
CUMI
таб
0
-
I
-
II
-
\
-М
-М
0
-
-10
-м
0
-
-10
5
0
-
Базис
Рг
А
ь
А)
±-Рг
А
ь
N
-*А
2
А
5
А;
в
3
2
1
~5М
3/2
1/2
5/2
-М/2-15
5/3
1/3
10/3
-15
-10
Ai
1
2 |
1
-1
-амчо
1
0
0
0
1
0
0
0
5
А
2
-1
1
-2
-5
/6
'
-1/2
1
3/2 1
-5/2
-ЗЛГ/2
0
.1
0
0
0
As
-1
0
0
м
-1/2
1/2
-1/2
-ЛГ/2+5
-1/3
1/3
0
5
0
А
4
0
-1
0
м
0
-1
0
м
-1/3
-2/3
-5/3
0
0
Аь
0,
0
1
0
0
0
1
0
0
0
1
0
-м
Pi
1
0
0
0
X
X
-м
р
2
0
1
0
0
0
1
0
0
X
Q
3/2
2
-
1/3
В симплекс-таблице II получен опорный план исходной
ЗЛП; поскольку все оценки Aj > 0, / = 1,5, то этот план явля-
ется и оптимальным, т.е. х\ = 5/3, х\ = 1/3 (исходные перемен-
ные),
х\ = 10/3, х\
=
0, х\ = 0 (дополнительные переменные),
при этом min f(X) = - max Д(Х) = -(-15) = 15 . Л
Вопросы
и
задания
1.
В
чем суть принципа оптимальности
в
планировании
и
управлении?
2.
Сформулируйте общую постановку задачи линейного программиро-
вания.
Каковы особенности канонической формы записи этой задачи?
3. Дайте общую характеристику метода Жордана-Гаусса исследова-
ния систем линейных уравнений.
4.
В чем
заключается геометрическая интерпретация задачи линейно-
го программирования?
5. Каковы основные этапы графического метода решения задач линей-
ного программирования?
Основы линейного программирования
65
6. В чем суть симплекс-метода? На каких свойствах задач линейного
программирования он основан?
7. Сформулируйте последовательность этапов практической реализа-
ции алгоритмов симплекс-метода при решении задач линейного
программирования.
8. Когда возникает необходимость использования симплекс-метода с
искусственным базисом (М-метода)? В чем суть этой модификации
симплекс-метода?
Упражнения
1.
Исследовать методом Жордана-Гаусса систему линейных
уравнений; в случае совместности системы найти общее ре-
шение, некоторое частное небазисное решение, все базисные
решения, указав при этом опорные решения:
а) 4*! - х
2
+ 2#з - Зх
4
=2 б) xi + х
2
- х
3
+
2^4
=
2
2*1 + 3^2 ~ *з + *4
=
5 -*1 + х
2
- Зх
3
- х
4
= 1
*1 ~ 4^2 + Зх
3
~ 4х
4
= -3; 3*! - х
2
+ 5х
3
+ 4х
4
= 3;
в) х\ + 2х
2
+ *з + *4 ~ Зл;
5
= 4
3*1 + 4х
2
~ 2х
3
~ *4 +
х
ь = 6
-Х\ + 4х
3
+ Зх
4
- 7х
5
= 2
2*1 + 6*2 - х
3
+ х
5
= 6.
2.
Решить графическим методом следующие задачи ли-
нейного программирования:
a) max f(X) = x-^+3x
2
б) min f(X) = ~6xi + 9x
2
-xi + x
2
< 3
Xl
+ Sx
2
> 9
xi + x
2
<7 _
2xi
+
X2
< 5
3*!
+ x
2
< 15 2*! - 3x
2
< 0
*b *2 * 0; _
Xi> Ж2
>
0;
в) minf(X)= 2x\-x
2
2x
x
+ 3x
2
> 12
*! - X
2
< 1
0 < xi 5 5
*
2
>0.
3.
Решить симплексным методом следующие задачи ли-
нейного программирования:
66
Глава 2
б) minf(X)= -2JCI - Зх
2
3*!
+ Зх
2
^ 15
xi + Зх
2
<
9
*1 < 4
*
ь
х
2
>
0;
a) max f(X) =
—JCJ
+ лг
2
2х
г
+ лг
2
< 15
xi + x
2
<
3
*2^
6
x
b
x
2
> 0;
в) min/(X)=2x
1
- 3*
2
2л;
i - х
2
- хз ^ 3
*! - ж
2
+ х
3
> 2
х
ъ
х
2
,х
3
>
0.
4.
Для выпуска четырех видов продукции требуются за-
траты сырья, рабочего времени и оборудования. Исходные
данные приведены в таблице:
Тип
ресурса
Сырье
Рабочее время
Оборудование
Прибыль на еди-
ницу продукции
Нормы затрат ресурсов
на единицу продукции
1
3
22
10
30
2
5
14
14
25
3
2
18
8
8
4
4
30
16
16
Наличие
ресурсов
60
400
128
Сформулировать экономико-математическую модель задачи
на максимум прибыли и найти оптимальный план выпуска
продукции.
Глава 3
ОПТИМАЛЬНЫЕ ЭКОНОМИКО-
МАТЕМАТИЧЕСКИЕ МОДЕЛИ
• Теория двойственности в анализе оптимальных решений экономи-
ческих задач
•
Транспортная задача
• Целочисленное программирование
• Задачи многокритериальной оптимизации
• Нелинейное и динамическое программирование; понятие об
ими-
тационном моделировании
• Модели сетевого планирования и управления
3.1.
Теория двойственности в анализе оптимальных
решений экономических задач
Рассмотрим основные понятия и выводы специального
раздела линейного программирования — теорию двойствен-
ности. В гл. 2 показано, что любую задачу линейного про-
граммирования можно записать следующим образом:
п
f(X)
=
Y,Cj
•
*j -> max, (3.1)
n
^a
tJ
-Xj <bj-,i
=
\,m, (3.2)
Xj >0;j = l,n. (3.3)
В этой главе для большей наглядности используются
записи типа f(X) -» max(min), эквивалентные записям
max(min)/
!
(X).
С каждой задачей линейного программирования тесно
связана другая линейная задача, называемая двойственной;
первоначальная задача называется исходной или прямой.
68
Глава 3
Связь исходной и двойственной задач заключается, в част-
ности, в том, что решение одной из них может быть получено
непосредственно из решения другой.
Хорошо разработанный математический аппарат линей-
ного программирования позволяет не только получать с по-
мощью эффективных вычислительных процедур оптимальный
план, но и делать ряд экономически содержательных выводов,
основанных на свойствах задачи, двойственной к исходной
ЗЛП. Переменные двойственной задачи у; называют объек-
тивно обусловленными оценками., или двойственными оцен-
ками. Модель двойственной задачи имеет вид:
g(Y) = ]Г b
t
•
y
t
-> min,
г=1
т
2°U
-У1
ZCj;j = l,n,
i=\
y
t
> 0; i ^ 1, т.
(3.4)
(3.5)
(3.6)
Каждая из задач двойственной пары фактически является
самостоятельной задачей линейного программирования и
может быть решена независимо от другой. Однако при опре-
делении симплексным методом оптимального плана одной
из задач находится решение и другой задачи.
Двойственная задача по отношению к исходной состав-
ляется согласно следующим правилам:
1) целевая функция исходной задачи (3.1)-(3.3) формули-
руется на максимум, а целевая функция двойственной
задачи (3.4)-(3. 6) — на минимум, при этом в задаче на
максимум все неравенства в функциональных ограниче-
ниях имеют вид <, а в задаче на минимум — вид >;
2) матрица А-
«и
«21
v
a
ml
°12 •
fl
22
-
а
тг •
••
а
\п
••
а
2п
а
тп
Оптимальные экономико-математические модели 69
составленная из коэффициентов при неизвестных в сис-
теме ограничений (3.2) исходной задачи, и аналогич*
ная матрица
°21 "•
а
т\
а
22 "••
а
т2
7
а
2п
-
"'
а
тпУ
в двойственной задаче получаются друг из друга транс-
понированием ;
3) число переменных в двойственной задаче равно числу
функциональных ограничений (3.2) исходной задачи, а
число ограничений в системе (3.5) двойственной задачи —
числу переменных в исходной задаче;
4) коэффициентами при неизвестных в целевой функции
(3.4) двойственной задачи являются свободные члены в
системе (3.2) ограничений исходной задачи, а правыми
частями в ограничениях (3.5) двойственной задачи —
коэффициенты при неизвестных в целевой функции (3.1)
исходной задачи;
5) каждому ограничению одной задачи соответствует пере-
менная другой задачи: номер переменной совпадает с
номером ограничения; при этом ограничению, записан-
ному в виде неравенства <, соответствует переменная,
связанная условием неотрицательности. Если функцио-
нальное ограничение исходной задачи является равенст-
вом, то соответствующая переменная двойственной зада-
чи может принимать как положительные, так и отрица-
тельные значения.
Математические модели пары двойственных задач могут
быть симметричными и несимметричными. В несимметрич-
ных двойственных задачах система ограничений исходной
задачи задается в виде равенств, а двойственной — в виде
неравенств, причем в последней переменные могут быть и
отрицательными. В симметричных задачах система ограни-
чений как исходной, так и двойственной задачи задается
неравенствами, причем на двойственные переменные нала-
гается условие неотрицательности. В дальнейшем мы будем
А
г
=
а
п
°12
70
Глава 3
рассматривать только симметричные взаимодвойственные
задачи линейного программирования.
Итак, согласно теории линейного программирования ка-
ждой ЗЛП вида (3.1)-(3.3) соответствует двойственная ей
ЗЛП: (3.4)-(3.6). Основные утверждения о взаимодвойствен-
ных задачах содержатся в двух следующих теоремах.
Первая теорема двойственности. Для взаимодвойствен-
ных ЗЛП имеет место один из взаимоисключающих случаев;
1.
В прямой и двойственной задачах имеются оптимальные
решения, при этом значения целевых функций на оп-
тимальных решениях совпадают: max ДХ) = ming(Y).
2.
В прямой задаче допустимое множество не пусто, а це-
левая функция на этом множестве не ограничена сверху.
При этом у двойственной задачи будет пустое допусти-
мое множество.
3.
В двойственной задаче допустимое множество не пусто, а
целевая функция на этом множестве не ограничена
снизу. При этом у прямой задачи допустимое множест-
во оказывается пустым.
4.
Обе из рассматриваемых задач имеют пустые допусти-
мые множества.
Вторая теорема двойственности (теорема о дополняющей
нежесткости). Пусть X = (х
1
,х
2
,...,х
п
) — допустимое реше-
ние прямой задачи (3.1)-(3.3), a Y = (j/i,y
2
'---'J/m) — Допус-
тимое решение двойственной задачи (3.4)-(3.6). Для того
чтобы они были оптимальными решениями соответствую-
щих взаимодвойственных задач (3.1)-(3.3) и (3.4)-(3.6), не-
обходимо и достаточно, чтобы выполнялись следующие соот-
ношения:
У*(1Х;*;-М
=
0;*
=
1Г^
(3.7)
т
х
1&
а
иУ1 ~Cj) = 0;j=l,n. (3.8)
i=l