Повна версія

Головна arrow Економіка arrow Дослідження операцій в економіці

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ПОДВІЙНІ ЗАВДАННЯ

Кожній задачі лінійного програмування відповідає інша задача, звана двоїстої, або сполученої, по відношенню до вихідної. Теорія двоїстості виявилася корисною для проведення якісних досліджень задач лінійного програмування.

Економічна інтерпретація завдання, двоїстої задачі про використання ресурсів

У гл. 1 розглянуто задачу про використання ресурсів (економіко-математична модель та змістовна інтерпретація цього завдання I представлені в лівій частині табл. 6.1). У наведеній моделі Т- (г = 1, 2, ..., т) позначає запас ресурсу S 'а. - число одиниць ресурсу S jt споживаного при виробництві одиниці продукції Р. (j = 1,2, ..., п); Cj - прибуток (виручка) від реалізації одиниці продукції Р. (або ціна продукції Р.).

Припустимо, що деяка організація вирішила закупити ресурси 5 ,, S 2, ..., S m підприємства і необхідно встановити оптимальні ціни на ці ресурси y v у 2, ..., у т.

Очевидно, що купує організація зацікавлена в тому, щоб витрати на всі ресурси Z в кількостях b v b 2, ..., Ь т за цінами відповідно у у у 2, ..., у т були мінімальні, тобто

У той же час, підприємство, що продає ресурси, зацікавлене в тому, щоб отримана виручка була не менше тієї суми, яку підприємство може отримати при переробці ресурсів в готову продукцію. На виготовлення одиниці продукції Р {витрачається "Π одиниць ресурсу 54, а 2 [одиниць ресурсу S 2, ..., а п одиниць ресурсу 5 (, ..., a mi одиниць ресурсу S m за ціною відповідно у { , у 2 , ..., у т. Тому для задоволення вимог продавця витрати на ресурси, що споживаються при виготовленні одиниці продукції Р {, повинні бути не менше нiж її ціни c v тобто

Аналогічно можна скласти обмеження у вигляді нерівностей по кожному виду продукції . Економіко-математична модель та змістовна інтерпретація отриманої таким чином двоїстої задачі II наведені в правій частині табл. 6.1.

Таблиця 6.1

Завдання I (початкова)

Завдання II (подвійна)

при обмеженнях:

при обмеженнях:

і умови невід'ємності

і умови невід'ємності

Скласти такий план випуску продукції X = (x v х 2, .... х п ), при якому прибуток (виручка) від реалізації продукції буде максимальною за умови, що споживання ресурсів за кожним видом продукції не перевершить наявних запасів

Знайти такий набір цін (оцінок) ресурсів Y = г у 2, ..., у п ), при якому загальні витрати на ресурси будуть мінімальними за умови, що витрати на ресурси при виробництві кожного виду продукції будуть не менш прибутку (виручки ) від реалізації цієї продукції

Ціни ресурсів в економічній літературі отримали різні назви: облікові, неявні, тіньові. Сенс цих назв полягає в тому, що це умовні, "несправжні" ціни. На відміну від "зовнішніх" цін па продукцію, відомих, як правило, до початку виробництва, ціни ресурсів є внутрішніми, так як вони задаються не ззовні, а визначаються безпосередньо в результаті рішення задачі, тому їх частіше називають оцінками ресурсів.

Взаємно двоїсті задачі лінійного програмування і їх властивості

Розглянемо формально два завдання I і 11 лінійного програмування, представлені в табл. 6.1, абстрагуючись від змістовної інтерпретації параметрів, що входять в їх економіко-математичні моделі. Обидва завдання мають такі властивості.

  • 1. В одному завданню шукають максимум лінійної функції, в іншій - мінімум.
  • 2. Коефіцієнти при змінних в лінійній функції однієї задачі є вільними членами системи обмежень в інший.
  • 3. Кожна із завдань задана в стандартній формі, причому в задачі максимізації все нерівності виду "<", а в задачі мінімізації все нерівності виду ">".
  • 4. Матриці коефіцієнтів при змінних в системах обмежень обох завдань є транспоновану один до одного: 5 6

  • 5. Число нерівностей в системі обмежень однієї задачі збігається з числом змінних в іншому завданні.
  • 6. Умови невід'ємності змінних є в обох задачах.

Дві завдання I і II лінійного програмування, що володіють вказаними властивостями, називаються симетричними взаємно подвійними завданнями . В подальшому для простоти будемо називати їх просто подвійними завданнями.

Виходячи з визначення, можна запропонувати наступний алгоритм складання двоїстої задачі.

  • 1. Привести все нерівності системи обмежень вихідної задачі до одного змістом: якщо у вихідній задачі шукають максимум лінійної функції, то все нерівності системи обмежень привести до виду "≤", а якщо мінімум - до виду "≥". Для цього нерівності, в яких дана вимога не виконується, помножити на -1.
  • 2. Скласти розширену матрицю системи А у в яку включити матрицю коефіцієнтів при змінних А, стовпець вільних членів системи обмежень і рядок коефіцієнтів при змінних в лінійній функції.
  • 3. Знайти матрицю А {, транспоновану до матриці А г
  • 4. Сформулювати двоїсту задачу на підставі отриманої матриці А і умови невід'ємності змінних.
  • 6.1. Скласти задачу, двоїсту наступної задачі:

при обмеженнях:

Рішення. 1. Так як вихідна задача на максимізацію, то наведемо все нерівності системи обмежень до виду "≤", для чого обидві частини першого і четвертого нерівності помножимо на -1. отримаємо

2. Складемо розширену матрицю системи:

3. Знайдемо матрицю А , транспоновану до А:

4. Сформулюємо двоїсту задачу: при обмеженнях:

 
<<   ЗМІСТ   >>