183956 (584872), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Продавати ресурси доцільно лише за умови, що виручка, отримана від продажу ресурсів, перевищує суму, яку можна було б отримати від реалізації продукції, виготовленої з тих самих обсягів ресурсів, тобто:

.

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

.

Отже, в результаті маємо двоїсту задачу:

(3.4)

за умов: (3.5)

(3.6)

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

Зауважимо, що справжній зміст величин – умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadowprices» у літературі перекладають як «оцінка» або «тіньова, неявна ціна». Академік Л.В. Канторович назвав їх об’єктивно обумовленими оцінками відповідного ресурсу.

Задача (3.4) – (3.6) є двоїстою або спряженою до задачі (3.1) – (3.3), яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (3.4) – (3.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу – двоїстою. Симетричність двох таких задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних: , ; . Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

Початкова постановка задачі та математична модель може мати вигляд як (3.1) – (3.3), так і (3.4) – (3.6). Отже, як правило, кажуть про пару спряжених задач лінійного програмування.

2.1 Правила побудови двоїстих задач

Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду « », а для задачі на відшукання мінімального значення – до виду « ».

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

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

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі – на визначення найменшого значення (min), і навпаки.

4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.

5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.

6. Матриця

,

що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків – рядками.

Процес побудови двоїстої задачі зручно зобразити схематично:

Рис. 3.1. Схема побудови двоїстої задачі до прямої

Пари задач лінійного програмування бувають симетричні та несиметричні.

У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.

У несиметричних задачах деякі обмеження прямої задачі можуть бути рівняннями, а двоїстої – лише нерівностями. У цьому разі відповідні рівнянням змінні двоїстої задачі можуть набувати будь-яких значень, не обмежених знаком.

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

Несиметричні задачі

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

max F = –5x1 + 2x2;

Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак « ». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max F = –5x1 + 2x2;

Тепер за відповідними правилами складемо двоїсту задачу:

;

Або схематично (використовуючи компоненти векторів та матриць) зв’язок між парою цих задач можна зобразити так:

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

Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція F мінімізується і в системі обмежень є нерівності, то вони мають бути виду « ». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

Двоїста задача:

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

3. Основні теореми двоїстості та їх економічний зміст

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (3.1) – (3.3) та (3.4) – (3.6) з економічною інтерпретацією.

Якщо та – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

або . (3.7)

Доведення. Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:

Підсумувавши праві і ліві частини нерівностей, отримаємо:

. (3.8)

Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі:

Підсумувавши після множення тут також ліві та праві частини, отримаємо нерівність:

(3.9)

Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:

.

Нерівність (3.7) доведено.

Якщо та – допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність

(3.10)

то X*, Y* – оптимальні розв’язки відповідних задач.

Доведення. Нехай – допустимий план прямої задачі (3.1) – (3.3). Тоді на підставі нерівності (3.7) маємо: . За умовою задачі , отже

(3.11)

Оскільки за допущенням – довільний допустимий план прямої задачі, то нерівність (3.11) виконується для будь-якого з можливих розв’язків. Отже, маємо, що при цільова функція (3.1) набирає найбільшого значення, тобто є оптимальним розв’язком початкової задачі.

В аналогічний спосіб доводиться, що – оптимальний план двоїстої задачі.

3.1 Перша теорема двоїстості

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

Якщо цільова функція однієї із задач необмежена, то спряжена задача також не має розв’язку.

Доведення. Допустимо, що початкова задача (3.1) – (3.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з першихm векторів . Остання симплексна таблиця має вигляд:

Таблиця 3.1

Позначимо через D матрицю, що утворена з компонент векторів А1, А2,…, Аm останнього базису в першій симплексній таблиці.

Для оптимального плану отримаємо:

(3.12)

де , В-вектор, що складається з вільних членів системи обмежень.

Характеристики

Список файлов ответов (шпаргалок)