Методы оптимальных решений

Июль 25, 2022

Главная
Математика
Методы оптимальных решений

Содержание

2. Майер И. И. Методы оптимальных решений Контрольная работа Контрольная работа. Поток разбивается на бригады по три
3. Майер И. И. Методы оптимальных решений Основные темы дисциплины Основные темы дисциплины Оптимизация – постановка задачи
4. Майер И. И. 1. Оптимизация – постановка задачи
5. Майер И. И. Оптимизация – постановка задачи Оптимизация – раздел теории исследования операций. Это деятельность, направленная
6. Майер И. И. Оптимизация – терминология Операция – любое действие, направленное на достижение конкретной цели Решение
7. Майер И. И. Оптимизация – терминология Показатель эффективности, целевая функция F – разработанный заранее численный критерий
8. Майер И. И. Оптимизация – постановка задачи Чаще всего оптимизационные модели принятия решений записываются как системы
9. Майер И. И. Оптимизация – постановка задачи Полученные на предыдущем слайде выражения: целевой функции F(X)? min
10. Майер И. И. Оптимизация – методы решения К методам решения оптимизационных задач относятся: Метод математического программирования
11. Майер И. И. 2. Линейное программирование. Методы решения К задачам линейного программирования относятся: - Разработка оптимального
12. Майер И. И. 2. Линейное программирование и задача оптимизации. Методы решения
13. Майер И. И. Линейное программирование. Методы решения Методы решения задач линейного программирования относятся к вычислительной математике,
14. Майер И. И. Линейное программирование. Пример 1. Цех производит стулья и столы. На производство стула идет
15. Майер И. И. 3. Продолжение примера 1 х1 –количество стульев, х2 - количество столов Задача оптимизации
16. Майер И. И. Решение примера 1 графическим методом Систему ограничений (2) можно представить в виде выпуклого
17. Майер И. И. Решение примера 1 графическим методом Ограничения по труду 10 Х1 + 15 Х2
18. Майер И. И. Линейное программирование. Продолжение примера 1
19. Майер И. И. Линейное программирование. Продолжение примера 1 Рис. 3 Объединение ограничений рис. 1 и рис.
20. Майер И. И. Вывод Полученное решение примера 1 говорит о том, что максимальную прибыль (2200 денежных
21. Майер И. И. 2. Линейное программирование. Пример 2 Рассмотрим задачу планирования производства: Кооператив по производству строительных
22. Майер И. И. В кооперативе работают 10 человек, по 40 часов в неделю 2. Линейное программирование.
23. Майер И. И. Продолжение примера 2. x1 – объем производимого жидкого стекла в неделю, x2 -
24. Майер И. И. 2.Линейное программирование. Продолжение примера 2 Описание задачи в матричной форме: Вектор переменных Х=(х1,
25. Майер И. И. 2 Линейное программирование. Пример 2. Продолжение Выше (слайд 20) была получена математическая модель
26. Майер И. И. 2. Линейное программирование. Симплекс метод 1. Основной, универсальный метод решения задачи линейного программирования
27. Майер И. И. 2. Линейное программирование. Симплекс метод Основной алгоритм метода: Исходная система при помощи дополнительных
28. Майер И. И. 2. Линейное программирование. Симплекс метод. Пример 3. Словесное и табличное описание задачи Предприятие
29. Майер И. И. Симплекс метод. Продолжение примера 3 Для удобства восприятия система ограничений дана в процентах
30. Майер И. И. Симплекс метод. Продолжение примера 3 Описание задачи после исключения неравенств (3) и (4)
31. Майер И. И. Симплекс метод. Продолжение примера 3 Решение системы (4) – первая итерация Х1 /
32. Майер И. И. Симплекс метод. Пример 3 Вторая итерация Данные на начало второй итерации Х1 /
33. Майер И. И. Симплекс метод. Продолжение примера 3 Х1 + 2/3 Х2 + 2/1,2 Х3 +
34. Майер И. И. Симплекс метод. Продолжение примера 3 Х1 + 9/7 Х3 + 1800/7 Х4 -
35. Майер И. И. Симплекс метод. Пример 4 Предприятие располагает тремя производственными ресурсами – сырьем, оборудованием, электроэнергией
36. Майер И. И. Симплекс метод. Пример 4 Таблица 1
37. Майер И. И. Симплекс метод. Пример 4 Решение: Обозначим: х1-время работы предприятия первым способом; х2- время
38. Майер И. И. Симплекс метод. Пример 4 Симплекс таблица первого шага В индексной строке – два
39. Майер И. И. Симплекс метод. Пример 4 Симплекс таблица второго шага Вектор решения второй итерации Значение
40. Майер И. И. Симплекс метод. Пример 4 Симплекс таблица третьего шага Все оценки свободных переменны x3,
41. Майер И. И. 3. Двойственные задачи
42. Майер И. И. 3. Двойственные задачи и их приложение Каждой задаче ЛП можно определенным образом поставить
43. Майер И. И. 3. Двойственные задачи. Примеры 1. Пример 1 и двойственная к нему задача Прямая
44. Майер И. И. 3. Задача, двойственная к примеру 2 Прямая задача Двойственная задача Алгоритм вычисления параметров
45. Майер И. И. Задача, двойственная к примеру 2 Прямая задача Двойственная задача Решение прямой задачи Решение
46. Майер И. И. 3. Двойственная задача Пример 3. Прямая задача: найти минимум целевой функции F =
47. Майер И. И. 4. Транспортная задача 4.1 Формулировка задачи 4.2.Примеры. Описание
48. Майер И. И. 4. Транспортная задача Транспортная задача – одна из задач линейного программирования. Ее цель
49. Майер И. И. 4. Транспортная задача. Постановка задачи. Пример 5 Товар хранится на трех складах, его
50. Майер И. И. 4. Транспортная задача. Пример 5.Продолжение 12 переменных xij удовлетворяют двум группам ограничений: По
52. Скачать презентацию

Слайд 2

Майер И. И.
Методы оптимальных решений Контрольная работа
Контрольная работа.
Поток разбивается на

бригады по три человека
Цель контрольной работы - постановка задач оптимизации.
В отчете следует сформулировать и описать
задачу линейного программирования
транспортную задачу.

Слайд 3

Майер И. И.
Методы оптимальных решений Основные темы дисциплины
Основные темы дисциплины
Оптимизация – постановка

задачи
Линейное программирование и задача оптимизации. Методы решения
Двойственные задачи. Применение в экономических приложениях
Транспортная задача
Нелинейная оптимизация – постановка задачи

Слайд 4

Майер И. И.
1. Оптимизация – постановка задачи

Слайд 5

Майер И. И.
Оптимизация – постановка задачи
Оптимизация – раздел теории исследования операций.

Это деятельность, направленная на получение наилучших результатов при соответствующих условиях.
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, (количество продукции и расход сырья; количество и качество продукции).
Выбор компромиссного варианта является решением оптимизационной задачи.
При постановке задачи оптимизации необходимо:
1).Наличие объекта и цели оптимизации;
2). Наличие ресурсов оптимизации, т.е. возможность выбора значений некоторых параметров оптимизируемого объекта;
3). Возможность количественной оценки оптимизируемой величины, так как только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
4). Учет ограничений.

Слайд 6

Майер И. И.
Оптимизация – терминология
Операция – любое действие, направленное на
достижение

конкретной цели
Решение - любой набор всех необходимых
параметров операции
Оптимальное решение – решение, которое
согласно последующей оценке, предпочтительнее
других.

Слайд 7

Майер И. И.
Оптимизация – терминология
Показатель эффективности, целевая функция F –
разработанный

заранее численный критерий оценки,
позволяющий сравнивать между собой различные варианты
решения задачи
На любую операцию воздействуют два вида факторов:
Известные, заданные факторы (параметры) a1, a2, …an
Подлежащие определению элементы решения x1, …xn
В этом случае целевая функция F зависит от каждого вида,
может быть записана
F(a1,a2..an;x1,x2,…xn) -? max
или
F(a1,a2..an;x1,x2,…xn) -? min

Слайд 8

Майер И. И.
Оптимизация – постановка задачи
Чаще всего оптимизационные модели принятия решений

записываются как системы ограничений на регулируемую
многомерную переменную Х и сформулированную целевую
функцию F (X) . Формулировка задачи
Целевая функция F(X)? min (или F(X)? max) (1)
Система ограничений Аx<=B (2)
В (1) и (2): X – вектор независимых переменных
А – матрица коэффициентов системы
B – вектор ограничений
Если и ограничения системы (2), и целевая функция (1)
линейны, то задача решается методами линейного
программирования
Управляющий параметр Х может иметь различную природу –
число, вектор, множество и т.п. Задача менеджера –
оптимизировать целевую функцию F (X), выбрав
управляющий параметр Х, соответствующий системе
ограничений (2)

Слайд 9

Майер И. И.
Оптимизация – постановка задачи
Полученные на предыдущем слайде выражения:
целевой

функции F(X)? min (F(X)? max) (1)
и системы ограничений Аx<=B (2)
могут быть записаны в матричной форме.
(1)
(2)

Слайд 10

Майер И. И.
Оптимизация – методы решения
К методам решения оптимизационных задач относятся:
Метод

математического программирования
Методы линейного программирования
Методы нелинейного программирования
Метод целочисленного программирования и др.
Широкое применение получил метод линейного
программирования. Основной особенностью задачи
линейного программирования является то, что как
ограничения (системы линейных неравенств или равенств),
так и целевая функция линейны.
Впервые задачи ЛП решались советским математиком
Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи
производственного менеджмента с целью оптимизации
организации производства и производственных процессов.
Впоследствии аналогичными задачами занялся Т. Купманс США).
Л.В. Канторович и Т. Купманс были награждены Нобелевскими
премиями по экономике.

Слайд 11

Майер И. И.
2. Линейное программирование. Методы решения
К задачам линейного программирования относятся:
-

Разработка оптимального плана производства;
- Задачи оптимального смешения – однопродуктовые и
многопродуктовые;
Задачи оптимального раскроя и др.
В зависимости от размерности управляющего параметра Х
(числа независимых переменных) задачу решают
графическим или аналитическим путем.
В случае двух независимых переменных задачу можно
решить графическим методом.
В случае, когда количество переменных больше двух,
применяют различные методы, такие, как симплекс метод
или метод двойственности

Слайд 12

Майер И. И.
2. Линейное программирование и задача оптимизации. Методы решения

Слайд 13

Майер И. И.
Линейное программирование. Методы решения
Методы решения задач линейного

программирования
относятся к вычислительной математике, а не к экономике и
менеджменту. Уметь пользоваться этим инструментом
должен любой менеджер или инженер. Существуют
программы, (Excel), позволяющие автоматизировать решение
этой задачи.
Методы решения задачи линейного программирования
1.Простой перебор. Метод графического решения задачи.
Строится многоугольник области допустимых решений, в
узлах этого прямоугольника вычисляется значение целевой
функции, находятся координаты оптимального решения.
Применим для задач с двумя управляющими параметрами
2. Направленный перебор. Строится линия целевой функции,
которая переносится параллельно самой себе в направлении
роста целевой функции. Находится вершина решения
3. Симплекс метод

Слайд 14

Майер И. И.
Линейное программирование. Пример 1.
Цех производит стулья и столы.

На производство стула идет 5 единиц
материала, на производство стола - 20 единиц. Стул требует 10
человеко-часов, стол - 15. Имеется 400 единиц материала и 450
человеко-часов. Прибыль при производстве стула – 45 руб. , при
производстве стола - 80 руб. Определить объем производимой
продукции, дающий максимальную прибыль, израсходовав при этом
весь материал.
Обозначим: Х1 - число изготовленных стульев, Х2 – количество
изготовленных столов. Опишем задачу в табличной форме
Таблица 1

Слайд 15

Майер И. И.
3. Продолжение примера 1
х1 –количество стульев, х2 -

количество столов
Задача оптимизации (целевая функция) и ограничения задачи
(допустимое множество Х) имеет вид
Целевая функция F(x1,x2) = 45 Х1 + 80 Х2 → max , (1)
Ограничения задачи 5 Х1 + 20 Х2 ≤ 400
10 Х1 + 15 Х2 ≤ 450 (2)
Х1 ≥ 0
Х2 ≥ 0

Слайд 16

Майер И. И.
Решение примера 1 графическим методом
Систему ограничений (2) можно представить

в виде выпуклого
многоугольника. F(x1,x2) = 45 Х1 + 80 Х2 ? max ,
5 Х1 + 20 Х2 ≤ 400
10 Х1 + 15 Х2 ≤ 450 (2)
Х1 ≥ 0 ; Х2 ≥ 0
Ограничения по материалу 5 Х1 + 20 Х2 ≤ 400 и Х1 ≥ 0 , Х2 ≥ 0,
можно представить в виде треугольника рис.1 ;
Рис. 1. Ограничения по материалу
Прямая пересекает ось Х1 (стулья) в точке (80,0), пересекает ось Х2 в
точке (0, 30). Это означает, что если весь материал пустить на
изготовление стульев, то будет изготовлено 80 стульев, если на
столы – то будет изготовлено 30 столов.

Слайд 17

Майер И. И.
Решение примера 1 графическим методом
Ограничения по труду 10 Х1

+ 15 Х2 ≤ 450 и Х1 ≥ 0 , Х2 ≥ 0 можно
представить в виде треугольника рис. 2.
Совмещение рис.1 и рис.2 дает рис.3, всю область допустимых
решений (выпуклый многоугольник допустимых решений)

Слайд 18

Майер И. И.
Линейное программирование. Продолжение примера 1

Слайд 19

Майер И. И.
Линейное программирование. Продолжение примера 1
Рис. 3
Объединение ограничений рис. 1

и рис. 2 приводит к образованию
совместной системы ограничений и формированию области допустимых
решений. Графически эта область представляет выпуклый многоугольник
(рис.3) с соответствующими координатами вершин. Максимальное значение
целевой функции для этой задачи можно найти методом простого перебора,
вычислив значение целевой функции F(x1,x2) = 45 Х1 + 80Х2 в узлах
выпуклого многоугольника или по градиентному методу поиска.
Решение задачи: максимум целевой функции достигается в точке (24, 14) и
равен 2200 денежных единиц.

Слайд 20

Майер И. И.
Вывод
Полученное решение примера 1 говорит о том, что
максимальную

прибыль (2200 денежных единиц) цех по
производству столов и стульев получит при производстве
24 стульев и 14 столов.

Слайд 21

Майер И. И.
2. Линейное программирование. Пример 2
Рассмотрим задачу планирования производства:
Кооператив по

производству строительных материалов выпускает
жидкое стекло и пенопласт.
Трудозатраты на производство 1 т. стекла -20 ч., 1 т. пенопласта -
10 ч.
Оборудование позволяет производить не более 15 т. стекла и 30 т.
пенопласта в неделю.
Прибыль от реализации 1 т. стекла - 50 р., 1 т. пенопласта – 40 р.
В кооперативе работают 10 рабочих, по 40 часов в неделю.
Сколько материалов каждого вида следует выпускать для
получения максимальной прибыли.
Приведем математическую модель задачи. Для этого обозначим
переменные задачи:
x1 – объем производимого стекла в неделю,
x2 - объем производимого пенопласта в неделю.

Слайд 22

Майер И. И.
В кооперативе работают 10 человек, по 40 часов в

неделю

2. Линейное программирование. Продолжение примера 2
Запишем условие задачи в виде таблицы
x1 – объем производимого жидкого стекла в неделю,
x2 - объем производимого пенопласта в неделю
F – целевая функция
Система ограничений

Слайд 23

Майер И. И.
Продолжение примера 2. x1 – объем производимого жидкого
стекла

в неделю, x2 - объем производимого пенопласта в неделю
F – целевая функция
Система ограничений

Слайд 24

Майер И. И.
2.Линейное программирование. Продолжение примера 2
Описание задачи в матричной форме:

Вектор переменных Х=(х1, х2)
Вектор коэффициентов целевой функции С=(с1, с2) = (50,40)
Вектор ограничений В=(в1,в2,в3)=( 400,15,30)
Матрица ограничений
Описание задачи в матричной форме:
F=C∙Xt ?max
A∙Xt ≤B
Xj>=0

Слайд 25

Майер И. И.
2 Линейное программирование. Пример 2. Продолжение
Выше (слайд 20) была

получена математическая модель примера 2
(1)
(2)
Найденное графическим методом оптимальное решение равно
Х=(х1, х2)= (5, 30 ), значение целевой функции, максимальная
прибыль от реализации 5 тонн жидкого стекла и 30 тонн пенопласта
равна F = 50х1 + 40х2 = 1450 условных денежных единиц

Слайд 26

Майер И. И.
2. Линейное программирование. Симплекс метод
1. Основной, универсальный метод решения

задачи
линейного программирования
2. Один из первых специализированных методов решения
задач линейного программирования. Предложен американцем
Г. Данцигом в 1951 г.
3. Основной алгоритм реализации метода: продвижение по
выпуклому многограннику ограничений от вершины к
вершине, при котором на каждом шаге значение целевой
функции улучшается до тех пор, пока не будет достигнут
оптимум.
В соответствии с методом, переход от одного
допустимого базисного решения к другому приводит к
тому, что значения целевой функции непрерывно
стремится к оптимальному .
Оптимальное решение находится за конечное число шагов.

Слайд 27

Майер И. И.
2. Линейное программирование. Симплекс метод
Основной алгоритм метода:
Исходная система при

помощи дополнительных переменных приводится в каноническую форму
Выбираются базисные переменные, свободные переменные пересчитываются через базисные, пересчитывается целевая функция.
Для следующей итерации выбирают разрешающую переменную, пересчитывают матрицу А, определяют новый базис
Пункты 2) и 3) повторяют до достижения оптимального значения целевой функции

Слайд 28

Майер И. И.
2. Линейное программирование. Симплекс метод.
Пример 3. Словесное и

табличное описание задачи
Предприятие может выпускать автоматические кухни, кофеварки и
самовары. Данные о производственных мощностях (в штуках
изделий) приведены в табл. 2. Штамповка и отделка проводятся на
одном и том же оборудовании, а сборка проводится на отдельных
участках
Таблица 2

Слайд 29

Майер И. И.
Симплекс метод. Продолжение примера 3
Для удобства восприятия система ограничений

дана в процентах и задача
линейного программирования имеет вид
Система ограничений
Х1  ≥ 0 , Х2 ≥ 0 , Х3 ≥ 0 , (0) {стандартные ограничения}
Х1  / 200 + Х2 / 300 + Х3 / 120 ≤ 100 , (1) {ограничение по штамповке}
Х1  / 300 + Х2 / 100 + Х3 / 100 ≤ 100 , (2) {ограничение по отделке}
Х1 / 200 ≤ 100 , (3) {ограничение по сборке для кухонь, вытекает из 1, можно исключить}
Х2 / 120 ≤ 100 , (4) {ограничение по сборке для кофеварок, из 2, можно исключить}
Х3 / 80 ≤ 100 , (5) {ограничение по сборке для самоваров}
Целевая функция
F = 15 Х1 + 12 Х2 + 14 Х3 → max .

Слайд 30

Майер И. И.
Симплекс метод. Продолжение примера 3
Описание задачи после исключения неравенств

(3) и (4)
F = 15 Х1 + 12 Х2 + 14 Х3 → max .
Х1  / 200 + Х2 / 300 + Х3 / 120 ≤ 100 (1),
Х1  / 300 + Х2 / 100 + Х3 / 100 ≤ 100 (2),
Х3 / 80 ≤ 100 (5)
Вводом трех новых переменных система неравенств приводится в систему
равенств. В результате получена система уравнений (4) с тремя уравнениями
и шестью неизвестными. Система решается путем последовательного
перебора базовых переменных, который приводит к росту целевой функции
Система ограничений
Х1  / 200 + Х2 / 300 + Х3 / 120 + Х4 = 100
Х1  / 300 + Х2 / 100 + Х3 / 100 + Х5 = 100 (4)
Х3 / 80 + Х6 = 100
Х1  ≥ 0 , Х2 ≥ 0 , Х3 ≥ 0, Х4  ≥ 0 , Х5 ≥ 0 , Х6 ≥ 0,
Целевая функция
F = 15 Х1 + 12 Х2 + 14 Х3 → max

Слайд 31

Майер И. И.
Симплекс метод. Продолжение примера 3
Решение системы (4) – первая

итерация
Х1 / 200 + Х2 / 300 + Х3 / 120 + Х4 = 100
Х1 / 300 + Х2 / 100 + Х3 / 100 + Х5 = 100 (4)
Х3 / 80 + Х6 = 100
15 Х1 + 12 Х2 + 14 Х3 = F
В данную систему переменные Х4 , Х5 , Х6 входят только в одно
из уравнений с коэффициентом 1 и они являются базисными
(балансовые переменные).
Свободные переменные Х1 , Х2 , , Х3 можно приравнять любой
константе, в том числе – нулю.
Тогда первое допустимое решение (0,0,0,100, 100, 100) , значение
целевой функции F =0.
Дальнейшая система пересчетов сводится к переводу одной из
свободных переменных в базис и с выводом одной из базисных
переменных и переводом ее в свободные переменные.

Слайд 32

Майер И. И.
Симплекс метод. Пример 3 Вторая итерация
Данные на начало второй

итерации
Х1 / 200 + Х2 / 300 + Х3 / 120 + Х4 = 100
Х1 / 300 + Х2 / 100 + Х3 / 100 + Х5 = 100 (4)
Х3 / 80 + Х6 = 100
Х = (0,0,0,100, 100, 100)
F = 15 Х1 + 12 Х2 + 14 Х3 =0
1. В качестве новой базисной переменной выбираем Х1 –
переменную с наибольшим положительным коэффициентом в F .
2. Сравниваем частные от деления свободных членов на
коэффициенты при выбранной базисной переменной Х1 .
Получаем 100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞.
Выбираем в системе строку, которой соответствует минимальное из
отношений. Это – первая строка. После ряда преобразований над
системой (4) получаем новую систему (4.1)

Слайд 33

Майер И. И.
Симплекс метод. Продолжение примера 3
Х1 + 2/3 Х2 + 2/1,2 Х3

+ 200 Х4 = 20000
7/900 Х2 + 4/900 Х3 - 2/3 Х4 + Х5 = 100/3, (4.1)
Х3 / 80 + Х6 = 100
2 Х2 - 11 Х3 - 3000 Х4 = F – 300000
В новой системе базисными являются Х1 , Х5 , Х6 , свободными - Х2,
Х3 Х4.. Второе допустимое решение (20000,0,0,0,100/3, 100)
Значение F = 300000.
Симплекс метод – третья итерация
Наименьший положительный коэффициент в целевой функции – при
Х2, выбираем Х2 базисной переменной. Проводя аналогичные
действия, образуем частные от деления свободных членов на
коэффициенты при Х2 , получаем
20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.
В качестве разрешающей выбираем вторую строку и после ряда
преобразований и пересчетов получаем систему (4.2)) и новую
целевую функцию

Слайд 34

Майер И. И.
Симплекс метод. Продолжение примера 3
Х1 + 9/7 Х3 + 1800/7 Х4

- 600/7 Х5 = 120000/7
Х2 + 4/7 Х3 - 600/7 Х4 + 900/7 Х5 = 30000/7 (4.2)
Х3 / 80 + Х6 = 100
- 85/7 Х3 - 19800/7 Х4 - 1800/7 Х5 = F – 308571
Из (4.2) следует, что базисными переменными являются:
Х1 =120000/7 , Х2 = 30000/7 , Х6 = 100 , F = 308571.
Так как в строке - 85/7 Х3 - 19800/7 Х4 - 1800/7 Х5 = F – 308571
не осталось ни одного положительного коэффициента, то
оптимальный план найден и производственная программа такая:
Кухни - 120000/7 = 17143
Кофемолки - 30000/7 = 4286
Самовары – 0
Максимальная прибыль – 308571 усл. ден. ед.
Все производственное оборудование будет задействовано за
исключением линии по сборке самоваров

Слайд 35

Майер И. И.
Симплекс метод. Пример 4
Предприятие располагает тремя производственными
ресурсами –

сырьем, оборудованием, электроэнергией –
и производит продукцию двумя способами:
- первый способ: предприятие выпускает 3000 изделий/мес.,
- второй способ: предприятие выпускает 4000 изделий/мес.
Расход ресурсов и амортизация оборудования за один месяц
и общий ресурс при каждом способе производства дан в
таблице 1 (в ден. ед.).
Требуется определить:
Сколько месяцев должно работать предприятие каждым
из способов, чтобы при наличных ресурсах обеспечить
максимальный выпуск продукции.
Табличное описание задачи приведено на следующем слайде.

Слайд 36

Майер И. И.
Симплекс метод. Пример 4
Таблица 1

Слайд 37

Майер И. И.
Симплекс метод. Пример 4
Решение: Обозначим: х1-время работы предприятия первым

способом; х2- время работы предприятия вторым способом.
Целевая функция F(x1, x2) =3∙x1+4∙x2 → max
при ограничениях Каноническая форма записи
Задача решается методом пошагового улучшения путем заполнения
соответствующих симплекс- таблиц .
Решение приведено на следующих слайдах

Слайд 38

Майер И. И.
Симплекс метод. Пример 4
Симплекс таблица первого шага
В индексной строке

– два отрицательных элемента. Ключевым
является второй столбец, по максимуму Abs(∆j ).
Ключевую строку выбираем по min (bi /ai,2) = min(4/2;3/1;8/1).
Ключевая строка вторая, ключевой элемент a1,2=2.
Выводим из базы X3 , вводим в базу X2. Производим перерасчет.
Симплекс таблица второго шага представлена на слайде 35

Слайд 39

Майер И. И.
Симплекс метод. Пример 4
Симплекс таблица второго шага
Вектор решения второй

итерации
Значение целевой функции F(x1,.. x5)= 4∙x2 =8
В индексной строке один отрицательный элемент. Ключевой столбец – первый.
Ключевую строку выбираем по min (bi /ai,1) = min(4, 2,6). Ключевая строка – вторая. Вводим в базис x1, выводим из базиса x4. Симплекс таблица третьего шага представлена на следующем слайде.

Слайд 40

Майер И. И.
Симплекс метод. Пример 4
Симплекс таблица третьего шага
Все оценки свободных

переменны x3, x4, x5 неотрицательны,
следовательно оптимальное решение найдено
Здесь x1 – время работы ( в месяцах) первым способом, x2 –
время работы вторым способом.

Слайд 41

Майер И. И.
3. Двойственные задачи

Слайд 42

Майер И. И.
3. Двойственные задачи и их приложение
Каждой задаче ЛП можно

определенным образом поставить в
соответствии другую задачу ЛП, которую называют
двойственной по отношению к исходной.
В двойственной задаче по сравнению с исходной задачей
строки матрицы ограничений переходят в столбцы,
неравенства целевой функции меняют знак, вместо
максимума ищется минимум (или вместо минимума –
максимум). Двойственную задачу чаще всего применяют
с целью уменьшить количество искомых переменных.
Алгоритм вычисления параметров двойственной задачи:
Матрица ограничений двойственной задачи равна Аt исходной
Целевая функция F* =Bt.Y
Для решения двойственной задачи можно применить графический метод решения или симплекс-метод
Доказано, что оптимальные значения целевых функций в
исходной и двойственной задачах совпадают (т.е. максимум в
исходной задаче совпадает с минимумом в двойственной).

Слайд 43

Майер И. И.
3. Двойственные задачи. Примеры
1. Пример 1 и двойственная к

нему задача
Прямая задача Двойственная задача
Целевая функция Целевая функция
F = 45Х1 + 80 Х2 → max , F= 400 y1 + 450 y2 → min ,
5 Х1 + 20 Х2 ≤ 400 , 5 y1 + 10 y2 ≥ 45,
10 Х1 + 15 Х2 ≤ 450 , 20 y1 + 15 y2 ≥ 80,
Х1 ≥ 0 , Х2 ≥ 0 . y1 ≥ 0, y2 ≥ 0.
Очевидно, что:
1. Матрица ограничений двойственной задачи равна
транспонированной матрице исходной ,
Адвойств.зад.= Аtисходной зад.
2. Целевая функция двойственной задачи равна F*двойств. =Bt.Y
3. Направление оптимизации меняется на противоположное
Fпрямая → max Fдвойств.. → min
или
Fпрямая → min Fдвойств. . → max

Слайд 44

Майер И. И.
3. Задача, двойственная к примеру 2
Прямая задача

Двойственная задача
Алгоритм вычисления параметров двойственной задачи:
Матрица ограничений двойственной задачи задачи равна Аt исходной
Целевая функция F* =Bt.Y
Для решения двойственной задачи можно применить графический метод решения или симплекс-метод

Слайд 45

Майер И. И.
Задача, двойственная к примеру 2
Прямая задача Двойственная

задача
Решение прямой задачи Решение двойственной задачи:
(см. на слайдах 20, 21) Задачу можно решить методом
простого перебора вершин много-
гранника ограничений
Оптимальное решение Оптимальное решение
x1=5; x2=30;F=1450 y1=2.5 ; y2=0; y3=15; F=1450
Двойственные оценки показывают на какую величину возрастает
прибыль, если ресурс увеличивается на единицу. В нашем случае
дополнительный час рабочего времени приносит 2.5 рубля прибыли,
а увеличение производственной мощности по пенопласту на 1 т.
приводит к увеличению прибыли на 15 руб.

Слайд 46

Майер И. И.
3. Двойственная задача
Пример 3. Прямая задача: найти минимум целевой

функции
F = 10x2 - 3x3 ? min при ограничениях
Двойственная задача
F* = y1+3y2 ? max при ограничениях
y1>=0 ; y2 >=0
Графическое решение обратной задачи: max F* = F*(2,4) = 14
Следовательно, минимум исходной задачи равен 14

Слайд 47

Майер И. И.
4. Транспортная задача
4.1 Формулировка задачи
4.2.Примеры. Описание

Слайд 48

Майер И. И.
4. Транспортная задача
Транспортная задача – одна из задач линейного

программирования.
Ее цель – разработка наиболее рациональных путей и способов
транспортировки товаров, устранения чрезмерно дальних,
встречных, повторных перевозок.
Разработка рациональных способов транспортировки товаров
позволяет сокращать время перевозок, расходы транспортировок,
приводит к своевременной реализации потребностей потребителя.
В зависимости от соотношения между суммарными запасами и
суммарными потребностями транспортные задачи могут быть
закрытыми и открытыми.
Если сумма запасов груза равна суммарной потребности в
нем, то задача - закрытая , в противном случае – открытая.
Математическая модель закрытой транспортной задачи –
минимизация целевой функции при заданных тарифах на
перевозки
Количество переменных и ограничений в транспортной задаче
таково, что ее следует решать с применением современных
программных продуктов. В учебных задачах небольшого размера
можно использовать метод потенциалов

Слайд 49

Майер И. И.
4. Транспортная задача. Постановка задачи. Пример 5
Товар хранится на

трех складах, его необходимо перевезти четырем
потребителям. Даны запасы товара на каждом складе, потребности
каждого потребителя и стоимость перевозки единицы товара от i-го
склада к j-му потребителю. Данные задачи приведены в таблице 3.
Таблица 3.
Необходимо спланировать перевозки, т.е. определить объемы
поставок товара Хij со склада i потребителю j , где i = 1,2,3;
j = 1,2,3,4. Очевидно, необходимо определить 12 переменных Хij

Слайд 50

Майер И. И.
4. Транспортная задача. Пример 5.Продолжение
12 переменных xij удовлетворяют двум

группам ограничений:
По запасам на складах: По ограничениям на потребление
X11 + Х12 + Х13 + Х14 = 60 , X11 + Х21 + Х31 = 50
X21 + Х22 + Х23 + Х24 = 80 , X12 + Х22 + Х32 = 40 ,
X31 + Х32 + Х33 + Х34 = 60 . X13 + Х23 + Х33 = 70 ,
X14 + Х24 + Х34 = 40
и все xij >=0
В данной задаче 7 ограничений типа равенств и 12 неравенств.
Целевая функция - издержки по перевозке, которые необходимо
минимизировать:
F = 2 X11 + 5 Х12 + 4 Х13 + 5 Х14 + X21 + 2 Х22 + Х23 + 4 Х24 +
3 X31 + Х32 + 5 Х33 + 2 Х34 → min .

Методы оптимальных решений

Содержание

Майер И. И.Методы оптимальных решений Контрольная работаКонтрольная работа. Поток разбивается на

Майер И. И.Методы оптимальных решений Основные темы дисциплиныОсновные темы дисциплиныОптимизация – постановка

Майер И. И.1. Оптимизация – постановка задачи

Майер И. И.Оптимизация – постановка задачиОптимизация – раздел теории исследования операций.

Майер И. И.Оптимизация – терминологияОперация – любое действие, направленное на достижение

Майер И. И.Оптимизация – терминологияПоказатель эффективности, целевая функция F – разработанный

Майер И. И.Оптимизация – постановка задачиЧаще всего оптимизационные модели принятия решений

Майер И. И.Оптимизация – постановка задачиПолученные на предыдущем слайде выражения: целевой

Майер И. И.Оптимизация – методы решенияК методам решения оптимизационных задач относятся:Метод

Майер И. И.2. Линейное программирование. Методы решенияК задачам линейного программирования относятся:-

Майер И. И.2. Линейное программирование и задача оптимизации. Методы решения

Майер И. И.Линейное программирование. Методы решения Методы решения задач линейного

Майер И. И.Линейное программирование. Пример 1. Цех производит стулья и столы.

Майер И. И.3. Продолжение примера 1 х1 –количество стульев, х2 -

Майер И. И.Решение примера 1 графическим методомСистему ограничений (2) можно представить

Майер И. И.Решение примера 1 графическим методомОграничения по труду 10 Х1

Майер И. И.Линейное программирование. Продолжение примера 1

Майер И. И.Линейное программирование. Продолжение примера 1Рис. 3Объединение ограничений рис. 1

Майер И. И.ВыводПолученное решение примера 1 говорит о том, что максимальную

Майер И. И.2. Линейное программирование. Пример 2Рассмотрим задачу планирования производства:Кооператив по

Майер И. И.В кооперативе работают 10 человек, по 40 часов в

Майер И. И.Продолжение примера 2. x1 – объем производимого жидкого стекла

Майер И. И.2.Линейное программирование. Продолжение примера 2Описание задачи в матричной форме:

Майер И. И.2 Линейное программирование. Пример 2. ПродолжениеВыше (слайд 20) была

Майер И. И.2. Линейное программирование. Симплекс метод1. Основной, универсальный метод решения

Майер И. И.2. Линейное программирование. Симплекс методОсновной алгоритм метода:Исходная система при

Майер И. И.2. Линейное программирование. Симплекс метод. Пример 3. Словесное и

Майер И. И.Симплекс метод. Продолжение примера 3Для удобства восприятия система ограничений

Майер И. И.Симплекс метод. Продолжение примера 3Описание задачи после исключения неравенств

Майер И. И.Симплекс метод. Продолжение примера 3Решение системы (4) – первая

Майер И. И.Симплекс метод. Пример 3 Вторая итерацияДанные на начало второй

Майер И. И.Симплекс метод. Продолжение примера 3Х1 + 2/3 Х2 + 2/1,2 Х3

Майер И. И.Симплекс метод. Продолжение примера 3Х1 + 9/7 Х3 + 1800/7 Х4

Майер И. И.Симплекс метод. Пример 4Предприятие располагает тремя производственными ресурсами –

Майер И. И.Симплекс метод. Пример 4 Таблица 1

Майер И. И.Симплекс метод. Пример 4Решение: Обозначим: х1-время работы предприятия первым

Майер И. И.Симплекс метод. Пример 4Симплекс таблица первого шагаВ индексной строке

Майер И. И.Симплекс метод. Пример 4Симплекс таблица второго шагаВектор решения второй

Майер И. И.Симплекс метод. Пример 4Симплекс таблица третьего шагаВсе оценки свободных

Майер И. И.3. Двойственные задачи

Майер И. И.3. Двойственные задачи и их приложениеКаждой задаче ЛП можно

Майер И. И.3. Двойственные задачи. Примеры1. Пример 1 и двойственная к

Майер И. И.3. Задача, двойственная к примеру 2 Прямая задача

Майер И. И.Задача, двойственная к примеру 2 Прямая задача Двойственная

Майер И. И.3. Двойственная задачаПример 3. Прямая задача: найти минимум целевой

Майер И. И.4. Транспортная задача4.1 Формулировка задачи4.2.Примеры. Описание

Майер И. И.4. Транспортная задачаТранспортная задача – одна из задач линейного

Майер И. И.4. Транспортная задача. Постановка задачи. Пример 5Товар хранится на

Майер И. И.4. Транспортная задача. Пример 5.Продолжение12 переменных xij удовлетворяют двум

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