|
Решение задач оптимизации с применением методов линей-
ного программирования
Оптимизация с использованием математического программи-
рования
теория и методам решения задач о нахождении экстремумов
функций на множествах, определяемых линейными и нелинейными
ограничениями (равенствами и неравенствами). Наиболее известным
методом этого семейства инструментов является
линейное програм-
мирование
. Однако практическое применение находят и другие мето-
ды математического программирования: нелинейное программирова-
ние, динамическое программирование, стохастическое программиро-
вание.
Большое число экономических задач, требующих учета разно-
образных факторов и характеристик, изменяющихся во времени и
влияющих друг на друга и на экономические процессы, сводится к
линейным математическим моделям
. Традиционно оптимизацион-
ные линейные математические модели называют моделями линейно-
го программирования.
В общем виде задача линейного программирования ставится
следующим образом: максимизировать (минимизировать) функцию
(5.1)
при ограничениях
(5.2)
где
-
управляющие переменные или решения задачи,
- параметры,
- целевая функция или критерий эф-
фективности задачи.
Функция (5.1) – линейная, ограничения (5.2) – линейные. Задача
содержит n переменных и m ограничений.
n
1
j
j
j
x
c
f
n
1
j
2
i
j
ij
n
1
j
2
1
i
j
ij
n
1
j
1
i
j
ij
);
m
,
1
m
i
(
,
b
x
a
);
m
,
1
m
i
(
,
b
x
a
),
m
,
1
i
(
,
b
x
a
n
,
1
j
,
x
j
n
,
1
j
,
m
,
1
i
,
a
,
b
ij
j
f
128
Решить задачу линейного программирования это значит найти
значения управляющих переменных
, удовлетворяющих ог-
раничениям (5.2), при которых целевая функция (5.1) принимает мак-
симальное или минимальное значение. Таким образом, оптимальное
решение – это решение, наиболее предпочтительное перед другими
по определенному критерию эффективности.
Наиболее распространенный способ решения задачи – симплекс
– метод. Для применения симплекс-метода задачу следует записать в
канонической форме:
(
(5.3)
(
(5.4)
В канонической форме записи все переменные неотрицательны
и ограничениями являются неравенства. Требуется найти такие зна-
чения
, при которых целевая функция имеет максимум.
Симплекс-метод является методом направленного перебора ре-
шений системы (1.3)-(1.4). Каждое следующее решение улучшает
значение целевой функции.
Симплекс- метод включает два этапа:
1.
Определение начального решения, удовлетворяющего ограни-
чениям (5.4);
2.
Последовательное улучшение начального решения и получе-
ние оптимального решения задачи (5.3-5.4).
Каждой задаче линейного программирования, которую можно
назвать исходной, соответствует двойственная задача. Рассмотрим
исходную задачу линейного программирования следующего вида:
(5.5)
n
,
1
j
,
x
j
max
x
c
...
x
c
x
c
f
n
n
2
2
1
1
n
,
1
j
,
0
x
;
b
x
a
...
x
a
x
a
......
;
b
x
a
...
x
a
x
a
;
b
x
a
...
x
a
x
a
j
m
n
mn
2
2
m
1
1
m
2
n
n
2
2
22
1
21
1
n
n
1
2
12
1
11
n
,
1
j
,
x
j
max
x
c
....
x
c
x
c
f
n
n
2
1
1
129
(5.6)
В задаче (5.5)-(5.6) требуется максимизировать целевую функ-
цию; все ограничения являются неравенствами со знаком
, все пе-
ременные
.
Задача содержит n управляющих переменных и m ограничений.
Коэффициенты при переменных в целевой функции:
; сво-
бодные члены:
.
Двойственная задача линейного программирования имеет вид:
(5.7)
(5.8)
В двойственной задаче (5.7)-(5.8) требуется найти минимум це-
левой функции, ограничения – неравенства со знаком , управляю-
щие переменные
. Задача содержит m управляю-
щих переменных и n ограничений. Коэффициенты целевой функции
задачи
являются свободными членами исходной задачи
линейного программирования, а свободные члены двойственной за-
дачи
- коэффициентами целевой функции исходной зада-
чи. Матрица коэффициентов двойственной задачи транспонирована,
т.е. строки заменены столбцами, а столбцы – строками.
Если управляющие переменные в задаче линейного программи-
рования определяют количество единиц неделимой продукции, то оп-
тимальное решение должно быть получено в целых числах. К задачам
такого типа относится большое количество экономических задач. Ес-
ли единица составляет малую часть от общего количества, например,
0
x
.....
0
x
,
0
x
;
b
x
a
...
x
a
x
a
......
;
b
x
a
...
x
a
x
a
;
b
x
a
...
x
a
x
a
n
2
1
m
n
mn
2
2
m
1
1
m
2
n
n
2
2
22
1
21
1
n
n
1
2
12
1
11
min
y
b
...
y
b
y
b
g
m
m
2
2
1
1
0
y
,...
0
y
,
0
y
;
c
y
a
...
y
a
y
a
......
;
c
y
a
...
y
a
y
a
;
c
y
a
...
y
a
y
a
m
2
1
n
m
mn
2
2
m
1
1
m
2
m
2
m
2
22
1
21
1
m
1
m
2
12
1
11
0
y
.....
0
y
,
0
y
n
2
1
130
при планировании массового или крупносерийного производства, то
для нахождения оптимального решения применяют обычный сим-
плекс-метод и округляют полученное решение до целого. В некото-
рых случаях округление может привести к решению, отличному от
оптимального. Линейные задачи, решение которых может быть полу-
чено в целых числах, называют задачами
Do'stlaringiz bilan baham: |
