Содержание
- 2. Пусть прямая задача, состоит в нахождении максимального значения функции: При условиях
- 3. Тогда двойственной по отношению к прямой задаче называется задача нахождения минимума функции При условиях
- 4. Правила формирования двойственной задачи : Целевая функция исходной задачи исследуется на максимум, а целевая функция двойственной
- 5. Матрица из коэффициентов при неизвестных в системе ограничений прямой задачи и аналогичная матрица в двойственной задаче
- 6. Число ограничений одной из задач совпадает с числом переменных в другой задаче. Коэффициенты при переменных в
- 7. Если переменная xj исходной задачи может принимать только неотрицательные значения, то j-е ограничение двойственной задачи является
- 8. Алгоритм составления двойственной задачи: Привести все неравенства системы ограничений исходной задачи к одному виду: если в
- 9. Составить расширенную матрицу системы ограничений исходной задачи, в которую включить матрицу коэффициентов при переменных , столбец
- 10. Найти матрицу А Т транспонированную к матрице А Сформулировать двойственную задачу на основании полученной матрицы и
- 11. Пример. Составить задачу, двойственную к следующей задаче:
- 12. Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду “≤”, для
- 13. Составим расширенную матрицу системы:
- 14. Найдем матрицу А т, транспонирующую к А.
- 15. Сформулируем двойственную задачу:
- 16. Теорема 1. Если исходная задача имеет оптимальный план, то и сопряженная к ней задача имеет оптимальный
- 17. Теорема 2 . Пара допустимых решений X* - в исходной задаче, Y* - в двойственной задаче
- 18. Связь исходной и двойственной задач Решение одной из них может быть получено из решения другой. Используя
- 19. Пример. Для производства трех видов изделий I, II, III используется 3 вида сырья. Запасы заданы в
- 20. Определить план выпуска продукции, при котором обеспечивается её максимальная стоимость и оценить каждый из видов сырья,
- 21. Решение. Обозначим через x1 – количество изделий I, x2 – изделий II, x3 – изделий III,
- 22. Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, равную yi . Тогда общая
- 23. Двойственные оценки должны быть такими , чтобы общая оценка сырья, используемого на производство единицы продукции каждого
- 24. Эти задачи образуют пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий I, II,
- 25. Найдем решение этой задачи симплекс-методом.
- 26. Из этой таблицы видно, что оптимальным планом производства изделий I, II, III является такой, при котором
- 27. Положительную двойственную оценку имеют те виды сырья, которые полностью используются. Переменные y1 и y3 обозначают двойственные
- 28. Вычислим значение целевой функции двойственной задачи Первая теорема двойственности выполняется – значение целевых функций двух задач
- 29. Проверим вторую терему двойственности Сначала подставим полученные значения переменных в ограничения прямой задачи, вычтем свободные члены
- 30. Подставим значения двойственных оценок в ограничения двойственной задачи ИЛИ
- 31. Первое ограничение выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного
- 33. Скачать презентацию