Архив категории ‘Исследование операций’

Решение задач

    На этом шаге мы рассмотрим решение нескольких задач линейного программирования.     Задача 1. Запишите двойственную задачу для следующей прямых задачи линейного программирования и найдите ее оптимальное решение.     Минимизировать z = 3x1 + 4x2 + 6x3 при ограничениях x1 + x2 ≥ 10, x1, x3 ≥ 0, x2 ≤ 0.     Задача 2. Решите […]

Пример решения задачи двойственным симплекс-методом

    На этом шаге рассмотрим применение двойственного симплекс-метода для решения задачи линейного программирования.     Дана задача линейного программирования:     Минимизировать     При ограничениях     Начальная симплекс-таблица имеет вид:     Среди дополнительных переменных этой задачи х3 и х4 являются избыточными, а x5 — остаточной. Умножим каждое равенство, соответствующее избыточным дополнительным переменным, на -1; в результате правые […]

Двойственый симплекс-метод

    На этом шаге рассмотрим алгоритм двойственного симплекс-метода.     Рассмотрим симплексный алгоритм, который основан на соотношениях между прямой и двойственной задачами. Этот алгоритм эффективно решает определенный класс задач линейного программирования.     В двойственном симплекс-методе решение задачи линейного программирования начинается с недопустимого, но лучшего, чем оптимальное решения. Последовательные итерации этого метода приближают решение к области допустимости […]

Пример экономической интерпретации ограничений двойственной задачи

    На этом шаге мы рассмотрим пример экономической интерпретации ограничений двойственной задачи.     Фабрика игрушек TOYCO собирает три вида игрушек: модели поездов, грузовиков и легковых автомобилей; при сборке каждого вида используется три типа операций. Ежедневный фонд рабочего времени на каждую операцию ограничен предельными величинами 430, 460 и 420 минут. Доход на одну игрушку каждого вида […]

Экономическая интерпретация ограничений двойственной задачи

    На этом шаге мы рассмотрим экономическую интерпретацию ограничений двойственной задачи.     Для интерпретации ограничений двойственной задачи используем соотношение 1. В соответствии с этим соотношением на любой итерации решения прямой задачи справедливо равенство коэффициент при xj в z-строке = .     Для интерпретации этого равенства воспользуемся анализом размерностей входящих в него величин. Коэффициент сj — […]

Пример экономической интерпретации переменных двойственной задачи

    На этом шаге мы рассмотрим пример экономической интерпретации переменных двойственной задачи.     Приведем формулировки прямой и двойственной задач, описывающие модель производства компании "Русские краски", в которой описывается производство двух видов краски на основе двух видов сырья, с учетом рыночных условий. Задача состоит в определении объемов производства красок каждого вида, при которых будет получен максимальный […]

Экономическая интерпретация переменных двойственной задачи

    На этом шаге мы рассмотрим экономическую интерпретацию переменных двойственной задачи.     Соотношение 2 устанавливает, что для любой пары решений прямой и двойственной задач значения (конечные) их целевых функций удовлетворяют неравенству .     Строгое равенство здесь достигается только тогда, когда решения прямой и двойственной задач оптимальны.     Рассмотрим сначала случай оптимума, т.е. когда z = […]

Экономическая интерпретация двойственности

    На этом шаге мы рассмотрим экономическую интерпретацию двойственности.     Задачу линейного программирования можно рассматривать как модель распределения ограниченных ресурсов, в которой целевая функция, отображающая прибыль или доход от производственной деятельности, подлежит максимизации. Если рассматривать задачу линейного программирования с этой точки зрения, соответствующая ей двойственная задача получает интересную экономическую интерпретацию.    Чтобы формализовать рассматриваемый вопрос, приведем […]

Применение второго соотношения между оптимальными решениями прямой и двойственной задач

    На этом шаге мы рассмотрим одноканальную модель системы массового обслуживания с ожиданием и не более, чем N клиентами. В примере шага 42 нетрудно показать (путем подстановки в ограничения), что прямая и двойственная задачи имеют допустимые решения х1 = 0, х2 = 0, х3 = 8/3 и у1 = 6, у2 = 0. Для этих […]

Применение первого соотношения между оптимальными решениями прямой и двойственной задач

    На этом шаге мы рассмотрим пример, иллюстрирующий применение первого соотношения.     Рассмотрим прямую и двойственную задачи из примера 1, которые для удобства сведены в следующую таблицу.     В следующей таблице представлены симплекс-итерации решения прямой задачи.     Применяя на третьей симплекс-итерации соотношение 1 для переменных х4 и R из начального базисного решения, получим следующие данные. […]