Xreferat.com » Рефераты по экономико-математическому моделированию » Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

лінійного програмування: економічна інтерпретація знаходження оптимальних планів" width="103" height="21" align="BOTTOM" border="0" /> – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівабо Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів. (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

і Базис Сб План с1 с2 сm cm + 1 cn




x1 x2 xm xm + 1 xn
1 x1

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

1 0 0

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

2 x2

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

0 1 0

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів












m xm

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

0 0 1

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

m + 1

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

F0 0 0 0

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


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

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


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(3.12)

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

Звідси:


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів(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) можливе лише у тому разі, коли кожний доданок виду Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: