ДВОЙСТВЕННЫЕ ЗАДАЧИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ: ТЕОРИЯ И АНАЛИЗ ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ РЕСУРСОВ

DUAL PROBLEMS IN LINEAR PROGRAMMING: THEORY AND ANALYSIS OF OPTIMAL RESOURCE USE

Khmelnitskaya Arina Stanislavovna,

Student, Department of Higher Mathematics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

Kireev Sergey Vladimirovich

Scientific supervisor, Candidate of Physical Sciences. - Mat. Sciences, Associate Professor of the Department of Higher Mathematics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

АННОТАЦИЯ

В данной статье рассматривается концепция двойственности в линейном программировании как математическая основа для оценки эффективности использования ограниченных производственных ресурсов. Актуальность темы обусловлена необходимостью количественного обоснования управленческих решений о закупке сырья и распределении трудозатрат. В теоретической части последовательно изложены правила построения симметричных двойственных пар, а также сформулированы первая и вторая теоремы двойственности, включая теорему о дополняющей нежесткости. Раскрыт экономический смысл двойственных переменных как объективно обусловленных оценок или теневых цен. В практической части работы рассматривается конкретная производственная задача мебельного цеха с двумя видами продукции и двумя ресурсами. Решение прямой задачи выполнено аналитическим методом через перебор угловых точек допустимой области. По найденному оптимальному плану выпуска построена двойственная задача и вычислены теневые цены обоих ресурсов. Проведена проверка выполнения теорем двойственности, подтвердившая корректность расчётов. Дана экономическая интерпретация полученных двойственных оценок, позволяющая определить предельно допустимые цены закупки дополнительного сырья и ставки оплаты сверхурочного труда. Показано, что метод двойственности представляет собой универсальный инструмент анализа чувствительности оптимального решения к изменению запасов ресурсов.

ABSTRACT

This article considers the concept of duality in linear programming as a mathematical basis for evaluating the efficiency of using limited production resources. The relevance of the topic is due to the need for quantitative substantiation of managerial decisions on the purchase of raw materials and the allocation of labor inputs. The theoretical part consistently outlines the rules for constructing symmetric dual pairs, as well as formulates the first and second duality theorems, including the complementary slackness theorem. The economic meaning of dual variables as objectively determined valuations or shadow prices is revealed. The practical part of the work considers a specific production problem of a furniture workshop with two types of products and two resources. The solution of the primal problem is performed by the analytical method through enumeration of the corner points of the feasible region. Based on the found optimal production plan, a dual problem is constructed and the shadow prices of both resources are calculated. The fulfillment of the duality theorems is verified, confirming the correctness of the calculations. An economic interpretation of the obtained dual assessments is given, allowing one to determine the marginal purchase prices for additional raw materials and overtime pay rates. It is shown that the duality method represents a universal tool for analyzing the sensitivity of the optimal solution to changes in resource stocks.

Ключевые слова: линейное программирование, двойственная задача, теневая цена, оптимизация, ограниченные ресурсы, теорема двойственности.

Keywords: linear programming, dual problem, shadow price, optimization, limited resources, duality theorem.

Задача оптимального распределения ограниченных ресурсов между несколькими направлениями производства является классической в исследовании операций. Традиционный подход предполагает решение прямой задачи: найти план выпуска, максимизирующий прибыль при заданных запасах сырья и трудозатрат. Однако теория двойственности позволяет взглянуть на проблему с другой стороны и оценить внутреннюю стоимость каждого ресурса. Целью работы является построение двойственной задачи для конкретного производственного примера и анализ полученных теневых цен.

Понятие двойственной задачи и правила её построения

Двойственная задача в линейном программировании представляет собой математическую конструкцию, зеркально отражающую прямую задачу. Если прямая задача отвечает на вопрос «как получить максимум продукции из имеющихся ресурсов?», то двойственная ставит вопрос иначе: «какова минимальная внутренняя стоимость этих ресурсов, при которой производство остаётся оправданным?».

Переменные двойственной задачи y_i называются объективно обусловленными оценками или теневыми ценами. Каждая такая переменная соответствует одному ограничению прямой задачи и показывает, на сколько изменится оптимальное значение целевой функции при увеличении запаса соответствующего ресурса на единицу.

Правила построения симметричной двойственной пары формулируются следующим образом. Пусть прямая задача имеет вид:

Целевая функция Z = ∑c_jx_j стремится к максимуму.

Ограничения: ∑a_ijx_j ≤ b_i для всех i.

Условие неотрицательности: x_j ≥ 0 для всех j.

Тогда двойственная задача строится так:

Целевая функция W = ∑b_iy_i стремится к минимуму.

Ограничения: ∑a_ijy_i ≥ c_j для всех j.

Условие неотрицательности: y_i ≥ 0 для всех i.

Число переменных двойственной задачи равно числу ограничений прямой, и наоборот. Коэффициентами в левых частях двойственных ограничений служат элементы транспонированной матрицы исходных технологических коэффициентов.

Теоремы двойственности

Ключевое значение для анализа имеют две фундаментальные теоремы.

Первая теорема двойственности утверждает, что если прямая задача имеет конечное оптимальное решение, то двойственная также разрешима, причём Z_max = W_min. Это означает, что максимальная прибыль, получаемая из наличных ресурсов, в точности равна минимальной суммарной внутренней оценке этих ресурсов.

Вторая теорема о дополняющей нежесткости устанавливает связь между переменными и ограничениями пары задач. Если в оптимальной точке некоторый ресурс использован не полностью, его двойственная оценка равна нулю. Если же ресурс израсходован полностью, его теневая цена положительна. Аналогично, если по некоторому продукту суммарная оценка затраченных ресурсов строго превышает его удельную прибыль, то выпуск такого продукта в оптимальном плане равен нулю.

Экономический смысл второй теоремы прост: дефицитный ресурс имеет цену, избыточный — нет.

Рассмотрим мебельный цех, выпускающий два изделия: книжные полки и журнальные столики. Для производства требуются два ресурса — древесина и труд. Нормы расхода, недельные запасы и удельная прибыль представлены в таблице 1.

Таблица 1.

Исходные данные

Построение и решение прямой задачи

Обозначим через x₁ количество полок, через x₂ — количество столиков. Прямая задача формулируется следующим образом:

Z = 8x₁ + 6x₂ → max

При ограничениях:

2x₁ + x₂ ≤ 30,

x₁ + 3x₂ ≤ 45,

x₁ ≥ 0, x₂ ≥ 0.

Для нахождения оптимального решения проанализируем угловые точки допустимой области.

Точка A (пересечение прямой 2x₁ + x₂ = 30 с осью x₁): x₂ = 0, x₁ = 15. Прибыль Z = 8·15 = 120.

Точка B (пересечение прямой x₁ + 3x₂ = 45 с осью x₂): x₁ = 0, x₂ = 15. Прибыль Z = 6·15 = 90.

Точка C (начало координат): x₁ = 0, x₂ = 0, Z = 0.

Точка D (пересечение двух ресурсных прямых). Решаем систему уравнений:

2x₁ + x₂ = 30,

x₁ + 3x₂ = 45.

Из первого уравнения выражаем x₂ = 30 − 2x₁. Подстановка во второе уравнение даёт: x₁ + 3(30 − 2x₁) = 45, откуда x₁ + 90 − 6x₁ = 45, −5x₁ = −45, x₁ = 9. Тогда x₂ = 30 − 2·9 = 12. Прибыль Z = 8·9 + 6·12 = 72 + 72 = 144.

Максимальное значение Z = 144 достигается в точке x₁ = 9, x₂ = 12. Оба ресурса при этом плане расходуются полностью.

Построение и решение двойственной задачи

Введём двойственные переменные: y₁ — теневая цена древесины, y₂ — теневая цена труда. По сформулированным выше правилам строим двойственную задачу:

W = 30y₁ + 45y₂ → min

при ограничениях:

2y₁ + y₂ ≥ 8,

y₁ + 3y₂ ≥ 6,

y₁ ≥ 0, y₂ ≥ 0.

Поскольку в оптимальной точке прямой задачи оба ресурса израсходованы полностью, y₁ > 0 и y₂ > 0. Оба продукта присутствуют в оптимальном плане, поэтому оба двойственных ограничения выполняются как равенства. Переходим к системе уравнений:

2y₁ + y₂ = 8,

y₁ + 3y₂ = 6.

Из первого уравнения: y₂ = 8 − 2y₁. Подстановка во второе: y₁ + 3(8 − 2y₁) = 6 → y₁ + 24 − 6y₁ = 6 → −5y₁ = −18 → y₁ = 3,6. Тогда y₂ = 8 − 2·3,6 = 0,8.

Проверка: W = 30·3,6 + 45·0,8 = 108 + 36 = 144. Первая теорема двойственности выполняется: Z_max = W_min = 144.

Интерпретация результатов

Полученные двойственные оценки имеют экономический смысл.

y₁ = 3,6 тыс. руб. означает, что прирост запаса древесины на 1 куб. м увеличит максимальную прибыль на 3,6 тыс. руб. Если рыночная цена дополнительной древесины ниже этой величины, закупка выгодна.

y₂ = 0,8 тыс. руб. показывает, что увеличение фонда рабочего времени на 1 чел./ч даёт прирост прибыли на 800 руб. Если оплата сверхурочного часа не превышает 800 руб., его введение целесообразно.

Соотношение y₁/y₂ = 4,5 говорит о том, что в данной системе древесина в 4,5 раза ценнее труда.

Для рассмотренного примера оптимальный производственный план составляет 9 полок и 12 столиков с недельной прибылью 144 тыс. руб. Двойственные оценки ресурсов равны 3,6 тыс. руб. за кубометр древесины и 0,8 тыс. руб. за человеко-час труда. Метод двойственности позволяет количественно обосновать решения о дополнительной закупке ресурсов и изменении структуры производства, не прибегая к дорогостоящим экспериментам.

Список литературы:

1. Ашманов С.А. Линейное программирование. М.: Наука, 2021. 304 с.
2. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. М.: ИНФРА-М, 2003. 255 с.
3. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Юстиция, 2022. 207 с.
4. Карманов В.Г. Математическое программирование: Учеб.пособие. - 5-е изд. , стереотип. - М.: ФИЗМАТЛИТ, 2004. - 264 с. ISBN 5-9221-0170-6.
5. Костевич Л.С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л.С. Костевич. - Мн.: Новое знание, 2003. -424с.:ил. ISBN 985-6516-83-8.