Математическая оптимизация программирования

Сентябрь 3, 2022

Главная
Алгебра
Математическая оптимизация программирования

Содержание

2. Лекцию читает к.т.н., доцент БОБРОВА ЛЮДМИЛА ВЛАДИМИРОВНА Кафедра информатики и компьютерных технологий
3. Рекомендуемая литература: 1. Ткаченко, Г. Г., Боброва Л.В. Математика, ч. 2. Методы оптимизации: учебно-методический комплекс. –
5. Пример 1 Для производства двух видов продукции фирма использует два вида ресурсов: ресурс1 – сырье, ресурс
6. Требуется найти план выпуска продукции, который обеспечивает максимальную выручку. Таблица 1
7. 1.1 Построение математической модели Обозначим: x1 – план выпуска продукции 1, x2 – план выпуска продукции
8. План X = (x1, x2) будет допустимым, если затраты каждого ресурса не превосходят их запасов, т.
9. Целевой функцией будет общая стоимость реализации плана (выручка) x1, x2: Z=40x1+100x2.
10. Итак, необходимо найти план выпуска продукции x1, x2, который обеспечивает максимальную выручку max Z=40 x1 +
11. Проверить является ли план x1=10, x2= 100 допустимым. Решение. Найдем затраты ресурсов на производство. Для выполнения
12. Самостоятельная работа 1 Задание. В условиях Примера 1 проверить допустимость плана решения при x1=20, x2= 50
13. Сверим ответы? Для выполнения этого плана потребуется 5x1+10x2 = 5⋅20 +10⋅50 = 600 кг сырья и
14. Решение. Выручка определяется целевой функцией Z=40x1+100x2. Значит, Z=40*10+100*100 = 10400 (у.е.). Пример 3 Для задачи Примера
15. Самостоятельная работа 2 Задание. В условиях Примера 1 найти выручку от реализации плана x1=20, x2= 50
16. Сверим ответы? Выручка определяется целевой функцией: Z=40*20+100*50 = 5800 (у.е.). x1=20, x2= 50 Z=40x1+100x2
17. Пример 4 Для задачи Примера 1 найти остаток ресурсов при плане x1=50, x2= 50. 5 x1
18. Самостоятельная работа 3 Задание. В условиях Примера 1 найти остаток ресурсов при плане x1=30, x2= 70
19. Сверим ответы? Для выполнения этого плана потребуется 5x1+10x2 = 5⋅30 +10⋅70 = 850 кг сырья и
20. 1.2. Определение оптимального плана производства графическим методом Построим множество допустимых решений. Проведем прямые 5 x1+10 x2
21. О 50 100 150 200 250 x1 x2 150 100 50 x1=0, x2=100, x2=0, x1=200. 5
22. О 50 100 150 200 250 x1 x2 150 100 50 M x1=0, x2=83,3, x2=0, x1=250.
23. О 50 100 150 200 250 x1 x2 150 100 83,3 50 M Строим область допустимых
24. О 50 100 150 Б 200 250 x1 x2 150 100 А 50 M Z=40x1+100x2=0 по
25. Самостоятельная работа 4 Задание. Область допустимых решений задачи линейного программирования имеет вид: Тогда максимальное значение функции
26. 1.3. Приведение задачи Примера 1 к канонической форме. Для этого введем две дополнительные переменные: s1 и
27. Ограничения (2) образуют систему двух уравнений с четырьмя неизвестными. Среди бесконечного множества решений этой системы базисные
28. Значения остальных переменных получаем из решения системы. Эти переменные назовем базисными. Базисное решение называется допустимым, если
29. 1. Пусть x1, x2 – свободные переменные. Подставляя значения x1 = 0, x2 = 0 в
30. Базисное решение означает, что первой и второй продукт не производятся. Это базисное решение является допустимым Выручка
31. 2. Пусть x1, s1 – свободные переменные. Подставляя значения x1 = 0, s1 = 0 в
32. Это базисное решение означает, что первый продукт не производится, второго продукта производится 100. Сырье полностью используется
33. 3. Пусть x1, s2 - свободные переменные. Подставляя значения x1=0, s2=0 в (2) , получаем систему
34. Это базисное решение означает, что первый продукт не производится, второго продукта производится 83 1/3. Сырье не
35. 4. Пусть x2, s1 - свободные переменные. Подставляя значения x2 = 0, s1 = 0 в
36. Базисное решение означает, что первого продукта производится 200, второй продукт не производится. Сырье полностью используется в
37. 5. Пусть x2, s2 – свободные переменные. Подставляя значения x2 = 0, s2 = 0 в
38. Это базисное решение означает, что первого продукта производится 250, второй продукт не производится. Не хватает для
39. 6. Пусть s1, s2 – свободные переменные. Тогда базисные переменные x1 и x2 найдем из системы
40. x1=100, x2=50, s1 =0, s2 =0. Это базисное решение означает, что первого продукта производится 100, второго
41. Максимальное значение выручки достигается на четвертом базисном решении в этой таблице X*={ x1=10; x2=50; S1=0; S2=0
42. 2.3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ
43. Построение симплекс-таблицы для Примера Получили план: X (0) ={x1=0, x2=0, s1=1000, s2=25}. Таблица 2
44. Анализ оптимальной симплекс-таблицы 1.Значения второго столбца определяют значения БП: x1 =100; x2 =50. Все переменные, не
45. Анализ оптимальной симплекс-таблицы Базисное решение прямой задачи: Х2 = {x1=100; x2 = 50; S1 = 0;
46. Анализ оптимальной симплекс-таблицы 2. В последней строке определяются: значение ЦФ прямой задачи Z=9000; значения 0 в
47. Самостоятельная работа Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции) имеет вид: Тогда оптимальный план
48. Самостоятельная работа Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции) имеет вид: Тогда максимальное значение
49. 1.3.3. Построение двойственной задачи линейного программирования Двойственная задача ЛП: Прямая задача 5 x1 +10 x2 =
50. Анализ оптимальной симплекс-таблицы Значение 4 в столбце s1 означает, что теневая цена 1 кг сырья равна
51. 2.3. Интервалы устойчивости. После нахождения оптимального решения выполняется анализ модели на чувствительность – необходимо знать какими
52. Решение задачи в Excel В электронную таблицу внести исходные данные :
53. Сервис – Поиск решения
54. В Поиске решения –Параметры - Заполнить окно -ОК
55. В Поиске решения Выполнить Выделить Устойчивость - ОК
56. Отчет по устойчивости решения
58. Скачать презентацию

Слайд 2

Лекцию читает
к.т.н., доцент
БОБРОВА
ЛЮДМИЛА ВЛАДИМИРОВНА
Кафедра информатики и компьютерных технологий

Слайд 3

Рекомендуемая литература:
1. Ткаченко, Г. Г., Боброва Л.В. Математика, ч. 2.

Методы оптимизации: учебно-методический комплекс. – СПб: Изд-во СЗТУ, 2009.
2. Ткаченко Г.Г. Математика, ч. 2. Методы оптимизации: учебное пособие. – СПб: Изд-во СЗТУ, 2007.
3. Таха Х.А. Введение в исследование операций. - М.: – Вильямс, 2008.

Слайд 4

Слайд 5

Пример 1
Для производства двух видов продукции фирма использует два

вида ресурсов:
ресурс1 – сырье,
ресурс 2 – время изготовления продукции на оборудовании.
Запасы ресурсов, нормы затрат каждого ресурса на единицу каждого продукта и рыночные цены приведены в табл.1.

1. Задача распределения ресурсов

Слайд 6

Требуется найти план выпуска продукции, который обеспечивает максимальную выручку.
Таблица 1

Слайд 7

1.1 Построение математической модели Обозначим: x1 – план выпуска продукции

1,
x2 – план выпуска продукции 2.
Тогда затраты сырья и времени изготовления, необходимые для реализации плана x1, x2, будут равны соответственно:

Слайд 8

План X = (x1, x2) будет допустимым, если затраты каждого ресурса

не превосходят их запасов, т. е. выполняются неравенства:

Слайд 9

Целевой функцией будет общая стоимость
реализации плана (выручка) x1, x2:

Z=40x1+100x2.

Слайд 10

Итак, необходимо найти план выпуска продукции x1, x2, который обеспечивает

максимальную выручку
max Z=40 x1 + 100 x2,
при выполнении ограничений
5 x1 +10 x2 ≤ 1000,
0,1 x1 +0,3 x2 ≤ 25,
x1≥0, x2≥0.

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

Слайд 11

Проверить является ли план x1=10, x2= 100 допустимым.
Решение. Найдем затраты

ресурсов на производство.
Для выполнения этого плана потребуется
5x1+10x2 = 5⋅10 +10⋅100 = 1050 кг сырья и
0,1x1+ 0,3x2 = 0,1⋅10 + 0,3⋅100 = 31 час работы оборудования.
Такой план выпуска недопустим, так как для его
выполнения недостаточно ресурсов.

Пример 2

5 x1 + 10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,

Слайд 12

Самостоятельная работа 1
Задание. В условиях Примера 1 проверить допустимость плана решения

при x1=20, x2= 50

Варианты A. Допустимый.
ответов: В. Недопустимый.

5 x1 + 10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,

Слайд 13

Сверим ответы?
Для выполнения этого плана потребуется
5x1+10x2 = 5⋅20 +10⋅50 =

600 кг сырья и
0,1x1+ 0,3x2 = 0,1⋅20 + 0,3⋅50 = 17 час работы оборудования.
План выпуска допустим, для его выполнения достаточно ресурсов.

5 x1 + 10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,

x1=20, x2= 50

Слайд 14

Решение.
Выручка определяется целевой функцией
Z=40x1+100x2.
Значит,
Z=4010+100100 = 10400 (у.е.).
Пример 3
Для

задачи Примера 1 найти выручку от реализации плана x1=10, x2= 100.

Слайд 15

Самостоятельная работа 2
Задание. В условиях Примера 1 найти выручку от реализации

плана x1=20, x2= 50

Варианты A. 3000 В. 3800
ответов: С. 5800 D. 2900

Z=40x1+100x2

Слайд 16

Сверим ответы?
Выручка определяется целевой функцией:
Z=4020+10050 = 5800 (у.е.).
x1=20, x2= 50
Z=40x1+100x2

Слайд 17

Пример 4
Для задачи Примера 1 найти остаток ресурсов при плане x1=50,

x2= 50.

5 x1 +10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,
x1≥0, x2≥0.

Решение
Для выполнения этого плана потребуется
5x1+10x2 = 5⋅50 +10⋅50 = 750 кг сырья и
0,1x1+ 0,3x2 = 0,1⋅50 + 0,3⋅50 = 20 час работы оборудования.

Остатки ресурсов:
s1= 1000 – 750 = 250
s2 = 25 – 20 = 5

Слайд 18

Самостоятельная работа 3
Задание. В условиях Примера 1 найти остаток ресурсов при

плане x1=30, x2= 70

Варианты A. 150; 3 В. 150; 1
ответов: С. 250; 1 D. 250; 3

5 x1 +10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,
x1≥0, x2≥0.

Слайд 19

Сверим ответы?
Для выполнения этого плана потребуется
5x1+10x2 = 5⋅30 +10⋅70 =

850 кг сырья и
0,1x1+ 0,3x2 = 0,1⋅30 + 0,3⋅70 = 24 час работы оборудования.

x1=30, x2= 70

5 x1 +10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,
x1≥0, x2≥0.

Остатки ресурсов:
s1= 1000 – 850 = 150
s2 = 25 – 24 = 1

Слайд 20

1.2. Определение оптимального плана производства графическим методом
Построим множество допустимых

решений.
Проведем прямые
5 x1+10 x2 = 1000: (x1=0, x2=1000/10=100,
x2=0, x1=1000/5=200.)
0,1 x1+0,3 x2 = 25: (x1=0, x2=25/0,3=250/3=83,3,
x2=0, x1=25/0,1=250).

5 x1 +10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,
x1≥0, x2≥0.

Слайд 21

О 50 100 150 200 250 x1
x2
150
100
50
x1=0, x2=100,
x2=0, x1=200.
5 x1+10

x2 = 1000

Строим прямую

Слайд 22

О 50 100 150 200 250 x1
x2
150
100
50
M
x1=0, x2=83,3,
x2=0, x1=250.
Строим прямую
0,1

x1+0,3 x2 = 25

Слайд 23

О 50 100 150 200 250 x1
x2
150
100
83,3

Строим область допустимых решений D:

Слайд 24

О 50 100 150 Б 200 250 x1
x2
150
100
А
50
M
Z=40x1+100x2=0
по

двум точкам:
(x1=0, x2=0)
и (x1=50, x2=-40⋅50/100=-20).

Для нахождения оптимального решения:
1. Проведем линию уровня

(0;0)

(50;-20)

Координаты точки М определяют оптимальный план выпуска продукции.

2. Перемещаем ее вверх до пересечения с границей допустимой области

Слайд 25

Самостоятельная работа 4
Задание. Область допустимых решений задачи линейного программирования имеет вид:

Тогда максимальное значение функции Z = 2x1 + 2x2 равно: А. 11. В. 13. С. 16. D. 8.

Слайд 26

1.3. Приведение задачи Примера 1 к канонической форме.
Для этого введем

две дополнительные переменные: s1 и s2 (s1 - остаток сырья, s2- остаток времени изготовления).
Тогда получим каноническую форму задачи: найти план x1, x2, s1, s2 , который дает максимальную выручку
Z=40⋅x1+100⋅x2+0⋅s1+0⋅s2
при ограничениях:

Z=40x1+100x2

5 x1 +10 x2 ≤ 1000,
0,1 x1 + 0,3 x2 ≤ 25,
x1≥0, x2≥0.

(1)

(2)

Слайд 27

Ограничения (2) образуют систему двух уравнений с четырьмя неизвестными.
Среди бесконечного

множества решений этой системы базисные решения получаются следующим образом.
Две переменных приравняем к 0.
Эти переменные назовем свободными.

1.4.Определение всех базисных решений

Слайд 28

Значения остальных переменных получаем из решения системы.
Эти переменные назовем базисными.

Базисное решение называется допустимым, если оно неотрицательно.

Слайд 29

1. Пусть x1, x2 – свободные переменные.
Подставляя значения x1 =

0, x2 = 0
в (2) , получаем систему уравнений:

.
Следовательно, базисное решение имеет вид:
x1 = 0, x2 = 0, s1 = 1 000, s2 = 25.

Z=40x1+100x2

(2)

Слайд 30

Базисное решение означает,
что первой и второй продукт не производятся.
Это

базисное решение является допустимым
Выручка от реализации этого плана составит
Z = 40 x1 + 100 x2 = 0.

Z=40x1+100x2

x1 = 0, x2 = 0, s1 = 1 000, s2 = 25.

Слайд 31

2. Пусть x1, s1 – свободные переменные.
Подставляя значения x1 = 0,

s1 = 0 в (2), получаем систему

Следовательно, базисное решение имеет вид

x1 = 0, x2 = 100, s1 = 0, s2 = -5.

(2)

Слайд 32

Это базисное решение означает,
что первый продукт не производится,
второго продукта

производится 100.
Сырье полностью используется в производстве,
Для производства не хватает
5 часов работы оборудования.
Это базисное решение не является допустимым.

x1 = 0, x2 = 100, s1 = 0, s2 = -5.

Слайд 33

3. Пусть x1, s2 - свободные переменные.
Подставляя значения x1=0, s2=0 в

(2) ,
получаем систему

(2)

Следовательно, базисное решение имеет вид

x1 = 0, x2 = 250/3 = 83 1/3, s1 = 166 2/3, s2 = 0.

Слайд 34

Это базисное решение означает,
что первый продукт не производится,
второго продукта

производится 83 1/3.
Сырье не полностью используется в производстве
и его остаток составляет 166 2/3 кг.
Время работы оборудования полностью используется в производстве.
Это базисное решение является допустимым.
Выручка от реализации этого плана составит

= 10433 1/3.

Z=40x1+100x2

x1 = 0, x2 = 250/3 = 83 1/3, s1 = 166 2/3, s2 = 0.

Слайд 35

4. Пусть x2, s1 - свободные переменные.
Подставляя значения x2 =

0, s1 = 0 в (2),
получаем систему

Следовательно, базисное решение имеет вид

x1 = 0, x2 = 250/3 = 83 1/3, s1 = 166 2/3, s2 = 0.

(2)

Слайд 36

Базисное решение означает,
что первого продукта производится 200,
второй продукт не

производится.
Сырье полностью используется в производстве.
Время обработки не полностью используется в производстве.
Это базисное решение является допустимым.
Выручка от реализации этого плана составит

x1 = 0, x2 = 250/3 = 83 1/3, s1 = 166 2/3, s2 = 0.

Z=40x1+100x2

= 8000.

Слайд 37

5. Пусть x2, s2 – свободные переменные.
Подставляя значения x2 =

0, s2 = 0 в (2),
получаем систему

(2)

Следовательно, базисное решение имеет вид

x1=250, x2= 0, s1 =-250, s2 =0.

Слайд 38

Это базисное решение означает,
что первого продукта производится 250,
второй продукт

не производится.
Не хватает для производства 250 кг сырья,
Время работы оборудования используется полностью.
Это базисное решение не является допустимым.

x1=250, x2= 0, s1 =-250, s2 =0.

Слайд 39

6. Пусть s1, s2 – свободные переменные.
Тогда базисные переменные x1

и x2
найдем из системы уравнений

(2)

Отсюда следует, что базисное решение имеет вид

x1=100, x2=50, s1 =0, s2 =0.

Слайд 40

x1=100, x2=50, s1 =0, s2 =0.
Это базисное решение означает,
что первого

продукта производится 100,
второго продукта производится 50.
Сырье и время работы оборудования используются полностью.
Это базисное решение является допустимым.
Выручка от реализации этого плана составит

Z=40x1+100x2

Z = 40∙100 + 130∙50 = 10500.

Слайд 41

Максимальное значение выручки достигается на четвертом базисном решении в этой таблице
X*={

x1=10; x2=50; S1=0; S2=0 }

Слайд 42

2.3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

Слайд 43

Построение симплекс-таблицы для Примера
Получили план:
X (0) ={x1=0, x2=0, s1=1000,

s2=25}.

Таблица 2

Слайд 44

Анализ оптимальной симплекс-таблицы
1.Значения второго столбца определяют значения БП: x1 =100; x2

=50.
Все переменные, не входящие в первый столбец, являются свободными и равны 0: s1 =0, s2 =0.

Слайд 45

Анализ оптимальной симплекс-таблицы
Базисное решение прямой задачи:
Х2 = {x1=100; x2 = 50;

S1 = 0; S2 = 0}

Слайд 46

Анализ оптимальной симплекс-таблицы
2. В последней строке определяются:
значение ЦФ прямой задачи

Z=9000;
значения 0 в столбцах x1 и x2 означают, что производства первого и второго продуктов рентабельны: Δ1=0, Δ2=0.
(при положительных Δ производство нерентабельно)

Слайд 47

Самостоятельная работа
Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции)

имеет вид:

Тогда оптимальный план выпуска продукции равен:
А. x1 = 0; x2 = 2. В. x1 = 6; x4 =6.
С. x3 = 1,25; x2 = 1. D. x2 = 2; x4 = 6

Слайд 48

Самостоятельная работа
Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции)

имеет вид:

Тогда максимальное значение целевой функции равно
А. 3 В. 6 С. 8 D. 1,25

Слайд 49

1.3.3. Построение двойственной задачи линейного программирования
Двойственная задача ЛП:
Прямая задача
5 x1 +10

x2 = 1000,
0,1 x1 + 0,3 x2 = 25,
Z=40 x1 + 100 x2 + 0 S1 + 0 S2

min

Слайд 50

Анализ оптимальной симплекс-таблицы
Значение 4 в столбце s1 означает, что теневая

цена 1 кг сырья равна 4 : y1 =4;
Значение 200 в столбце s2 означает, что теневая цена работы 1 часа оборудования равна 200: y2 =200.

Слайд 51

2.3. Интервалы устойчивости.
После нахождения оптимального решения
выполняется анализ модели на

чувствительность –
необходимо знать какими будут возможные
изменения решения при изменении параметров
системы.

Слайд 52

Решение задачи в Excel В электронную таблицу внести исходные данные :

Слайд 53

Сервис – Поиск решения

Слайд 54

В Поиске решения –Параметры - Заполнить окно -ОК

Слайд 55

В Поиске решения Выполнить Выделить Устойчивость - ОК

Слайд 56

Математическая оптимизация программирования

Содержание

Лекцию читает к.т.н., доцентБОБРОВА ЛЮДМИЛА ВЛАДИМИРОВНАКафедра информатики и компьютерных технологий

Рекомендуемая литература: 1. Ткаченко, Г. Г., Боброва Л.В. Математика, ч. 2.

Пример 1 Для производства двух видов продукции фирма использует два

Требуется найти план выпуска продукции, который обеспечивает максимальную выручку.Таблица 1

1.1 Построение математической модели Обозначим: x1 – план выпуска продукции

План X = (x1, x2) будет допустимым, если затраты каждого ресурса

Целевой функцией будет общая стоимость реализации плана (выручка) x1, x2:

Итак, необходимо найти план выпуска продукции x1, x2, который обеспечивает

Проверить является ли план x1=10, x2= 100 допустимым.Решение. Найдем затраты

Самостоятельная работа 1Задание. В условиях Примера 1 проверить допустимость плана решения

Сверим ответы?Для выполнения этого плана потребуется 5x1+10x2 = 5⋅20 +10⋅50 =

Решение. Выручка определяется целевой функцией Z=40x1+100x2. Значит,Z=40*10+100*100 = 10400 (у.е.).Пример 3Для

Самостоятельная работа 2Задание. В условиях Примера 1 найти выручку от реализации

Сверим ответы?Выручка определяется целевой функцией:Z=40*20+100*50 = 5800 (у.е.).x1=20, x2= 50 Z=40x1+100x2

Пример 4Для задачи Примера 1 найти остаток ресурсов при плане x1=50,

Самостоятельная работа 3Задание. В условиях Примера 1 найти остаток ресурсов при

Сверим ответы?Для выполнения этого плана потребуется 5x1+10x2 = 5⋅30 +10⋅70 =

1.2. Определение оптимального плана производства графическим методом Построим множество допустимых

О 50 100 150 200 250 x1x215010050x1=0, x2=100,x2=0, x1=200.5 x1+10

О 50 100 150 200 250 x1x215010050Mx1=0, x2=83,3,x2=0, x1=250.Строим прямую0,1

О 50 100 150 200 250 x1 x2 150100 83,3

О 50 100 150 Б 200 250 x1x2150100 А50MZ=40x1+100x2=0 по

Самостоятельная работа 4Задание. Область допустимых решений задачи линейного программирования имеет вид:

1.3. Приведение задачи Примера 1 к канонической форме. Для этого введем

Ограничения (2) образуют систему двух уравнений с четырьмя неизвестными. Среди бесконечного

Значения остальных переменных получаем из решения системы. Эти переменные назовем базисными.

1. Пусть x1, x2 – свободные переменные. Подставляя значения x1 =

Базисное решение означает, что первой и второй продукт не производятся. Это

2. Пусть x1, s1 – свободные переменные.Подставляя значения x1 = 0,

Это базисное решение означает, что первый продукт не производится, второго продукта

3. Пусть x1, s2 - свободные переменные.Подставляя значения x1=0, s2=0 в

Это базисное решение означает, что первый продукт не производится, второго продукта

4. Пусть x2, s1 - свободные переменные. Подставляя значения x2 =

Базисное решение означает, что первого продукта производится 200, второй продукт не

5. Пусть x2, s2 – свободные переменные. Подставляя значения x2 =

Это базисное решение означает, что первого продукта производится 250, второй продукт

6. Пусть s1, s2 – свободные переменные. Тогда базисные переменные x1

x1=100, x2=50, s1 =0, s2 =0.Это базисное решение означает, что первого

Максимальное значение выручки достигается на четвертом базисном решении в этой таблицеX*={

2.3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

Построение симплекс-таблицы для Примера Получили план:X (0) ={x1=0, x2=0, s1=1000,

Анализ оптимальной симплекс-таблицы1.Значения второго столбца определяют значения БП: x1 =100; x2

Анализ оптимальной симплекс-таблицыБазисное решение прямой задачи:Х2 = {x1=100; x2 = 50;

Анализ оптимальной симплекс-таблицы2. В последней строке определяются: значение ЦФ прямой задачи

Самостоятельная работа Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции)

Самостоятельная работа Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции)

1.3.3. Построение двойственной задачи линейного программированияДвойственная задача ЛП:Прямая задача5 x1 +10

Анализ оптимальной симплекс-таблицы Значение 4 в столбце s1 означает, что теневая

2.3. Интервалы устойчивости. После нахождения оптимального решения выполняется анализ модели на

Решение задачи в Excel В электронную таблицу внести исходные данные :

Сервис – Поиск решения

В Поиске решения –Параметры - Заполнить окно -ОК

В Поиске решения Выполнить Выделить Устойчивость - ОК

Отчет по устойчивости решения

Похожие презентации

Лекцию читает
к.т.н., доцент
БОБРОВА
ЛЮДМИЛА ВЛАДИМИРОВНА
Кафедра информатики и компьютерных технологий

Рекомендуемая литература:
1. Ткаченко, Г. Г., Боброва Л.В. Математика, ч. 2.

Пример 1
Для производства двух видов продукции фирма использует два

Требуется найти план выпуска продукции, который обеспечивает максимальную выручку.
Таблица 1

Целевой функцией будет общая стоимость
реализации плана (выручка) x1, x2:

Проверить является ли план x1=10, x2= 100 допустимым.
Решение. Найдем затраты

Самостоятельная работа 1
Задание. В условиях Примера 1 проверить допустимость плана решения

Сверим ответы?
Для выполнения этого плана потребуется
5x1+10x2 = 5⋅20 +10⋅50 =

Решение.
Выручка определяется целевой функцией
Z=40x1+100x2.
Значит,
Z=4010+100100 = 10400 (у.е.).
Пример 3
Для

Самостоятельная работа 2
Задание. В условиях Примера 1 найти выручку от реализации

Сверим ответы?
Выручка определяется целевой функцией:
Z=4020+10050 = 5800 (у.е.).
x1=20, x2= 50
Z=40x1+100x2

Пример 4
Для задачи Примера 1 найти остаток ресурсов при плане x1=50,

Самостоятельная работа 3
Задание. В условиях Примера 1 найти остаток ресурсов при

Сверим ответы?
Для выполнения этого плана потребуется
5x1+10x2 = 5⋅30 +10⋅70 =

1.2. Определение оптимального плана производства графическим методом
Построим множество допустимых

О 50 100 150 200 250 x1
x2
150
100
50
x1=0, x2=100,
x2=0, x1=200.
5 x1+10

О 50 100 150 200 250 x1
x2
150
100
50
M
x1=0, x2=83,3,
x2=0, x1=250.
Строим прямую
0,1

О 50 100 150 200 250 x1
x2
150
100
83,3

О 50 100 150 Б 200 250 x1
x2
150
100
А
50
M
Z=40x1+100x2=0
по

Самостоятельная работа 4
Задание. Область допустимых решений задачи линейного программирования имеет вид:

1.3. Приведение задачи Примера 1 к канонической форме.
Для этого введем

Ограничения (2) образуют систему двух уравнений с четырьмя неизвестными.
Среди бесконечного

Значения остальных переменных получаем из решения системы.
Эти переменные назовем базисными.

1. Пусть x1, x2 – свободные переменные.
Подставляя значения x1 =

Базисное решение означает,
что первой и второй продукт не производятся.
Это

2. Пусть x1, s1 – свободные переменные.
Подставляя значения x1 = 0,

Это базисное решение означает,
что первый продукт не производится,
второго продукта

3. Пусть x1, s2 - свободные переменные.
Подставляя значения x1=0, s2=0 в

Это базисное решение означает,
что первый продукт не производится,
второго продукта

4. Пусть x2, s1 - свободные переменные.
Подставляя значения x2 =

Базисное решение означает,
что первого продукта производится 200,
второй продукт не

5. Пусть x2, s2 – свободные переменные.
Подставляя значения x2 =

Это базисное решение означает,
что первого продукта производится 250,
второй продукт

6. Пусть s1, s2 – свободные переменные.
Тогда базисные переменные x1

x1=100, x2=50, s1 =0, s2 =0.
Это базисное решение означает,
что первого

Максимальное значение выручки достигается на четвертом базисном решении в этой таблице
X*={

Построение симплекс-таблицы для Примера
Получили план:
X (0) ={x1=0, x2=0, s1=1000,

Анализ оптимальной симплекс-таблицы
1.Значения второго столбца определяют значения БП: x1 =100; x2

Анализ оптимальной симплекс-таблицы
Базисное решение прямой задачи:
Х2 = {x1=100; x2 = 50;

Анализ оптимальной симплекс-таблицы
2. В последней строке определяются:
значение ЦФ прямой задачи

Самостоятельная работа
Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции)

Самостоятельная работа
Задание. Оптимальная симплекс-таблица задачи линейного программирования (планирования производства продукции)

1.3.3. Построение двойственной задачи линейного программирования
Двойственная задача ЛП:
Прямая задача
5 x1 +10

Анализ оптимальной симплекс-таблицы
Значение 4 в столбце s1 означает, что теневая

2.3. Интервалы устойчивости.
После нахождения оптимального решения
выполняется анализ модели на