Двойственность в задачах линейного программирования. 17 Двойственность в задачах линейного программирования
 Скачать 3.38 Mb.
|
|
17 Двойственность в задачах линейного программирования. Двойственность ЗЛП сводится к тому, что вместо поиска максимума можно искать минимум двойственной задачи с другими переменными, и наоборот. В итоге это может дать один и тот же эффект. Например, если необходимо в течение рабочего дня получить дополнительное время на решение выполнения некоторого задания, то можно или максимизировать скорость выполнения других заданий при сохранении ограничения на время отдыха, или, наоборот, минимизировать время отдыха при сохранении ограничения на скорость выполнения других заданий. Преобразование прямой задачи в двойственную производится следующим путем: вместо n переменных прямой задачи в двойственной задаче вводятсяm новых переменных (z) по количеству ограничений в прямой задаче; в выражение целевой функции с новыми переменными вместо коэффициентовсi записываются коэффициентыbj, которые в прямой задаче есть значения ограничений; вместо поиска максимума в прямой задаче осуществляется поиск минимума в двойственной задаче; вместоm ограничений прямой задачи вводятсяn ограничений двойственной задачи. Результаты этих преобразований представлены ниже.  Сматематической точки зрения переход к двойственной задаче позволяет вряде случаев упростить решение, применить более эффективные методы, невозможные для прямой задачи. 18 Постановка задачи динамического программирования Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана. Если модели линейного программирования можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях, то модели динамического программирования применяются при решении задач значительно меньшего масштаба, например, при разработке правил управления запасами; при распределении инвестиционных ресурсов между альтернативными проектами; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены и т.п. Общая постановка задачи динамического программирования. Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования и т.п. В результате управления система (объект управления) S переводится из начального состояния s0 в состояние sn. Пусть, управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управленческих решений. Обозначим через Xk управленческое решение на k-м шаге (k=1, 2, …, n). Переменные Xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Xk может быть числом, точкой в n-мерном пространстве или качественным признаком). Пусть X=(X1, X2, …, Xn) – управление, переводящее систему S из состояния s0 в состояние sn. Обозначим через sk состояние системы (характеризуемое определенным набором параметров и конкретных их значений) после k-го шага управления. Причем состояние системы sk в конце k-го шага зависит только от предшествующего состояния sk-1 и управленческого решения на k-ом шаге Xk (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:  Таким образом, получаем последовательность состояний s0, s1, …, sk-1, sk, …, sn-1, sn. Тогда n-шаговый управленческий процесс схематично можно изобразить следующим образом: |