2. Лекции Практические и лабораторные занятия

1.Понятие о динамическом программировании(ДП).

2.Постановка задачи ДП.
Рекомендуемая литература:

1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981.

2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996

3. практические и лабораторные занятия

2.Уметь показывать алгоритм на блок- схемах

1. 
   Составить алгоритм решения задач
   

2х₁+х₃-х₄+х₅ ≤2

х₁-х₃+2х₄+х₅ ≤ 3

2х₂+х₃-х₄+2х₅ ≤ 6

х₁,х₂,х₃,х₄,х₅≥0
2.F= х₁-7х₂-х₄+2х₅

х₁-х₃-х₄+4х₅ ≤2

3х₁+х₃+2х₄ ≥ 3

х₂-х₄+2х₅ ≤ 6

х₁,х₂,х₃,х₄,х₅≥0
3.F= х₁-2х₂-5х₄

2х₁+х₃-+х₅ ≥7

х₁-3х₃+2х₄+х₅ ≤ 13

4х₂-х₄+2х₅ ≥ 6

х₁,х₂,х₃,х₄,х₅≥0
4.F= 3х₁-5х₄+х₅

12х₁+х₃-х₄ ≥5

х₁-х₃+2х₄+х₅ ≤ 3

х₁,х₂,х₃,х₄,х₅≥0

5.F= 3х₁-2х₂-5х₄+х₅

2х₁+х₃-х₄+х₅ ≤2

х₁-2х₄+х₅ ≥ 3

х₃-х₄+2х₅ ≥ 6

х₁,х₂,х₃,х₄,х₅≥0
Практическая работа 2. Решение задач линейного программирования графическим методом

Цель: 1. Изучение графического метода

2. Построение графика функции

Записать в форме основной задачи линейного программирования задачу: найти максимум функции

1. 
   F= 3х₁-2х₂-5х₄+х₅ при условиях
   

х₁-х₃+2х₄+х₅ ≤ 3

2х₂+х₃-х₄+2х₅ ≤ 6

х₁,х₂,х₃,х₄,х₅≥0

2. 
   F= х₁-2х₂-5х₄ при условиях
   

х₁-3х₃+2х₄+х₅ = 13

4х₂-х₄+2х₅ = 6

х₁,х₂,х₃,х₄,х₅≥0

3. 
   F= х₁-7х₂-х₄+2х₅
   

3х₁+х₃+2х₄ ≥ 3

х₂-х₄+2х₅ = 6

х₁,х₂,х₃,х₄,х₅≥0

4. 
   F= 3х₁-5х₄+х₅
   

х₁-х₃+2х₄+х₅ = 3

х₁,х₂,х₃,х₄,х₅≥0

5. 
   F= 3х₁-2х₂-5х₄+х₅
   

х₁-2х₄+х₅ ≥ 3

х₃-х₄+2х₅ ≥ 6

х₁,х₂,х₃,х₄,х₅≥0

2. Запись задача состоящих в максимизации функции

1. 
   F= -х₁+2х₂-х₃ +х₄ при условиях
   

х₁+2х₂+х₃ -х₄≥8

3х₁-х₂+2х₃≤10

х₁,х₂,х₃≥0

2. 
   F= -2х₁+х₂+5х₃ при условиях
   

6х₁-3х₂+4х₃=18

3х₁+3х₂-2х₃≤16

х₁,х₂,х₃≥0

3. 
   F= -8х₁+2х₂-5х₃ при условиях
   

6х₁+7х₂+4х₃=8

3х₁-3х₂-3х₃≤6

х₁,х₂,х₃≥0

4. 
   F= х₁+2х₂-5х₃ при условиях
   

-х₁+7х₂-4х₃=2

-х₁+9х₂+3х₃≤6

х₁,х₂,х₃≥0

5. 
   F= -8х₁+2х₂-5х₃ при условиях
   

6х₁+7х₂+4х₃=8

3х₁-3х₂-3х₃≤6

х₁,х₂,х₃≥0

1. 
   F= -х₁+2х₂-х₃ при условиях
   

х₁+2х₂+х₃ ≥8

3х₁-х₂+2х₃≤10

х₁,х₂,х₃≥0

2. 
   F= -2х₁+х₂ при условиях
   

6х₁-3х₂=18

3х₁+3х₂≤16

х₁,х₂,х₃≥0

3. 
   F= -8х₁+2х₂-5х₃ при условиях
   

6х₁+7х₂+4х₃=8

3х₁-3х₂-3х₃≤6

х₁,х₂,х₃≥0

4. 
   F= х₁+2х₂-5х₃ при условиях
   

-х₁+7х₂-4х₃=2

-х₁+9х₂+3х₃=6

х₁,х₂,х₃≥0

5. 
   F= -8х₁+2х₂-5х₃ при условиях
   

6х₁+7х₂+4х₃=8

3х₁-3х₂-3х₃=6

х₁,х₂,х₃≥0

2. Построение симплекс-таблицы.

Решить задачи симплекс- методом

1. 
   F= 3х₁-2х₂-5х₄+х₅ max при условиях
   

х₁-х₃+2х₄+х₅ = 3

2х₂+х₃-х₄+2х₅ = 6

х₁,х₂,х₃,х₄,х₅≥0

2. 
   F= х₁-2х₂-5х₄ max при условиях
   

х₁-3х₃+2х₄+х₅ = 13

4х₂-х₄+2х₅ = 6

х₁,х₂,х₃,х₄,х₅≥0

3. 
   F= х₁-7х₂-х₄+2х₅ min
   

3х₁+х₃+2х₄ = 3

х₂-х₄+2х₅ = 6

х₁,х₂,х₃,х₄,х₅≥0

4. 
   F= 3х₁-5х₄+х₅ max
   

х₁-х₃+2х₄+х₅ = 3

х₁,х₂,х₃,х₄,х₅≥0

5. 
   F= 3х₁-2х₂-5х₄+х₅ min
   

х₁-2х₄+х₅ = 3

х₃-х₄+2х₅ = 6

х₁,х₂,х₃,х₄,х₅≥0

2. Построение симплекс-таблицы методом искусственного базиса.

Решить симплекс таблицу методом искусственного базиса.

1. 
   F= -х₁+2х₂-х₃ при условиях
   

х₁+2х₂+х₃ +х₅=8

3х₁-х₂+2х₃+х₆=10

х₁,х₂,х₃≥0

2. 
   F= -2х₁+х₂ при условиях
   

6х₁-3х₂+х₄=18

3х₁+3х₂+х₅=16

х₁,х₂,х₃≥0

3. 
   F= -8х₁+2х₂-5х₃ при условиях
   

6х₁+7х₂+4х₃+х₄=8

3х₁-3х₂-3х₃+х₅=6

х₁,х₂,х₃≥0

4. 
   F= х₁+2х₂-5х₃ при условиях
   

-х₁+7х₂-4х₃+х₅=2

-х₁+9х₂+3х₃+х₆=6

х₁,х₂,х₃≥0

5. 
   F= -8х₁+2х₂-5х₃ при условиях
   

5х₁+2х₂+5х₃= 1

6х₁+7х₂+4х₃+х₄=8

3х₁-3х₂-3х₃+х₅=6

х₁,х₂,х₃≥0
Практическая работа 6. Решение транспортной задачи методом северо- западного угла.

Цель: Построение модели транспортной задачи.

Задания практической работы:

Решить транспортную задачу методом северо- западного угла.

1. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 1 9 7

3 5 8 9

2. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

6 1 9 6

3 5 9 9

3. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

4 1 8 7

3 5 5 9

4. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 1 9 5

3 5 6 9

5. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 2 9 7

3 7 8 9

1. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

с= 4 6 2 12

3 5 8 9

2. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

с= 4 7 2 12

3 5 9 9

3. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

с= 4 6 2 10

3 5 5 9

4. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 1 9 5

3 5 6 9

5. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 2 9 7

3 7 8 9

Решить транспортную задачу методом аппроксимации Фогеля.

1. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 1 9 7

3 5 8 9

2. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

6 1 9 6

3 5 9 9

3. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

4 1 8 7

3 5 5 9

4. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

с= 4 6 2 7

3 5 6 9

5. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 2 9 7

3 7 8 9
Практическая работа 9. Решение транспортной задачи методом потенциалов

Решить транспортную задачу методом потенциалов.

1. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 1 9 7

3 5 8 9

2. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

6 1 9 6

3 5 9 9

3. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

4 1 8 7

3 5 5 9

4. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 1 9 5

3 5 6 9

5. 
   на 3 хлебокомбинатах ежедневно производится 110, 190, 90 т муки. Эта мука потребляется 4 хлебозаводами, ежедневная потребность которых 90,60,170,80 т муки. Расстояние между ними в км задано матрицей
   

8 2 9 7

3 7 8 9

2. Теорема Куна-Таккера.

Решить задачи квадратичного программирования с помощью функции Лагранжа.

1. 
   F= 2х₁+4х₂-х₁²-2х₂²
   

2х₁-х₂ ≤ 12

х₁,х₂ ≥0

2. 
   F= 3х₁+5х₂-3х₁²-2х₂²
   

2х₁+х₂ ≤ 12

х₁,х₂ ≥0

3. 
   F= -2х₁+6х₂-х₁²-х₂²
   

2х₁+7х₂ ≤ 12

х₁,х₂ ≥0

4. 
   F= 2х₁-4х₂+х₁²-2х₂²
   

2х₁-4х₂ ≤ 12

х₁,х₂ ≥0

5. 
   F= 2х₁+4х₂-7х₁²+2х₂²
   

2х₁-7х₂ ≤ 9

х₁,х₂ ≥0

Практическая работа 11. Градиентные методы. Метод Франко-Вулфа.

Цель: 1. Решение задач с помощью градиентных методов.

2. Решение задач с использованием метода Франко-Вулфа.

Решить задачи с помощью метода Франко-Вулфа.

1. F= 2х₁+4х₂-7х₁ ²+2х₂² max

Х₁+2х₂ ≤ 8

2х₁-7х₂ ≤ 9

х₁,х₂ ≥0

Х₁+2х₂ ≤ 4

-2х₁+7х₂ ≤ 9

х₁,х₂ ≥0

Х₁+2х₂ ≤ 4

8х₁+7х₂ ≤ 7

х₁,х₂ ≥0

5Х₁-2х₂ ≥4

-2х₁+7х₂ ≤ 9

х₁,х₂ ≥0

-5Х₁-2х₂ ≥4

-2х₁+2х₂ ≤ 9

х₁,х₂ ≥0

Найти максимальное значение функции:

1. 
   F= -х₁²-х₂²
   

х₁,х₂ ≥0

2. 
   F= -2х₁²-х₂²
   

х₁,х₂ ≥0

3. 
   F= -3х₁²-х₂²
   

х₁,х₂ ≥0

4. 
   F= -х₁²-х₂²
   

х₁,х₂ ≥0

5. 
   F= -х₁²-х₂²
   

х₁,х₂ ≥0

2. Решение задач методом кусочно- линейной аппроксимации

Решить задачу методом кусочно- линейной аппроксимации:

1. F= х₂-х₁²+6х₁-9 max

2х₁+3х₂ ≤ 24

х₁+2х₂ ≤ 15

3х₁+2х₂ ≤ 24

х₁,х₂ ≥0

2. F= 4х₂-х₁²+х₁-1 max

2х₁-х₂ ≤ 24

2х₁+2х₂ ≤ 1

3х₁+2х₂ ≤ 18

х₁,х₂ ≥0

3. F= х₂-х₁²+16х₁-7 max

2х₁+3х₂ ≤ 24

х₁+2х₂ ≤ 15

3х₁+9х₂ ≤ 11

х₁,х₂ ≥0

4. F= -х₂-х₁²+6х₁-3 max

2х₁+3х₂ ≤ 24

х₁+2х₂ ≤ 1

-3х₁+х₂ ≤ 2

х₁,х₂ ≥0

5. F= х₂-3х₁²+7х₁-9 max

2х₁+3х₂ ≤ 24

-х₁+4х₂ ≤ 1

-3х₁+2х₂ ≤ 7

х₁,х₂ ≥0
Практическая работа 14. Двойственные задачи.

Цель: 1. Прямая задача.

2. Двойственная задача.

Сформулировать двойственные задачи по отношению к нижеследующим задачам:

1. F= х₁-2х₂+5х₃ max

2х₁+2х₂+4х₃ ≤ 18

2х₁+х₂-3х₃ ≤ 20

5х₁-3х₂+6х₃ ≥ 19

х₁,х₂,х₃≥0
2. F= 3х₁+3х₂-4х₃ max

2х₁+х₂-3х₃ ≥ 18

4х₁-5х₃ ≤ 12

3х₁-2х₂+х₃ ≥ 14

х₁,х₂,х₃ ≥0
3. F= 6х₁-х₂+3х₃ max

3х₁-7х₂+5х₃ ≤ 15

2х₁+3х₂-4х₃ =16

6х₁+5х₂-8х₃ ≤ 12

х₁,х₂,х₃ ≥0
4. F= -2х₁+5х₂-4х₃ max

4х₁+2х₂-3х₃ ≥9

3х₁-2х₂+5х₃ ≥ 8

х₁+3х₂+4х₃ ≥ 12

х₁,х₂,х₃ ≥0
5. F= -3х₁+4х₂-6х₃ max

2х₁+3х₂-х₃ ≥ 8

-3х₁+2х₂-2х₃ =10

5х₁-4х₂+х₃ ≥ 7

х₁,х₂,х₃ ≥0
Практическая работа 15. Динамическое программирование.

Цель: Решение задач динамического программирования.

Задания практической работы:

Найти распределение средств между предприятиями обеспечивающих максимальный прирост выпуска продукции:

1. 
   Совет директоров фирмы рассматривает вопрос по наращиванию производственных мощностей для увеличения выпуска однородной продукции на 4 предприятиях принадлежащих фирме. Для расширения производства совет директоров выделяет средства в объеме 20 млн.ден.ед. Прирост на предприятиях зависит от выделенной суммы. Его значения представлены в таблице:
   

   Выделенные средства (млн.)	Прирост выпуска продукции
   	1	2	3	4
   20	8	10	12	11
   40	16	20	21	23
   60	25	28	27	30
   80	36	40	38	37
   100	44	48	50	51
   120	62	62	63	63

2. 
   Совет директоров фирмы рассматривает вопрос по наращиванию производственных мощностей для увеличения выпуска однородной продукции на 4 предприятиях принадлежащих фирме. Для расширения производства совет директоров выделяет средства в объеме 20 млн.ден.ед. Прирост на предприятиях зависит от выделенной суммы. Его значения представлены в таблице:
   

   Выделенные средства (млн.)	Прирост выпуска продукции
   	1	2	3	4
   20	8	10	17	11
   40	17	30	21	28
   60	25	28	29	30
   80	36	40	38	41
   100	49	56	51	51
   120	62	62	63	63

3. 
   Совет директоров фирмы рассматривает вопрос по наращиванию производственных мощностей для увеличения выпуска однородной продукции на 4 предприятиях принадлежащих фирме. Для расширения производства совет директоров выделяет средства в объеме 20 млн.ден.ед. Прирост на предприятиях зависит от выделенной суммы. Его значения представлены в таблице:
   

   Выделенные средства (млн.)	Прирост выпуска продукции
   	1	2	3	4
   20	8	10	12	11
   40	7	20	10	23
   60	25	28	27	30
   80	36	15	38	37
   100	44	48	50	49
   120	62	62	63	63

4. 
   Совет директоров фирмы рассматривает вопрос по наращиванию производственных мощностей для увеличения выпуска однородной продукции на 4 предприятиях принадлежащих фирме. Для расширения производства совет директоров выделяет средства в объеме 20 млн.ден.ед. Прирост на предприятиях зависит от выделенной суммы. Его значения представлены в таблице:
   

   Выделенные средства (млн.)	Прирост выпуска продукции
   	1	2	3	4
   20	8	10	12	11
   40	16	20	34	23
   60	25	28	27	30
   80	36	58	38	37
   100	32	48	50	47
   120	62	62	63	63

5. 
   Совет директоров фирмы рассматривает вопрос по наращиванию производственных мощностей для увеличения выпуска однородной продукции на 4 предприятиях принадлежащих фирме. Для расширения производства совет директоров выделяет средства в объеме 20 млн.ден.ед. Прирост на предприятиях зависит от выделенной суммы. Его значения представлены в таблице:
   

Задания предоставляется в письменном или распечатанном виде, выполненные на компьютере в текстовом редакторе Word, с обязательными пояснениями по выполнению заданий, размер шрифта 14, размер бумаги А4 (210х298 мм). В тексте можно использовать различные шрифты, например, Arial, Times New Roman; различное начертание для выделения отдельных элементов текста: полужирный, курсив, подчеркнутый.

1. 
   Как строится математическая модель.
   
2. 
   В чем определяется неполнота оптимизационной модели.
   
3. 
   Основные элементы модели.
   

1. 
   Экономико- математический анализ полученных оптимальных решений.
   
2. 
   Основные элементы линейной алгебры. Их роль при построении модели.
   
3. 
   Анализ моделей на чувствительность. Виды моделей.
   

1. 
   Построение модели задачи планирования производства.
   
2. 
   Графическое решение двухмерной задачи линейного программирования.
   
3. 
   Графическое и аналитическое решение матричных и биматричных игр.
   

1. 
   Решение задачи с применением симплекс- метода.
   
2. 
   Нахождение максимума и минимумам функции.
   
3. 
   Решение задачи методом искусственного базиса.
   

1. Решение методом Лагранжа задачи о потреблении.

2. Нахождение совершенного равновесия методом обратной индукции.

3. Нахождение экстремума функции.

- наименование учебной дисциплины;

- курс, номер учебной группы;

- фамилию, имя, отчество автора;

1. 
   Основные принципы составления модели.
   
2. 
   Характеристика модели при выборе определяющего метода.
   
3. 
   Основные понятия и характеристики методов линейного программирования.
   
4. 
   Особенности задач нелинейного программирования.
   
5. 
   Решение задач методом Лагранжа.
   
6. 
   Определение ценности ресурсов и чувствительность решения к изменению запасов сырья.
   
7. 
   Целесообразность включения в план новых переменных.
   
8. 
   Применение симплекс- метода при решение задач.
   
9. 
   Решение задач методом искусственного базиса.
   
10. 
    Метод Лагранжа при решении задач о потреблении.
    

4.2. перечень тем рефератов для текущего и входного контроля знаний студентов (тесты, вопросы коллоквиумов и т.д.) и др.

1. 
   Основные понятия методов оптимизации, история возникновения, перспективы развития. Области применения.
   
2. 
   Понятие модели. Классификация экономико-математических моделей
   
3. 
   Оптимизационные модели
   
4. 
   Примеры содержательных постановок задач линейного программирования
   

5. Задача об оптимальном использовании ресурсов

6. Транспортная задача линейного программирования

7. 
   Различные формы задач линейного программирования
   

8. Стандартная форма задачи линейного программирования

9. 
   Каноническая форма задачи линейного программи­рования (ЗЛП)
   
10. 
    Переход от стандартной формы задачам линейного программирования (ЗЛП) к канонической
    
11. 
    Графический метод решения задач линейного программирования
    
12. 
    Основные теоремы линейного программирования
    
13. 
    Геометрическая интерпретация симплекс-метода
    
14. 
    Использования симплекс-метода для решения задачи линейного программирования
    
15. 
    Двойственные задачи линейного программирования
    
16. 
    Построение двойственной задачи по заданной прямой
    
17. 
    Содержательная интерпретация прямой и двойст­венной задачи. Прямая задача. Двойственная задача
    

18. Основное неравенство теории двойственности

19. Экономический смысл первой (основной) теоремы двойственности

20. 
    Формулировка задач нелинейного программирования и их классификация
    
21. 
    Практическая реализация методов нелинейного программирования
    
22. 
    Задачи, решаемых с применением методов нелинейного программировании . Решение совместных систем линейных алгебраиче­ских уравнений (n x п). Решение произвольных систем алгебраических урав­нений. Задачи уравнивания. Задача о защите поверхности.
    
23. 
    Динамическое программирование. Многоэтапные процессы принятия решений
    
24. 
    Принцип оптимальности и уравнение Р. Беллмана
    
25. 
    Типы задач, к которым можно применить метод динамического программирования