На этом шаге мы рассмотрим решение нескольких задач линейного программирования. Задача 1. Запишите двойственную задачу для следующей прямых задачи линейного программирования и найдите ее оптимальное решение. Минимизировать z = 3x1 + 4x2 + 6x3 при ограничениях x1 + x2 ≥ 10, x1, x3 ≥ 0, x2 ≤ 0. Задача 2. Решите […]
Архив категории ‘Исследование операций’
Категория: 
Пример решения задачи двойственным симплекс-методом
16 декабря 2020 
mob25 На этом шаге рассмотрим применение двойственного симплекс-метода для решения задачи линейного программирования. Дана задача линейного программирования: Минимизировать При ограничениях Начальная симплекс-таблица имеет вид: Среди дополнительных переменных этой задачи х3 и х4 являются избыточными, а x5 — остаточной. Умножим каждое равенство, соответствующее избыточным дополнительным переменным, на -1; в результате правые […]
Двойственый симплекс-метод
16 декабря 2020 mob25 На этом шаге рассмотрим алгоритм двойственного симплекс-метода. Рассмотрим симплексный алгоритм, который основан на соотношениях между прямой и двойственной задачами. Этот алгоритм эффективно решает определенный класс задач линейного программирования. В двойственном симплекс-методе решение задачи линейного программирования начинается с недопустимого, но лучшего, чем оптимальное решения. Последовательные итерации этого метода приближают решение к области допустимости […]
Пример экономической интерпретации ограничений двойственной задачи
16 декабря 2020 mob25 На этом шаге мы рассмотрим пример экономической интерпретации ограничений двойственной задачи. Фабрика игрушек TOYCO собирает три вида игрушек: модели поездов, грузовиков и легковых автомобилей; при сборке каждого вида используется три типа операций. Ежедневный фонд рабочего времени на каждую операцию ограничен предельными величинами 430, 460 и 420 минут. Доход на одну игрушку каждого вида […]
Экономическая интерпретация ограничений двойственной задачи
16 декабря 2020 mob25 На этом шаге мы рассмотрим экономическую интерпретацию ограничений двойственной задачи. Для интерпретации ограничений двойственной задачи используем соотношение 1. В соответствии с этим соотношением на любой итерации решения прямой задачи справедливо равенство коэффициент при xj в z-строке = . Для интерпретации этого равенства воспользуемся анализом размерностей входящих в него величин. Коэффициент сj — […]
Пример экономической интерпретации переменных двойственной задачи
16 декабря 2020 mob25 На этом шаге мы рассмотрим пример экономической интерпретации переменных двойственной задачи. Приведем формулировки прямой и двойственной задач, описывающие модель производства компании "Русские краски", в которой описывается производство двух видов краски на основе двух видов сырья, с учетом рыночных условий. Задача состоит в определении объемов производства красок каждого вида, при которых будет получен максимальный […]
Экономическая интерпретация переменных двойственной задачи
16 декабря 2020 mob25 На этом шаге мы рассмотрим экономическую интерпретацию переменных двойственной задачи. Соотношение 2 устанавливает, что для любой пары решений прямой и двойственной задач значения (конечные) их целевых функций удовлетворяют неравенству . Строгое равенство здесь достигается только тогда, когда решения прямой и двойственной задач оптимальны. Рассмотрим сначала случай оптимума, т.е. когда z = […]
Экономическая интерпретация двойственности
16 декабря 2020 mob25 На этом шаге мы рассмотрим экономическую интерпретацию двойственности. Задачу линейного программирования можно рассматривать как модель распределения ограниченных ресурсов, в которой целевая функция, отображающая прибыль или доход от производственной деятельности, подлежит максимизации. Если рассматривать задачу линейного программирования с этой точки зрения, соответствующая ей двойственная задача получает интересную экономическую интерпретацию. Чтобы формализовать рассматриваемый вопрос, приведем […]
Применение второго соотношения между оптимальными решениями прямой и двойственной задач
16 декабря 2020 mob25 На этом шаге мы рассмотрим одноканальную модель системы массового обслуживания с ожиданием и не более, чем N клиентами. В примере шага 42 нетрудно показать (путем подстановки в ограничения), что прямая и двойственная задачи имеют допустимые решения х1 = 0, х2 = 0, х3 = 8/3 и у1 = 6, у2 = 0. Для этих […]
Применение первого соотношения между оптимальными решениями прямой и двойственной задач
16 декабря 2020 mob25 На этом шаге мы рассмотрим пример, иллюстрирующий применение первого соотношения. Рассмотрим прямую и двойственную задачи из примера 1, которые для удобства сведены в следующую таблицу. В следующей таблице представлены симплекс-итерации решения прямой задачи. Применяя на третьей симплекс-итерации соотношение 1 для переменных х4 и R из начального базисного решения, получим следующие данные. […]
