Линейное программирование

1.

ЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ
Главы 2 - 8

2. Предисловие. Общая задача оптимизации

Модель
системы
Оценка
полезности
исходов
ЛПР
2

3. Конечная и бесконечномерная оптимизация

Оптимизация
Конечномерная
математическое программирование
(mathematical programming)
Бесконечномерная
вариационное исчисление,
(variations calculus)
Математическое программирование – это не программирование!
3

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

Математическое программирование
Линейное программирование
Linear programming - LP
Нелинейное программирование
Nonlinear programming - NLP
Важность линейного программирования для теории и практики
4

5.

Леонид Витальевич Канторович
(1912--1986)
Вручение Нобелевской премии,
1975
Джордж Данциг
(Dantzig, George Bernard; 1914 - 2005)
Слева направо: Тьяллинг Купманс (Koopmans, Tjalling;
1910--1985), Джордж Данциг,
5
Леонид Канторович

6. Глава 2. Примеры и каноническая форма задачи линейного программирования

2.1. Задача о производственном плане

7.

На примере мебельной фабрики
7

8.

54 ед.
50 ед.
9 ед.
10 ед.
6 ед.
5 ед.
?
8 у. е.
6 у. е.
8

9.

Столы
Стулья
Всего
Дерево, ед
10
5
50
Железо, ед
6
9
54
Цена, у.е.
8
6
Замечание 1. О целочисленности
9

10. Графическая интерпретация

10
9
8
?
7
6
Оптимальный план
5
4
3
2
Множество
планов
1
1
2
3
4
5
6
7
8
9
10
10

11.

2.2. Задача о диете

12.

Белки 0.1 кг
Жиры 0.1 кг
Углеводы 0.4 кг
Июль
2008 г.
12

13.

Белки – 0, 1 кг, жиры – 0,1 кг, углеводы – 0,4 кг
13

14.

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

15. Развернутая запись

1
Развернутая запись
15

16. Матричная запись

2
Матричная запись
16

17. Векторная запись

3
Векторная запись
17

18. Приведение к канонической форме

4
Приведение к канонической форме
18

19. Приведение к канонической форме

4
Приведение к канонической форме
19

20. Приведение к канонической форме

4
Приведение к канонической форме
20

21. Пример

5
Пример
21