Составляющие постановки задачи оптимизации
Формальная постановка задачи оптимизации
Краткая классификация оптимизационных задач
Задача линейного программирования (ЛП)
Матричная форма общей задачи ЛП
В постановке (5), (6):
2. Стандартная задача ЛП
3. Каноническая задача ЛП
Экономические интерпретации задачи ЛП
Какое количество единиц каждого продукта необходимо произвести, чтобы получить максимальную прибыль?
3. Целевая функция: чистая прибыль от реализации всего плана производства
Формальная постановка задачи планирования производства
Транспортная задача (ТЗ)
II.1. ТЗ по критерию стоимости
Формальная постановка ТЗ по критерию стоимости
II.2. ТЗ по критерию времени
Формальная постановка ТЗ по критерию времени
Пример 1.
Прибыль от реализации единицы продукции и составляет 20 и 30 тыс. рублей соответственно.
Потребление ресурсов не должно превышать их запасы:
Пример 2.
Каноническая форма:
414.30K
Category: mathematicsmathematics

Составляющие постановки задачи оптимизации

1.

Список литературы
1. Исследование операций в экономике: Учебное пособие для
вузов / Н.Ш. Кремер и др. – М.: Банки и биржи, ЮНИТИ,
1997. – 407 с.
2. Акулич И.Л. Математическое программирование в примерах
и задачах: Учебное пособие. – М.: Высш. шк., 1993. – 336 с.
3. Соловьев В.И. Методы оптимальных решений: Учебное
пособие. – М.: Финансовый университет, 2012. - 364 с.

2. Составляющие постановки задачи оптимизации

• Решение (план) задачи - вектор X [ x1 , x2 ,....xn ] .
T
• Целевая функция (функция цели, показатель
эффективности) F X .
• Условия D (система ограничений), налагаемые на
компоненты вектора
X
.

3. Формальная постановка задачи оптимизации

определить
min(max) F ( X )
X D
,
(1)
где
h ( X ) 0 , i 1,k
(2)
i
D:
j 1,l
g j ( X ) 0 ,
*
Допустимый план X , доставляющий функции цели
экстремальное значение
оптимальным.
(min
или
max),
называется

4. Краткая классификация оптимизационных задач


Признак
Классы задач
1 Наличие
ограничений
Условной
оптимизации
2 По виду целевой
функции и
ограничений X
Линейного
программирования
3 По виду вектора
Непрерывной
оптимизации
4 По размерности
целевой функции
5 По наличию и виду
неопределенных
факторов
Безусловной оптимизации
Нелинейного
программирования
Дискретной
оптимизации
Скалярной оптимизации
Детерминированной
оптимизации
Стохастической
оптимизации
Динамического
программирования
Многокритериальной
оптимизации
Оптимизации в
условиях
неопределенности .

5. Задача линейного программирования (ЛП)

1. Общая задача ЛП
n
определить
где
min ( max ) F ( X )
X D
cjxj
j 1
n
aij x j bi , i 1,k
j
1
n
D : aij x j bi , i (k 1) ,m
j 1
x 0,
j 1,l
j
(3)
(4)

6. Матричная форма общей задачи ЛП

определить min ( max ) F ( X )
X D
где
C X,
A1 X B1
D : A2 X B2
j 1,l
x j 0,
T
(5)
(6)

7. В постановке (5), (6):

T
dim C 1 n
dim A1 k n
dim A2 s n
k s m;
l n.
dim X n 1
dim B1 k 1
dim B2 s 1

8. 2. Стандартная задача ЛП

определить
min ( max ) F ( X )
X D
C X,
T
(7)
где
AX B
D:
X 0n
(8)

9. 3. Каноническая задача ЛП

определить
min ( max ) F ( X )
X D
где
!!!
Замечание.
CT X ,
AX B
G:
X 0n
Любая
задача
(9)
(10)
ЛП
может
быть
представлена в виде канонической, стандартной или
общей задачи ЛП.

10. Экономические интерпретации задачи ЛП

I.
Вид
ресурса
Запас
ресурса
Задача планирования производства
Стоимость
единицы
ресурса
Количество единиц ресурсов, затрачиваемых на
производство единицы продукции
P1
P2

Pj

Pn
R1
b1
d1
a11
a12

a1 j

a1n
R2
b2
d2
a21
a22

a2 j

a2n






ai1
ai2

aij

ain
am1
am2

amj

amn
c1
c2

cj

cn

Ri

Rm

bi

di

bm

dm
Цена продукта

11. Какое количество единиц каждого продукта необходимо произвести, чтобы получить максимальную прибыль?

Постановка задачи.
T
1. План производства: X x1 , , xn
2. Ограничения.
• Физический смысл:
x j 0, j 1, n
(11)
;
• Условие ограниченного спроса:
x j k j , j 1, n;
(12)
• Ресурсов должно хватить:
n
aij x j bi
j 1
i 1,m
;
(13)

12. 3. Целевая функция: чистая прибыль от реализации всего плана производства

• Себестоимость
s j единицы продукции Pj :
m
s j di aij
i 1
j 1,n
• Чистая прибыль от реализации единицы продукции
qj cj sj
Pj :
j 1,n
• Чистая прибыль от реализации всего плана производства:
n
F X q j x j , j 1, n
j 1
(14)

13. Формальная постановка задачи планирования производства

Требуется определить план производства X
x1 ,
,
T
xn ,
обеспечивающий максимальное значение целевой функции
F X вида (14) при соблюдении ограничений на вектор X
вида (11), (12), (13).
Замечание. Постановка (11)-(14) является стандартной
задачей ЛП.

14. Транспортная задача (ТЗ)

II. Транспортная задача (ТЗ)
Потребители
\\\\\\\\\\\\\\\
Источники
И1

Иi
П1

Пj

Пn
c11

c1 j

c1n





cij
ci1

Кол-во
ресурсов
a1

cin
ai




Иm
cm1

b1

Заявки на
товары от
потребителей

cmj
bj



cmn

bm
am
ai b j
i
j

15. II.1. ТЗ по критерию стоимости

Предполагаем, что
cij - стоимость перевозки единицы ресурса И i со склада
в пункт потребления П j ;
ai b j
i
j
, т.е. ТЗ с правильным балансом.
Постановка задачи.
1. План производства:
T
X xij , i 1, m; j 1, n .
2. Ограничения.
• физический смысл:
xij 0, i 1, n; j 1, n .
(15)

16.

• Емкости складов д.б. израсходованы полностью:
n
(16)
i 1, m .
xij ai
j 1
• Заявки, поданные потребителями, д.б. удовлетворены:
m
(17)
xij b j j 1, n .
i 1
3. Общая стоимость перевозок:
m n
F X cij xij .
i 1 j 1
(18)

17. Формальная постановка ТЗ по критерию стоимости

Требуется определить план перевозок
X ,
обеспечивающий минимальное значение целевой функции
F X вида (18) при соблюдении ограничений на вектор
вида (15), (16), (17).
Замечание. Постановка (15)-(18) является канонической
задачей ЛП.

18. II.2. ТЗ по критерию времени

Предполагаем, что
- время перевозки ресурса
cij xij
пункт потребления
со склада И i в
П j (зависит, вообще говоря, от
объема перевозки );
ai b j
i
, т.е. ТЗ с правильным балансом.
j
Постановка задачи.
1. План производства:
T
X xij , i 1, m; j 1, n .
2. Ограничения:– (15)-(17).

19.

3. Общее время всех перевозок T – все перевозки
заканчиваются, в момент, когда заканчивается самая
длительная из всех перевозок:
T F X max
i 1, m ,
j 1, n ,
xij 0
c x
ij
ij
(19)

20. Формальная постановка ТЗ по критерию времени

Требуется определить план перевозок
X ,
обеспечивающий минимальное значение целевой функции
F X вида (19) при соблюдении ограничений на вектор
вида (15), (16), (17).
Замечание. Постановка (15), (16), (17), (19) является задачей
нелинейного программирования.

21. Пример 1.

Сформулировать постановку задачи планирования
производства в виде задачи ЛП.
Дана таблица.
Вид ресурса
Запас ресурса
Кол-во единиц ресурсов,
затрачиваемых на
изготовление единицы
продукта
P1
P2
S1
S2
S3
180
6
8
160
7
6
50
4
1
S4
210
3
2

22. Прибыль от реализации единицы продукции и составляет 20 и 30 тыс. рублей соответственно.

Прибыль от реализации единицы продукции P1 и
составляет 20 и 30 тыс. рублей соответственно.
P2
Требуется найти план производства продукции, при котором
Прибыль от ее реализации будет максимальной.
T
Решение.
X x1 , x2 - план производства продукции
P1 и P2 соответственно.
Для реализации плана производства X потребуется
ресурсов
S1 : 6 x1 8x2 ; S2 : 7 x1 6 x2 ;
S3 : 4x1 1x2 ; S4 : 3x1 2x2 .

23. Потребление ресурсов не должно превышать их запасы:

6 x1 8x2 180
7 x1 6 x2 160
4x1 1x2 50
3x1 2x2 21
(20)
Исходя из физического смысла:
x1 0 , x2 0 .
(21)
Суммарная прибыль:
F X 20x1 30x2 max
(22)

24. Пример 2.

Привести стандартную задачу ЛП к канонической форме.
F X x1 x2 max
2x1 x2 1
x1 x2 0
x1 0 , x2 0.
Решение. Введем новые переменные по правилу:
2x1 x2 1 x3
x1 x2 x4

25. Каноническая форма:

F X x1 x2 max
при ограничениях
2x1 x2 x3 1
x1 x2 x4 0
x1 0 , x2 0 , x3 0 , x4 0.
English     Русский Rules