Симметричные двойственные задачи
Рассмотрим задачу производственного планирования. Пусть предприятие имеет m видов ресурсов объемом единиц. Эти ресурсы должны быть использованы для выпуска n видов продукции. Пусть – норма потребления i-го вида ресурса на производство единицы j-ой продукции; – цена реализации j-ой продукции; – объем производства j-ой продукции, обеспечивающий предприятию максимальную выручку.
План производства следует составить из условия максимизации общей стоимости продукции при ограничениях на использовании ресурсов
,
Или в краткой форме записи математическая модель задачи имеет вид:
(1)
, (2)
, (3)
Задачу (1) – (3) называют исходной.
По исходным данным задачи (1) – (3) сформируем другую экономическую задачу.
Предположим, что предприятию разрешено на его усмотрение реализовать все указанные ресурсы. Необходимо установить цены на них – , , пользуясь следующими соображениями:
– покупатель стремится минимизировать их общую стоимость;
– предприятие согласно продать по ценам, дающим прибыль не меньшую, чем выручка, которую оно может получить от реализации изготовленной продукции.
Эти требования можно записать в виде следующей ЗЛП:
,
Или в краткой форме записи:
(4)
, (5)
, (6)
Полученную задачу (4) – (6) называют двойственной. Переменные называются двойственными оценками, или теневыми ценами.
Задачи (1) – (3) и (4) – (6) называют парой взаимно двойственных симметричных задач, т.к. они обладают следующими свойствами:
1. Если в одной задаче ищется максимум целевой функции, то в другой – минимум.
2. Коэффициенты при переменных в целевой функции одной задачи являются правыми частями ограничений другой задачи и, наоборот.
3. В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла: если задача на max, то все неравенства содержат знаки « », если на min, то все неравенства содержат знаки « ».
4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
5. Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Примечание: Понятие «прямой» и «двойственной» задач условно.
Дата добавления: 2022-07-20; просмотров: 81;