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