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

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

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

Звідси:

(3.13)

Симплексна таблиця 3.1 містить коефіцієнти розкладу векторів початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (3.1) – (3.3) Аj відповідає в симплексній таблиці вектор , такий що

(3.14)

Позначимо через матрицю, що складається з коефіцієнтів розкладу векторів . Тоді буде справджуватися рівність:

, звідки

. (3.15)

Враховуючи (3.13), значення оптимального плану даної задачі знаходиться у вигляді:

де , причому

,

тобто всі компоненти вектора є оцінками оптимального плану задачі (3.1) – (3.3), а тому

. (3.16)

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

. (3.17)

Доведемо, що дійсно є оптимальним планом двоїстої задачі.

Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд: .

Підставимо в цю нерівність значення . Тоді, враховуючи (3.15), (3.16) та (3.17), отримаємо: .

Звідки: . Отже, задовольняє систему обмежень (3.5) двоїстої задачі, тому є допустимим планом задачі (3.4) – (3.6).

Для даного плану значення функціонала дорівнюватиме:

, (3.18)

де . Підставимо в (3.18) значення з (3.17) та, враховуючи (3.13), матимемо:

. (3.19)

Доведено, що збігається зі значенням оптимального плану початкової задачі.

Отже, за лемою 3.2 (достатня умова оптимальності плану задачі лінійного програмування) план є оптимальним планом двоїстої задачі (3.4) – (3.6).

Аналогічно доводиться, що коли двоїста задача має розв’язок, то початкова також має розв’язок і виконується рівність: .

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

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

3.2 Друга теорема двоїстості

Між розв’язками спряжених задач крім рівності значень цільових функцій існує тісніший взаємозв’язок. Для його дослідження розглянемо дві симетричні задачі лінійного програмування.

Пряма задача:

(3.20)

.

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

(3.21)

Для розв’язування задач симплексним методом необхідно звести їх доканонічної форми, для чого в системи обмежень задач (3.20) і (3.21) необхідно ввести відповідно m та n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні її двоїстої задачі.

Отримали таку відповідність між змінними спряжених задач:

Наступна теорема в літературі, як правило, має назву теореми про доповнюючу нежорсткість.

Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани X* та Y* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:

(3.22)

. (3.23)

Доведення. Необхідність. Нехай X* та Y* – оптимальні плани відповідно прямої та двоїстої задач (3.20) i (3.21). З першої теореми двоїстості відомо, що

,

а також компоненти векторів X* та Y* задовольняють системи обмежень задач (3.20) та (3.21), тобто:

, (3.24)

. (3.25)

Помножимо (3.24) на , а (3.25) – на і підсумуємо праві та ліві частини. Отримаємо:

;

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

;

Виконаємо перетворення для кожного рівняння:

; (3.26)

. (3.27)

Оскільки , то в рівнянні (3.26) кожна з компонент , а , тому виконання рівняння (3.26) можливе лише у тому разі, коли кожний доданок виду . Аналогічне міркування проведемо для (3.27), після чого можна висновувати, що .

Достатність. За умовою виконуються рівняння

,

, .

Необхідно довести, що X* та Y* – оптимальні плани відповідно прямої (3.20) та двоїстої (3.21) задач. У кожному рівнянні розкриємо дужки та підсумуємо перше рівняння по , а друге – по . Отримаємо:

;

.

Ліві частини цих рівнянь однакові, отже, . Тоді за першою теоремою двоїстості, оскільки значення цільових функцій цих задач збігаються, можна висновувати, що X* та Y* – оптимальні плани спряжених симетричних задач. Теорему доведено.

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

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

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

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

Якщо ж витрати ресурсу дорівнюють його наявному обсягові , тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка буде строго більшою від нуля.

Економічне тлумачення другої теореми двоїстості щодо оптимального плану Y* двоїстої задачі: у разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну сj, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції дорівнює нулю.

Якщо витрати на виробництво j-го виду продукції дорівнюють ціні одиниці продукції , то її необхідно виготовляти в обсязі, який визначає оптимальний план прямої задачі .

3.3 Третя теорема двоїстості

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

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

(3.28)

Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:

(3.29)

(3.30)

(3.31)

Двоїсту задачу до задачі (3.29) – (3.31) сформулюємо так: знайти оптимальний план , за якого мінімізується значення

(3.32)

за умов:

(3.33)

причому умова невід’ємності змінних відсутня.

Позначимо – оптимальний план двоїстої задачі, – оптимальний план задачі (3.29) – (3.31). За першою теоремою двоїстості відомо, що:

,

або

. (3.34)

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

. (3.35)

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

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

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

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

Отже, за умови незначних змін замість задачі (3.29) – (3.31) маємо нову задачу, де замінено на . Позначимо через оптимальний план нової задачі. Для визначення не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою , де – оптимальний план задачі (3.29) – (3.31).

4. Приклади застосування теорії двоїстості для знаходження оптимальних планів прямої та двоїстої задач

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

До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язати одну з них симплекс-методом та визначити оптимальний план другої задачі, використовуючи співвідношення першої теореми двоїстості.

max Z = – 5x1 + 2x2;

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

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