Методы и системы поддержки принятия решений. Задачи линейного и целочисленного программирования

1. Методы и Системы Поддержки Принятия Решений Methods and Systems for Decision-Making Support

Л-3
Задачи линейного и
целочисленного программирования
(классические задачи исследования операций)
2019

2. Задачи Линейного Программирования

ЗЛП: частный случай задач оптимизации
при наличии ограничений, в которых:
- ц.ф. линейна,
- система ограничений, выделяющая
допустимую область возможных значений,
представляет собой систему линейных
неравенств.

3. Стандартная форма ЗЛП

n
Z= c j x j max
(1)
j 1
n
a x
j 1
ij
j
bi , i 1,..., m, (2)
x j 0, j 1,..., n

4. Каноническая форма ЗЛП

n
Z= c j x j max
j 1
n
a x
j 1
ij
j
bi , i 1,..., m,
x j 0, j 1,..., n. (3)

5. Общая форма ЗЛП:

≤, = , (и свободные переменные
(не все неотрицательные)
(все формы ЗЛП эквивалентны…)
Ограничения выделяют выпуклое
многогранное множ-во
(если оно ограниченно – выпуклый
многоугольник/многогранник)
(Рисунки плоскостей – представление
множества огранич D)

6. Классические ЗЛП

7. 3.1 Задача производственного Планирования

Предприятие может производить продукцию n типов, имеется
запас ресурсов m типов;
aij – кол-во ресурса i-ого вида, необходимого для про-ва
единицы продукции j-ого вида;
cj - стоимость (прибыль) 1-цы продукции j-ого вида;
xj – план производства – кол-во выпускаемой продукции j-ого
вида.
bi – количество ресурса (запас) i–ого типа; i=1,…,m, j=1,…,n.
Цель: найти план про-ва максимизирующего стоимость
выпускаемой продукции при заданных ограничениях.
x=(x1,…,xn) – удовлетворяющий ограничениям (2) – план
(допустимый план), допустимое решение,
X – множ-во допустимых решений.
Модель: ур-е (1)

8. Задача производственного Планирования

Табл. матрица Планирования:
xn
Запас
a1j
a1n
b1
aij
ain
bi
x1
…
xj
1
a11
…
i
ai1
m
an1
Прибыль
c1
…
bm
…
cj
…
cn

9. 3.2 Задача о пищевом рационе (о смеси)

Имеется набор первичных продуктов, из
которых можно составить различные
(питательные) смеси. Требование: в смеси колво питательных веществ (белков, жиров, углер.,
минер. Солей, витаминов,…) должно быть не
ниже установленной нормы.
Задача: найти допустимую смесь минимальной
стоимости

10. Задача о пищевом рационе (о смеси)

Модель: Матрица планирования:
aij – кол-во питат. веществ i-ого вида, содержащееся в 1-це
продукта j-ого вида;
cj - стоимость 1-цы вещества j-ого вида;
bi – (минимальная) норма питат. Веществ i–ого типа в смеси;
xj – кол-во продукта j-ого вида в смеси, i=1,…,m, j=1,…,n
n
Z= c j x j min
j 1
n
a x
j 1
ij
j
bi , i 1,..., m, x j 0, j 1,..., n.

11. 3.3 Задача о перевозках (транспортная задача)

Имеется m пунктов производства (поставки)
некоторого однородного продукта и n пунктов
его потребления. Для каждого пункта
производства i=1,…,m, и каждого пункта его
потребления j=1,…,n, заданы:
ai – объем производства в пункте i;
bj – объем потребления в пункте j;
сij – затраты на перевозку 1цы продукта от
пункта производства i до пункта потребления
j.

12. Задача о перевозках (транспортная задача)

Предполагают производство сбалансированным:
m
n
a b
i 1
i
j 1
j
( 0)
(потребление не превышает производства).
Задача: Составить план перевозок:
- не выводящий за пределы производства,
- полностью обеспечивающий всех потребителей,
- дающий минимум суммарных затрат на перевозку:

13. Задача о перевозках (транспортная задача)

xij – обем перевозок из i в j.
m
Z=
i 1
m
x
i 1
ij
xij 0
n
c x
j 1
ij ij
bj ;
min
n
x
j 1
ij
ai

14. Задача о перевозках (транспортная задача)

Th. При любых целых значениях ai, bj ,
транспортная задача всегда имеет
целочисленный оптимальный план
(независимо от коэффициентов сij ).

15. Целочисленные ЗЛП [ЦЗЛП] (дискретные ЗЛП)

- ЗЛП, в которых на все переменные
наложено требование целочисленности.
(полностью целочисл, частично целочисл.)
Бинарная задача ЦЛП: xi - только 0, 1.

16. 3.4 Задача о ранце (рюкзаке) (knapsack problem)

(Классич вариант ЦЗЛП)
Имеется n предметов, заданы:
aj – вес предмета j;
сj - ценность предмета j;
Максимально допустимый вес ранца
(грузоподъемность): А.
Загрузить ранец максимальной ценностью

17. Задача о ранце (рюкзаке)

Реш-е.:
xj =1 – если берем j-ый предмет,
xj =0 – не берем j-ый предмет.
Модель:
n
Z= c j x j max
j 1
n
a x
j 1
j
j
A,
x j {0,1}, j 1,..., n.

18. Задача о ранце (рюкзаке)

Разновидности модели о ранце:
n
Z= c j x j max
j 1
n
a x
j 1
ij
j
Ai , i 1,..., m, x j 0, j 1,..., n.
x j {0,1}, j 1,..., n.

19. 3.5 Задача о назначениях (задача выбора)

Имеется n работ и n кандидатов
для их выполнения.
Назначение кандидата i на работу j
связано затратами сij .
Требуется назначить кандидатов на
все работы с минимальными
суммарными затратами.

20. Задача о назначениях (задача выбора)

Реш-е:
xij =1 – если i-ый кандидат назначен на j-ую работу.
xij =0 – в противном случае.
n
Z=
i 1
m
x
ij
i 1
n
x
j 1
ij
n
c x
j 1
ij ij
min
1 ( b j );
1 ( ai )
xij {0,1}

21. Задача о назначениях (задача выбора)

Реш-е:
xij =1 – если i-ый кандидат назначен на j-ую работу.
xij =0 – в противном случае.
[частный случай транспортной задачи (m=n, ai=bj=1)]
n
Z=
i 1
n
x
ij
i 1
n
x
j 1
ij
n
c x
j 1
ij ij
min
1 ( b j );
1 ( ai )
xij {0,1}

22. Задача о бродячем торговце (задача коммивояжера)

Имеется n+1 город;
сij – матрица расстояния между городами (i -j)
Выезжая из исходного города, коммивояжер должен
побывать во всех остальных городах ровно 1 раз и
вернуться в исходный город.
Модель: xij =1 – если Комм из города i едет в j;
xij =0 – в противном случае.
(ДЗ: составить ЗЛП)!

23. Общая ЗЛП

Th. Линейная ф-я n переменных
(отличная от постоянной), заданная
на замкнутом ограниченном
множестве, достигает глобального
экстремума на границе области.
(grad)

24. Общая ЗЛП

Примеры: нет решений, 1 решение, много
решений (на ребре), не имеет решений
(имеет max, или min)
(grad)