Двойственные задачи и их решение
Каждой задаче линейного программирования ставят в соответствие другую задачу, построенную на основе тех же данных по определенным правилам. Эти правила сводятся к следующему: § все ограничения исходной задачи приводят к одному виду: в случае § выписывают матрицу коэффициентов при неизвестных § используют новые переменные (неотрицательные) и на основе транспонированной матрицы формируют ограничения двойственной задачи. Знак неравенств берут противоположным по отношению к знаку неравенств исходной задачи. В качестве правых частей ограничений используют коэффициенты целевой функции исходной задачи; § составляют целевую функцию двойственной задачи, беря в качестве коэффициентов правые части ограничений исходной задачи. Направленность целевой функции двойственной задачи будет противоположна направленности целевой функции исходной задачи. Например, для задачи, решенной симплексным методом, составим двойственную, исходя из приведенных правил.
Переход от любой задачи к двойственной можно выполнить, используя табличную схему:
Запись одной задачи идет по строкам, другой – по столбцам.
! Необходимо запомнить, что при решении одной из двух двойственных задач автоматически решается и вторая, и значения целевых функций у них совпадают. Решение двойственной задачи с обратным знаком содержится в
Например, в рассмотренной задаче имели:
Дополнительными были столбцы
Рассмотрение двойственных задач очень полезно, т.к. они имеют самостоятельный экономический смысл и позволяют изучать экономический процесс с разных сторон.
Анализ матричной игры Теория игр – это математическая теория конфликтных ситуаций. Игра – конфликтная ситуация, регламентированная определенными правилами: § порядок выполнения ходов; § порядок выполнения каждого хода; § количественный результат игры. Наиболее изучены матричные игры. Например,
В этой игре два участника – сторона
Решить игру – значит, дать рекомендации каждом из сторон относительно использования их стратегий. Предварительно игру анализируют по “принципу мини-макса”. Он состоит в выборе наиболее осторожной стратегии, исходя из наихудшего образа действия другой стороны. а) Анализируем игру с позиций стороны б) Анализируем игру с позиции стороны
в) Цена игры Если
где
Каждой матричной игре можно поставить в соответствие две двойственные задачи, отражающие интересы сторон. Для стороны Анализ матричной игры проводится в два этапа: § формируются двойственные задачи, решают одну из них симплекс-методом и записывают решение обеих двойственных задач; § определяют решение игры. 1. Запишем две двойственные задачи на основе приведенной платежной матрицы:
Симплексное решение удобно проводить для первой задачи, т.к. в ней не будет искусственных переменных. Данная задача приобретет вид: В результате использования симплекс-алгоритма получим:
Решение будет иметь вид: а)
б)
2. Найдем решение игры: а) определим цену игры, – эта величина характеризует количественный результат игры:
б) найдем вероятности стратегий:
в) составим оптимальные стратегии для участников
Как видим, для достижения оптимального результата стороне
Метод потенциалов Этот метод используется для решения многих распределительных задач, содержащих большое число переменных и включающих в себя требование целочисленности решения. Такими, в частности, являются транспортные задачи, на них и будет проиллюстрирован алгоритм метода. Теоретические основы метода следующие: § необходимым и достаточным условием существования решения является баланс между спросом и предложением; § по загруженным клеткам определяют систему потенциалов:
где
§ в оптимальном распределении сумма потенциалов строки и столбца не должна превосходить тариф соответствующей незагруженной клетки; § количество поставок должно быть равно величине Метод потенциалов осуществляется в три этапа: 1. Построение первоначального опорного плана (начальное распределение грузов). 2. 0ценка оптимальности распределения грузов с помощью системы потенциалов. 3. Улучшение плана перевозок, если оно возможно. Второй и третий этапы повторяются до тех пор, пока решение не станет оптимальным.
I этап. Построение начального опорного плана
Начальное распределение можно выполнять различными способами: способом северо-западного угла, способом наименьших тарифов, двойного предпочтения, способом Фогеля, способом Лебедева-Тихомирова и др. Наиболее простым и легко реализуемым на ЭВМ является способ северо-западного угла. Он заключается в том, что от каждого поставщика, начиная с первого, вывозят весь груз с учетом запросов потребителей. Распределение завершено, если весь груз от поставщиков вывезен, а каждый потребитель получил требуемый объем. Рассмотрим пример: имеется три поставщика Таблица 1
Установим, прежде всего, наличие баланса между спросом и предложением 250 + 150 + 250 = 650 200 + 250 + 200 = 650 Баланс есть. Теперь распределим груз, начиная с первой верхней клетки, отсюда и название способа - северо-западный угол. Распределение завершено, необходимо определить затраты (величину
II этап. Оценка оптимальности решения По загруженным клеткам составим систему уравнений для потенциалов, предварительно проверив количество заполненных клеток. Их должно быть
Имеем систему из 5 уравнений с 6 неизвестными, поэтому один из потенциалов примем равным 0. Обычно берут
Теперь необходимо проверить выполнение второго условия оптимального решения: сумма потенциалов для незаполненной клетки не должна превосходить величину тарифа в ней.
Условие оптимальности ни для одной из пустых клеток не выполняется. Следует улучшить решение.
III этап. Построение нового распределения Из всех клеток, для которых условие оптимальности не выполняется, выбирают ту, в которой расхождение наибольшее. Если таких клеток несколько, то выбирают клетку с меньшим тарифом. Ее отмечают знаком “+”. Начиная от выбранной клетки, строят прямоугольную фигуру, все остальные вершины которой располагаются в заполненных клетках. Знаки вершин чередуют. Прямоугольные фигуры могут быть следующих видов: Реже встречаются фигуры такого вида:
Вид фигуры предопределен распределением поставок. Из всех клеток, отмеченных знаком минус, выбирают наименьший груз. Его перемещают вдоль прямоугольной фигуры, прибавляя, если стоит знак “+”, и, вычитая, если стоит знак “–”. Все изменения отражают в новой таблице. Величины, не участвующие в перераспределении, в новую таблицу переносят без изменения. Обратимся к примеру: в таблице 1 знаком “–” отмечены две клетки, выбирают наименьший груз 50 и перемещают его вдоль прямоугольной фигуры. Все изменения отражают в табл. 2. Получено новое распределение: необходимо оценить его, поэтому возвращаемся ко II этапу алгоритма.
Таблица 2
Проверим число заполненных клеток, их по-прежнему 5. Вновь находим потенциалы, причем можно не составлять систему, а использовать правила: 1. В 1 строке берем 0. 2. Неизвестный потенциал столбца равен разности между издержками заполненной клетки и известным потенциалом строки. 3. Неизвестный потенциал строки равен разности между издержками заполненной клетки и известным потенциалом столбца. Чередуя эти правила, найдем потенциалы. Проверку оптимальности также можно проводить непосредственно в таблице, ставя “точку”, если условие выполняется, и, указывая в круглых скобках величину расхождения в случае невыполнения условия. В нашем примере самое большое расхождение между суммой потенциалов и тарифами – в клетке (2;1). Строим прямоугольную фигуру и замечаем, что две клетки, отмеченные знаком “–”, имеют одинаковую наименьшую величину 150, – этот факт ведет к вырожденному распределению. И действительно, после перемещения получим таблицу 3, в которой число загруженных клеток равно 4. Таблица 3
Вырожденность может появиться и исчезнуть при переходе от таблицы к таблице. Чтобы продолжить решение в случае вырожденной задачи, вводят нулевые поставки, соответствующие клетки считают условно заполненными. Нулей будет столько, сколько недостает поставок. Их вписывают в клетки, имеющие малые издержки, и при этом следят, чтобы не получался замкнутый цикл (прямоугольная фигура, во всех вершинах которой - заполненные клетки). В данном примере следует вписать один ноль и лучше всего в клетку (3; 1). В остальном решение обычное: находят потенциалы, проверяют условие оптимальности. После очередного перераспределения получим таблицу 4. Таблица 4
Задача вновь стала невырожденной - число загруженных клеток равно 5. Условие оптимальности выполняется. Размещение грузов видно из таблицы. Найденные суммы издержек на каждом этапе решения: Замечание 1. Если мы имеем дело с открытой транспортной задачей, то для ее решения необходимо первоначально обеспечить баланс между спросом и предложением. Для этого вводят дополнительного поставщика, если спрос превышает предложение, в противном случае вводят дополнительного потребителя. Если добавляют поставщика, то его “мощностью” будет величина, недостающая до баланса, транспортные тарифы берут равными нулю. Аналогично поступают, если добавляют потребителя. В дальнейшем решение проводят по изложенному выше алгоритму. Введение дополнительного поставщика или потребителя имеет вполне определенное экономическое объяснение. В первом случае мы определяем, какому потребителю выгоднее недопоставить груз, исходя из интересов всех участников, во втором случае – у какого поставщика целесообразнее всего оставить часть груза. Замечание 2. Ранее был подробно рассмотрен способ северо-западного угла для начального распределения грузов. Число итераций (таблиц) можно уменьшить, если воспользоваться способом наименьших тарифов. Он заключается в анализе всей матрицы тарифов, выборе наименьших значений и максимальном заполнении соответствующих клеток таблицы. Эти действия выполняются до тех пор, пока не будет распределен весь груз и удовлетворен спрос всех потребителей. В результате заполнения одной из клеток исключается из рассмотрения какой-то поставщик или потребитель. При этом условные участники транспортной задачи принимаются во внимание в последнюю очередь. Рассмотрим пример транспортной задачи.
Баланса между спросом и предложением нет, необходимо ввести условного поставщика с мощностью 150 тыс. единиц. Распределение выполним способом наименьших тарифов
Полученный план не оптимален, следует перейти к лучшему. Это можно сделать на основе изложенного алгоритма.
Задачи о назначении
Проблема, состоящая в том, чтобы правильно распределить наличные людские ресурсы в соответствии с профессиональными требованиями, актуальна в разных сферах – в армии, в промышленности, в кадровой политике любой структуры. Математическое программирование является одним из важных инструментов в области рационального использования персонала. Центральное место в указанной проблеме занимает задача о назначении. В ней переменные интерпретируются как назначение соответствующего человека на определенную работу. Каждая переменная может принимать лишь значения, равные единице (претендент выбран) или нулю (претендент не выбран). Математическая структура этой задачи следующая:
где Например, если § приходится вписывать большое число нулей, что вызывает некоторые затруднения; § прямоугольная фигура перераспределения величин иногда бывает достаточно сложной. Пример. Семь претендентов распределяются на 7 участков деятельности. Решается задача на минимум затрат. Последовательность использования претендентов и перераспределения отражены в таблицах 1 – 3. Таблица 1
Начальное распределение было выполнено по методу наименьших тарифов.
Таблица 2
В таблице 2 распределение нуждается в улучшении. Таблица 3
В таблице 3 условие оптимальности выполняется, конкретные назначения видны. Если рассматривается задача на максимум эффективности использования персонала, то помимо указанных особенностей существенно меняется алгоритм метода потенциалов: § распределение следует вести по наибольшим показателям эффективности; § располагать нули также следует в клетки с большими тарифами; § условие оптимальности противоположно традиционному – сумма потенциалов для пустых клеток должна быть не меньше тарифа, именно в этом случае будет достигнут максимум. Пример. Рассмотрим ту же самую матрицу тарифов, предполагая, что в ней указаны показатели эффективности. Таблица 1
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|