 |
Построение двойственной задачи к задаче распределения ресурсов
|
|
|
|
Построение экономико-математической модели задачи распределения ресурсов
С целью построения экономико-математической модели задачи распределения ресурсов следует ввести переменные и представить исходные данные в табличном виде:
| Норма затрат Ресурсы | Виды изделий | Запас ресурсов | Скрытые цены ресурсов | |||
| 
| 
| yi | yi* | ||
| a11 | a12 | a13 | b1 | 
| |
| a21 | a22 | a23 | b2 | 
| |
| a31 | a32 | a33 | b3 |  
| |
| Цена единицы изделия | c1 | c2 | c3 | fmax(х) | gmin(у) | |
| План выпуска | xj | 
| 
| 
| ||
| xj* |
Введем переменные: х1 – объем производства продукции первого вида; х2 – объем производства продукции второго вида; х3 – объем производства продукции третьего вида.
Представим исходные данные варианта 4 в виде таблицы 1.
Таблица 1 - Исходные данные
| Норма затрат Ресурсы | Виды изделий | Запас ресурсов | Скрытые цены ресурсов | |||
|
|
|
| yi | yi* | ||
|
|
| |||||
|
|
| |||||
|
|
| |||||
| Цена единицы изделия | fmax(х) | gmin(у) | ||||
| План выпуска | xj |
|
|
| ||
| xj* |
Целевая функция, отражающая доход от реализации произведенной продукции, представляет собой сумму произведений объема производства каждого вида продукции на значение ее цены:
,
где n – количество видов продукции.
Поскольку требуется максимизировать доход, то целевая функция стремиться к максимуму. При ресурсных ограничениях, представленных системой неравенств, левые части которых отражают затраты ресурсов каждого вида на производство продукции соответствующего вида, а правые отражают запасы ресурсов каждого вида. Знак неравенств «меньше или равно», поскольку расход ресурсов не должен превысить имеющихся запасов:
|
|
|
,
где m – количество ресурсов.
Также должно выполняться условие неотрицательности переменных:
.
Таким образом, экономико-математическая модель прямой задачи линейного программирования (ПЗЛП) варианта 4 имеет вид:
при ограничениях:
Данная ПЗЛП имеет стандартную форму записи, поскольку в задаче на максимум все функциональные (ресурсные) ограничения имеют знаки «меньше или равно».
Построение двойственной задачи к задаче распределения ресурсов
Для построения двойственной задачи линейного программирования (ДЗЛП) следует ввести двойственные переменные: у1 – скрытая цена первого ресурса; у2 – скрытая цена второго ресурса; у3 – скрытая цена третьего ресурса.
Целевая функция ДЗЛП представляет собой совокупные затраты второго предприятия на приобретение всех ресурсов первого предприятия, при этом второе предприятие стремиться, чтобы его затраты на приобретение ресурсов у первого предприятия были минимальными:
.
Ограничениями ДЗЛП является система неравенств, отражающая условия, при которых первому предприятию будет выгодно продать свои ресурсы вместо производства из них продукции, то есть при равенстве или превышении суммы, полученной от второго предприятия, над суммой дохода, полученной от реализации продукции:
.
Должно выполняться условие неотрицательности переменных:
.
Также для построения ДЗЛП можно руководствоваться следующими правилами.
1. В первой задаче определяется максимум линейной целевой функции, во второй – минимум.
2. Коэффициенты при переменных в целевой функции первой задачи являются правыми частями в системе ограничений во второй задаче.
3. Каждая из задач задана в стандартной форме, при этом в задаче максимизации все неравенства вида «меньше или равно», а в задаче минимизации все неравенства вида «больше или равно».
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.
|
|
|
Экономико-математическая модель ДЗЛП варианта 4 имеет вид:
при ограничениях
Данная ДЗЛП имеет стандартную форму записи, поскольку в задаче на минимум все функциональные (затратные) ограничения имеют знаки «больше или равно».
|
|
|
