- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
15.Экономическая интерпретация двойственной задачи
Что отражает двойственная модель? Оказывается, она дает возможность оценить решение исходной (прямой) задачи. В рассматриваемом примере прямая задача состоит, фактически, в наилучшем использовании всех имеющихся ресурсов. Каждому варианту плана поизводства продукции соответствует свое использование ресурсов, а, следовательно, и их полезность или значимость. Под последним понимается степень влияния ресурса на результат. Так как каждому условию прямой задачи, отражающему использование ресурса, ставится в соответствие двойственная переменная, то именно она и является мерилом значимости этого ресурса.
Действительно, рассмотрим уравнение размерности условия двойственной задачи
[A][U]=[C].
Пусть, например, ресурс – фонд времени оборудования (сколько часов оборудование может быть загружено в течение планового периода). Тогда размерность двойственной переменной будет
.
Итак, U дает стоимость единицы ресурса в единицах критерия, то есть в нашем случае – прирост произведенной стоимости в рублях на каждый дополнительный час работы оборудования. Ниже, в теоремах двойственности, это будет показано строго математически. Поэтому двойственные переменные называют также теневыми ценами. Чтобы увидеть отличие теневой цены от рыночной, возьмем конкретные цифры. Пусть рыночная цена некоторого ресурса, полностью используемого в производстве, равна 500 руб/кг и 1 кг достаточно (при наличии других ресурсов) для выпуска дополнительной продукции на сумму 100000 руб. Тогда теневая цена этого ресурса равна 100000 руб. Если поставщик сорвал поставку данного ресурса, то он должен нести ответственность не в размере рыночной цены, а по теневой цене за каждую единицу недопоставленного ресурса. Такое предложение было высказано впервые Л. Канторовичем, который называл двойственные переменные объективно обусловленными оценками, сокращенно О.О.О. (объективные цены, складывающиеся в конкретной ситуации производства и потребления).
Таким образом, чем больше абсолютная величина двойственной переменной, тем выше значимость ресурса в полученном решении, и наоборот, более сильному влиянию ресурса на критерий соответствует большее значение двойственной переменной.
Теперь интерпретируем условия двойственной задачи. Если Ui – объективная цена за единицу ресурса, то левая часть неравенства двойственной модели представляет собой полные затраты на производство единицы продукции, а все неравенство отражает тот факт, что произведенная стоимость Ci не может превышать суммарных затрат.
Значимость ресурса эквивалентна его дефицитности. Поэтому критерий двойственной задачи можно интерпретировать как суммарную дефицитность ресурсов, которую следует минимизировать.
Другая трактовка заключается в том, что двойственная задача моделирует взаимодоговоренности Покупателя и Продавца ресурсов. Продавец готов продать свои ресурсы, отказавшись от производства продукции, если цены на них (Ui) будут такими, что он получит за ресурсы, расходуемые им на единицу продукции, не меньше Ci, то есть не меньше того, что он имел бы от производства этой продукции. Эти требования выражаются неравенствами двойственной задачи. С другой стороны, Покупатель стремится к таким ценам, которые минимизируют плату за все ресурсы. Это стремление и выражает критерий двойственной задачи.