Двойственная задача линейного программирования. Решение задач и контрольных работ по линейному программированию онлайн
Краткая теория
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется прямой или исходной. Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому говорят о паре взаимно двойственных задач линейного программирования. Пара симметричных двойственных ЗЛП имеет следующий вид:
|
Прямая задача:
|
Двойственная задача
|
Рассмотренная пара взаимно
двойственных задач может быть экономически интерпретирована, например, так.
Прямая задача: сколько и какой продукции надо произвести, чтобы при заданных объемах имеющихся ресурсов и нормах расходов максимизировать выпуск продукции в стоимостном выражении?
Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных и минимизировать общую оценку затрат на ресурсы?
Для построения двойственной задачи необходимо пользоваться следующими правилами:
- Если прямая задача
решается на максимум, то двойственная — на минимум, и наоборот.В задаче на максимум
ограничения-неравенства имеют смысл ≤, а в задаче минимизации — смысл ≥.Каждому ограничению
прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому
ограничению двойственной задачи соответствует переменная прямой задачи.Матрица системы
ограничений двойственной задачи получается из матрицы системы ограничений
исходной задачи транспонированием.
Свободные члены системы ограничений
прямой задачи являются коэффициентами при соответствующих переменных целевой
функции двойственной задачи, и наоборот.Если на переменную
прямой задачи наложено условие неотрицательности, то соответствующее
ограничение двойственной задачи записывается как ограничение-неравенство, если
же нет, то как ограничение-равенство.Если какое-либо
ограничение прямой задачи записано как равенство, то на соответствующую
переменную двойственной задачи условие неотрицательности не налагается.Основное неравенство теории двойственности
Для любых допустимых планов и пары двойственных задач справедливо неравенство . Его экономическое содержание состоит в том, что для любого допустимого плана производства и любого допустимого вектора оценок ресурсов общая созданная стоимость не превосходит суммарной оценки ресурсов.
Критерий оптимальности Канторовича (достаточный признак оптимальности)
Если для некоторых
допустимых планов
и
пары
двойственных задач выполняется равенство
, то
и
являются оптимальными планами
соответствующих задач. Экономический смысл критерия следующий: план
производства
и
вектор оценок ресурсов
являются оптимальными, если цена всей
произведенной продукции и суммарная оценка ресурсов совпадают.
Теорема существования оптимальных планов пары двойственных задач
Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существования допустимого плана для каждой из них.
Первая теорема двойственности
Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций совпадают . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание
первой теоремы двойственности состоит в следующем: если задача определения
оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима
и задача определения оценок ресурсов. Причем цена продукта, полученного в
результате реализации оптимального плана, совпадает с суммарной оценкой
ресурсов. Совпадения значений целевых функций для соответствующих решений пары
двойственных задач достаточно для того, чтобы эти решения были оптимальными.
Это значит, что план производства и вектор оценок ресурсов являются
оптимальными тогда и только тогда, когда цена произведенной продукции и
суммарная оценка ресурсов совпадают. Оценки выступают как инструмент
балансирования затрат и результатов. Двойственные оценки обладают тем
свойством, что они гарантируют рентабельность оптимального плана, то есть
равенство общей оценки продукции и ресурсов обусловливает убыточность всякого
другого плана, отличного от оптимального. Двойственные оценки позволяют
сопоставлять и балансировать затраты и результаты системы.
Связь между задачами
двойственной пары глубже, чем указано в формулировке теоремы. Решая симплексным
методом одну из них, автоматически получаем решение другой. Для этого
достаточно воспользоваться соответствием переменных прямой и двойственной задач
и оценок в последней симплексной таблице.
| … | … | … | … | ||||
| | | | | | | | | | | | | | | | |
| … | … | … | … | ||||
| … | … | … | … |
Отсюда имеем оптимальный
план двойственной задачи. Если прямая задача решается на максимум, то пользуясь
соответствием переменных:
и так далее.
Если прямая задача решается на минимум, то:
и так далее.
Вторая теорема двойственности (о дополняющей нежесткости)
Для того, чтобы планы и пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
Эти условия называются
условиями дополняющей нежесткости. Из них следует: если какое-либо неравенство
системы ограничений одной из задач не обращается в строгое равенство
оптимальным планом этой задачи, то соответствующая компонента оптимального
плана двойственной задачи должна равняться нулю. Если же какая-либо компонента
оптимального плана одной из задач положительна, то соответствующее ограничение
в двойственной задаче ее оптимальным планом должно обращаться в строгое
равенство.
Экономически это означает, что если по некоторому оптимальному плану производства расход i-го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а избыточный ресурс (используемый не полностью) имеет нулевую оценку.
Третья теорема двойственности
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения ЗЛП, то есть:
Выясним экономическое
содержание третьей теоремы двойственности. Для этого в последнем выражении
дифференциалы заменим приращениями. Получим:
При имеем
То есть двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки часто называют скрытыми, теневыми или маргинальными оценками ресурсов.
Примеры решения задач
Задача 1
Постройте модель двойственной задачи для данной задачи линейного программирования, заданной в произвольной форме.
Решение
Воспользуемся правилами для построения двойственной задачи.Заполним вспомогательную таблицу.
| ДЗ/ПЗ | min | СП/ЦФ | |||
| -18 | 7 | -12 | -2 | ||
| -12 | 16 | -12 | 3 | ||
| -11 | 3 | -7 | = | -2 | |
| 0 | 13 | -12 | -1 | ||
| max | = | ||||
| ЦФ/СП | -18 | 1 | -3 |
Двойственная задача будет иметь следующий вид:
–любого знака,
Задача 2
Для приведенной ниже задачи
записать двойственную. Решить одну из них симплексным методом и получить решение
другой.
Решение
Приведем задачу к каноническому виду.
Воспользуемся правилами для построения двойственной задачи.
Двойственная задача будет иметь следующий вид:
Приведем двойственную задачу к каноническому виду.
Заполняем симплексную таблицу 0-й итерации.
| БП | Симплексные отношения | ||||||||
| 5 | 4 | 0 | 0 | 0 | 0 | ||||
| 0 | 3 | 2 | 3 | 1 | 0 | 0 | 0 | 3/2 | |
| 0 | 4 | 1 | -2 | 0 | 1 | 0 | 0 | 4 | |
| 0 | 5 | -1 | 1 | 0 | 0 | 1 | 0 | — | |
| 0 | 6 | 5 | 4 | 0 | 0 | 0 | 1 | 6/5 | |
| 0 | -5 | -4 | 0 | 0 | 0 | 0 | |||
Если не находите примера, аналогичного вашему, если сами не успеваете выполнить работу, если впереди экзамен по предмету и нужна помощь — свяжитесь со мной:
ВКонтакте
WhatsApp
Telegram
Я буду работать с вами, над вашей проблемой, пока она не решится.
Переходим к таблице 1-й итерации:
| БП | Симплексные отношения | ||||||||
| 5 | 4 | 0 | 0 | 0 | 0 | ||||
| 0 | 3/5 | 0 | 7/5 | 1 | 0 | 0 | -2/5 | ||
| 0 | 14/5 | 0 | -14/5 | 0 | 1 | 0 | -1/5 | ||
| 0 | 31/5 | 0 | 9/5 | 0 | 0 | 1 | 1/5 | ||
| 5 | 6/5 | 1 | 4/5 | 0 | 0 | 0 | 1/5 | ||
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | |||
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Соответствие между переменными исходной и двойственной задачи:
|
|
|
|
|
|
|
|
| |
| |
| |
| |
| |
| |
|
|
|
|
|
|
|
На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования:
Задача 3
Дана задача линейного программирования:
Решение прямой задачи:
Найти
оптимальное решение двойственной задачи линейного программирования.
Решение
Исходя из вышеописанных правил построения модели двойственной задачи, двойственная задача будет иметь следующий вид:
Найдем оптимальное решение двойственной задачи:
Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения:
Так как для оптимального решения прямой задачи 3-е и 4-е ограничения выполняются как неравенство, то
Для нахождения значений и , получаем:
Ответ
Решение двойственной задачи:
Юдин Д. Б., Гольштейн Е. Г. Задачи и методы линейного программирования ОНЛАЙН
Математика / Математика для студентов, аспирантов и научных работников / Методы оптимизации, математическое программирование, математическое моделирование / Экономика / Экономика для студентов и аспирантов / Экономическая математика
Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования . — М., 1961. — 492 с.
Книга является первым в отечественной литературе систематическим изложением теоретических основ, методов и приложений новой математической дисциплины — линейного программирования. Основное внимание здесь обращено на обоснование и описание вычислительных алгоритмов, которые доводятся до расчетных схем и иллюстрируются примерами.
Книга предназначена для широкого круга специалистов — математиков, инженеров и экономистов с повышенной математической подготовкой.
ОГЛАВЛЕНИЕ
Предисловие……………………….3
Глава 1. Основные понятия линейного программирования . 7
§ 1. Предмет линейного программирования … 7
§ 2. Задачи линейного программирования …….. 11
п. 2.1. Организация снабжения…………..11
п. 2.2. Выбор системы вооружения.. …………18
п. 2.3. Размещение заказов и загрузка оборудования . 20
§ 3. Каноническая форма задач линейного программирования …………….23
§ 4. Геометрический смысл простейших задач линейного программирования………………27
§ 5. Выпуклые многогранники и линейное программирование ……………………38
§ 6. Векторы условий и вектор ограничений … 48
§ 7. Геометрические интерпретации общей задачи линейного программирования…………..52
§ 8. Экономическая интерпретация и терминология задачи линейного программирования ….. 59
§ 9. Общая характеристика методов линейного программирования ………..63
§ 10. Краткая историческая справка ……
Глава 2. Практические задачи линейного программирования 75
§ 1. Задача о смеси………………..78
§ 2. Об оптимальном раскрое материалов …. 78
§ 3. Распределение самолетов между воздушными линиями……………………83
§ 4. Сельскохозяйственные задачи…………84
§ 5. Задачи о размещении оборудования …. 88
§ 6. Общая планово-производственная задача … 91
§ 7. Проблема составления графиков……….95
§ 8. Дилемма: быстро, но дорого, или медленно, но дешево…………100
§ 9. Выбор рациональной системы допусков . . . 103
§ 10. Планирование производства и перевозок …..110
§ 11. Военные приложения методов линейного программирования (по материалам зарубежной печати) …..119
§ 12. Проблема узких мест . ……. 120
§ 13. Задача целераспределения …….125
§ 14. Теоретико-игровые модели задач линейного программирования ……….131
Глава 3. Метод последовательного улучшения плана . . 136
§ 1. Основы метода . 137
§ 2. Выбор начального опорного плана . . …… 147
§ 3. Связь между параметрами последовательных приближений ……….. 151
§ 4. Алгоритм метода последовательного улучшения плана ………….160
§ 5. Вторая форма критерия оптимальности …. 178
§ 6. II алгоритм 182
§ 7. Вырожденность……….204
§ 8. Исследование общих проблем линейного программирования с помощью метода последовательного улучшения плана . ……….214
Глава 4. Общие методы линейного программирования, основанные на принципе двойственности … 217
§ 1. Основы теории двойственности……217
п. 1.1. Постановка вопроса…….217
п. 1.2. Теоремы двойственности….. . 222
п. 1.3. Задачи линейного программирования со смешанными условиями……..228
п. 1.4. Задачи линейного программирования в канонической форме………234
п. 1.5. Критерии оптимальности……237
п. 1.6. Геометрическая интерпретация задач двойственной пары………242
§ 2. Метод последовательного уточнения оценок . . 246
п. 2.1. Предварительные замечания …. 246
п. 2.2. Основы метода………………..248
п. 2.3. Геометрическая интерпретация метода . . 258
п. 2.4. Алгоритм метода……..259
п. 2.5. Способы отыскания первого приближения . 266
п. 2.6. Случай вырожденности. …..276
п 2.7. Методы улучшения плана и уточнения оценок….. 285
п. 2.8. Пример………..290
§ 3. Метод последовательного сокращения невязок …… 300
п. 3.1. Предварительные замечания …….. . 300
п. 3.2. Описание метода …….. 303
п. 3.3. Алгоритм метода . 310
п. 3.4. Пример………..317
п. 3.5. Об оценках быстроты сходимости метода сокращения невязок …….. 323
Глава 5. Транспортная задача 326
§ 1. Постановка вопроса и предварительные замечания 327
п. 1.1. Постановка задачи . . . . . . . 327
п. 1.2. О разрешимости транспортной проблемы . . 333
п. 1.3. Алгоритм построения плана…..335
п. 1.4. Транспортная задача с нарушенным балансом
производства и потребления . . . . 338
п. 1.5. Свойства решений транспортной задачи . . 340
п. 1.6. Условия невырожденности транспортной задачи 343
п. 1.7. О задачах, сводящихся к транспортной …… . 346
§ 2. Метод потенциалов……. 349
п. 2.1. Предварительные замечания . ……….349
п. 2.2. Описание метода потенциалов …. 350
п. 2.3. Описание алгоритма ……… 356
п. 2.4. Метод минимального элемента …. 365
п. 2.5. Распространение метода на вырожденные задачи . … 369
§ 3. Венгерский метод………377
п. 3.1. Предварительные замечания…..377
п. 3.2. Проблема выбора………379
п. 3.3. Алгоритм решения проблемы выбора . . . 380
п. 3.4. Обоснование алгоритма решения проблемы выбора …………383
п. 3.5. Общая транспортная задача, алгоритм . . 393
п. 3.6. Обоснование алгоритма решения общей транспортной задачи……….398
п. 3.7. Пример………..402
п. 3.8. Особенности венгерского метода …. 404
Глава 6. Математические основы линейного программирования 408
§ 1. Конечномерные пространства и выпуклые множества 408
п. 1.1. Конечномерное векторное пространство . . 408
п. 1.2. Выпуклые множества…….415
п. 1.3. Крайние точки множества и их свойства . . 420
п. 1.4. Выпуклые конусы . . ……426
§ 2. Доказательства теорем двойственности …. 434
§ 3. Обоснование некоторых утверждений главы 5 ….. 441
Глава 7. Заключение . ……..459
§ 1. Некоторые специальные вопросы линейного программирования ………..461
п. 1.1. Выпуклое программирование…..461
п. 1.2. Целочисленное программирование …. 464
п. 1.3. Учет специфики задач……465
§ 2. Линейное программирование и теория игр . . . 467
§ 3. Перспективные вопросы линейного программирования …………..477
п. 3.1. Параметрическое программирование . . . 477
п. 3.2. Линейное программирование в условиях неопределенности ………480
Литература …… …….484
Калькулятор метода Big M онлайн
Метод Big M является одним из обязательных методов обучения для студентов, изучающих операции, и часто создает для них трудности из-за используемых расчетов. Чтобы помочь вам лучше понять этот метод, мы разработали онлайн-калькулятор для решения задач линейного программирования методом Big M. Этот инструмент имеет те же операции и эстетику, что и наше онлайн-приложение двухфазного симплексного метода.
Калькулятор метода Big M — Бесплатная версия
Количество переменных:
Количество ограничений:
У вас уже есть членство?
Получить членство
Онлайн-калькулятор Big M в бесплатной версии показывает нам таблицы для каждой из итераций, необходимых для получения окончательного решения. Однако, если вы хотите узнать больше о том, как получается каждое число в таблицах, мы предлагаем вам проверить профессиональную версию нашего калькулятора:
Расширенные функции онлайн-калькулятора метода больших М
Для решения упражнений по линейному программированию методом больших М мы должны применить симплекс-алгоритм. Вот почему мы разработали калькулятор для всех наших пользователей с членством, который дает вам подробное объяснение того, как алгоритм применяется в каждой из строк таблицы и как получить соответствующие значения. Для этой цели мы включили следующие функции:
- Вы можете решать упражнения с 20 переменными и 50 ограничениями.
- Анализ способов определения условия оптимальности.
- Объяснение критериев для установления условия осуществимости.
- Пояснение к расчетам, выполненным для получения вектора приведенных затрат, сводной строки и остальных строк таблицы.
- Анализ особых случаев, таких как неограниченные и недопустимые решения.
Полные примеры работы приложения можно найти по этой ссылке.
Как использовать калькулятор метода Big M
Чтобы использовать наше приложение, необходимо выполнить следующие шаги:
- Введите количество переменных и ограничений задачи.
- Выберите тип проблемы: максимизировать или минимизировать .
- Введите коэффициенты целевой функции и ограничения. Вы можете вводить отрицательные числа, дроби и десятичные дроби (с точкой).
- Нажмите «Решить».
- Онлайн-калькулятор адаптирует введенные значения к стандартной форме симплексный алгоритм и создать первую таблицу.
- Вы сможете визуализировать таблицы, рассчитанные для каждой из итераций метода Big M. Если вы используете версию членства, вы сможете увидеть пошаговые расчеты каждого значения таблицы в каждой из итераций, а также объяснение условия оптимальности и выполнимости и, наконец, оптимальное решение.
Пример:
Ниже мы показываем некоторые справочные изображения шаг за шагом и результат следующего примера:
Для минимизации следующей задачи требуется:
Целевая функция Z = 3X 1 + 2X 2 .
Subject to the following constraints
2X 1 + X 2 ≥ 18
2X 1 + 3X 2 ≥ 42
X 1 , X 2 ≥ 0
Solution:
Сначала вводим количество переменных и ограничений:
Записываем коэффициенты целевой функции и ограничения:
Нажав «Решить», мы увидим детали расчета. Ниже в качестве примера показаны некоторые части:
Итерации в сводной строке:
И, наконец, результат упражнения:
решать задачи с ограничениями со знаками «равно» и «больше» или «равно». Эти типы ограничений добавят искусственные переменные в стандартную модель линейного программирования. Если задача имеет только ограничения со знаком меньше или равным, калькулятор решит ее традиционным симплексным методом. В любом случае, наш инструмент может решить любую задачу, будь то минимизация и/или максимизация.
Напоминаем, что в рамках нашего членства вы также получите доступ к нашему калькулятору для двухфазного метода и графического метода линейного программирования.
Окончательное размышление
Наличие программного инструмента, который шаг за шагом решает метод Big M , — это «лайфхак», который вы не должны пропустить, чтобы повысить свою производительность, свое обучение и, прежде всего, свои оценки.
Если у вас есть вопросы по этому поводу или вы нашли ошибку в нашем приложении, мы будем признательны, если вы напишите нам на нашей странице контактов.
Онлайн-линейная оптимизация с ограничениями разреженности
Джун-Кун Ван, Чи-Джен Лу, Шоу-Де ЛиньМатериалы 30-й Международной конференции по теории алгоритмического обучения , PMLR 98:883-897, 2019.
Аннотация
Мы изучаем задачу линейной онлайн-оптимизации с ограничениями разреженности в полубандитной постановке. Его можно рассматривать как сочетание двух хорошо известных задач: онлайн-задачи линейной оптимизации и комбинаторной бандитской задачи. Для этой проблемы мы предлагаем алгоритм, который эффективен и достигает сублинейной границы сожаления. Кроме того, мы распространили наши результаты на две обобщенные настройки: одну с задержкой обратной связи и одну с затратами на получение обратной связи. Наконец, мы проводим эксперименты, которые показывают эффективность наших методов на практике.
Процитировать эту статью
БибТекс
@InProceedings{pmlr-v98-wang19b,
title = {Линейная онлайн-оптимизация с ограничениями разреженности},
автор = {Ван, Цзюнь-Кун и Лу, Чи-Джен и Линь, Шоу-Дэ},
booktitle = {Материалы 30-й Международной конференции по алгоритмической теории обучения},
страницы = {883--897},
год = {2019},
редактор = {Гаривье, Орельен и Кале, Сатьен},
громкость = {98},
серия = {Материалы исследования машинного обучения},
месяц = {22--24 марта},
издатель = {PMLR},
pdf = {http://proceedings.mlr.press/v98/wang19b/wang19b.pdf},
URL = {https://proceedings.mlr.press/v98/wang19b.html},
абстракция = {
Мы изучаем задачу линейной онлайн-оптимизации с ограничениями разреженности в полубандитной постановке. Его можно рассматривать как сочетание двух хорошо известных задач: онлайн-задачи линейной оптимизации и комбинаторной бандитской задачи. Для этой проблемы мы предлагаем алгоритм, который эффективен и достигает сублинейной границы сожаления. Кроме того, мы распространили наши результаты на две обобщенные настройки: одну с задержкой обратной связи и одну с затратами на получение обратной связи. Наконец, мы проводим эксперименты, которые показывают эффективность наших методов на практике.}
}
Сноска
%0 Документ конференции
%T Онлайн-линейная оптимизация с ограничениями разреженности
%A Джун-Кун Ван
%A Чи-Джен Лу
%A Шоу-Де Лин
%B Материалы 30-й Международной конференции по теории алгоритмического обучения
%C Материалы исследований машинного обучения
%D 2019
%E Орельен Гаривье
%E сатьен капуста
%F pmler-v98-wang19b
%I PMLR
%Р 883--897
%U https://proceedings.mlr.press/v98/wang19b.html
%V 98
%ИКС
Мы изучаем задачу линейной онлайн-оптимизации с ограничениями разреженности в полубандитной постановке. Его можно рассматривать как сочетание двух хорошо известных задач: онлайн-задачи линейной оптимизации и комбинаторной бандитской задачи. Для этой проблемы мы предлагаем алгоритм, который эффективен и достигает сублинейной границы сожаления.