Математическое программирование (линейное программирование). Киселева Э.В - 6 стр.

UptoLike

ВУЗ: 

НГАСУ «Сибстрин» | Новосибирск

Составители: 

Рубрика: 

13 14
Линейное программирование
Линейное программирование – это раздел математическо-
го программирования, который исследует модели экстремальных
задач с линейной целевой функцией
∑
=
⋅=
n
j
jj
xc
1
Ζ
и системой ог-
раничений, состоящей из линейных уравнений и неравенств.
Классические методы нахождения экстремума функции мно-
гих переменных связаны с решением системы уравнений:
.n,j
x
j
)1(0 ==
∂
∂
Ζ
Очевидно, для линейной функции Z:
.n,jc
x
j
j
)1( ==
∂
∂
Ζ
А так как все коэффициенты с
j
одновременно не могут быть рав-
ны 0, то внутри области, образованной системой ограничений,
экстремальной точки не существует. Она может существовать на
границе области, но применение классических методов также
невозможно, так как частные производные функции Z по всем
переменным также равны константам. Поэтому для решения за-
дач линейного программирования (ЗЛП) были созданы
специаль-
ные методы.
1. ПРИМЕРЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1.1. Задача оптимального производственного планирования
Для изготовления n видов продукции P
1
,…,P
n
используется m
видов сырья S
1
,…,S
m
, запасы которого ограничены и составляют
соответственно b
1
,…,b
m
единиц. Известно, что на производство
единицы продукции P
j
(j= n,1 ) расходуется а
ij
единиц ресурса S
i
(i=
),1 m , а прибыль от реализации единицы продукции P
j
(j= ),1 n
составляет с
j
(j= ),1 n .
Требуется определить план производства, который позволяет
при наличных ресурсах получить максимальную прибыль пред-
приятия от реализации продукции.
Прежде всего запишем условия задачи компактно в виде
таблицы:
Вид продукции
Вид сырья
Р
1
... P
j
... P
n
Запас
ресурса
S
1
a
11
... a
1j
... a
1n
b
1
... ... ... ... ... ... ...
S
i
a
i1
... a
ij
... a
in
b
i
... ... ... ... ... ... ...
S
m
a
m1
... a
mj
... a
mn
b
m
Прибыль c
1
… c
j
… c
n
Составим математическую модель задачи.
Обозначим через x
j
(j=
),1 n
планируемое к выпуску количе-
ство продукции Р
j
(j= ),1 n , а через Z (х
1
,…,
x
n
) – прибыль пред-
приятия от реализации всей продукции.
Тогда
планом производства будет вектор Х = (х
1
,…,х
n
),
показывающий, какое количество продукции каждого вида будет
произведено. Переменные х
1
,…,х
n
– управляемые переменные.
Цель решения задачи (критерий оптимальности) – максими-
зировать прибыль:
Z = c
1
x
1
+ c
2
x
2
+. . . + c
n
x
n
. 
               Линейное программирование                                               1. ПРИМЕРЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ
    Линейное программирование – это раздел математическо-                                 ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
го программирования, который исследует модели экстремальных                    1.1. Задача оптимального производственного планирования
                                               n
задач с линейной целевой функцией Ζ =     ∑c
                                           j =1
                                                   j   ⋅ x j и системой ог-       Для изготовления n видов продукции P1,…,Pn используется m
                                                                              видов сырья S1,…,Sm, запасы которого ограничены и составляют
раничений, состоящей из линейных уравнений и неравенств.                      соответственно b1,…,bm единиц. Известно, что на производство
    Классические методы нахождения экстремума функции мно-                    единицы продукции Pj (j= 1, n ) расходуется аij единиц ресурса Si
гих переменных связаны с решением системы уравнений:
                                                                              (i= 1, m) , а прибыль от реализации единицы продукции Pj (j= 1, n)
                       ∂Ζ
                            = 0 ( j = 1, n) .                                 составляет сj (j= 1, n) .
                       ∂x j
                                                                                  Требуется определить план производства, который позволяет
Очевидно, для линейной функции Z:                                             при наличных ресурсах получить максимальную прибыль пред-
                                                                              приятия от реализации продукции.
                     ∂Ζ                                                           Прежде всего запишем условия задачи компактно в виде
                          = c j ( j = 1,n) .
                     ∂x j                                                     таблицы:
А так как все коэффициенты сj одновременно не могут быть рав-
                                                                                     Вид продукции Р1       ...    Pj    ...    Pn     Запас
ны 0, то внутри области, образованной системой ограничений,                    Вид сырья                                              ресурса
экстремальной точки не существует. Она может существовать на                           S1          a11      ...    a1j   ...   a1n       b1
границе области, но применение классических методов также                              ...          ...     ...    ...   ...    ...      ...
невозможно, так как частные производные функции Z по всем                              Si          ai1      ...    aij   ...   ain       bi
переменным также равны константам. Поэтому для решения за-                             ...          ...     ...    ...   ...    ...      ...
дач линейного программирования (ЗЛП) были созданы специаль-                            Sm          am1      ...    amj   ...   amn      bm
ные методы.                                                                         Прибыль         c1      …       cj   …      cn

                                                                                  Составим математическую модель задачи.
                                                                                  Обозначим через xj (j= 1, n) планируемое к выпуску количе-
                                                                              ство продукции Рj (j= 1, n) , а через Z (х1,…, xn) – прибыль пред-
                                                                              приятия от реализации всей продукции.
                                                                                  Тогда планом производства будет вектор Х = (х1,…,хn),
                                                                              показывающий, какое количество продукции каждого вида будет
                                                                              произведено. Переменные х1,…,хn – управляемые переменные.
                                                                                  Цель решения задачи (критерий оптимальности) – максими-
                                                                              зировать прибыль:
                                                                                                   Z = c1x1 + c2x2 +. . . + cnxn .
                                13                                                                                14

Страницы