Теорія двоїстості та двоїсті оцінки у лінійному програмуванні. Економічна інтерпретація задач лінійного програмування. Правила побудови двоїстих задач. Встановлення зв’язків між оптимальними розв’язками задач за допомогою леми та теореми двоїстості.
Аннотация к работе
В роботі розглянуто математичні задачі, методи їх розвязування, економічні та технологічні процеси, економічна інтерпретація прямої та двоїстої задач лінійного програмування, правила побудови двоїстих задач, основні теореми двоїстості та їх економічний зміст, приклади застосування теорії двоїстості для знаходження оптимальних планів прямої та двоїстої задач, післяоптимізаційний аналіз задач лінійного програмування. Математичне програмування передусім є строгою математичною дисципліною, тому критеріями класифікації мають бути в основному математичні структури (властивості) задач і методів їх розвязування. Якщо всі змінні можуть набувати будь-якого значення в деяких інтервалах числової осі, то задача є неперервною. Задача (3.4) - (3.6) є двоїстою або спряженою до задачі (3.1) - (3.3), яку називають прямою (основною, початковою). У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невідємних значень.З останньої симплекс-таблиці запишемо оптимальний план прямої задачі: Х = (0; 5/3; 2/3; 0), Zmax = 10/3. Згідно зі співвідношенням двоїстості за першою теоремою можна висновувати, що оптимальний план двоїстої задачі існує і min F = max Z = 10/3. Компоненти вектора Y (оптимальний план двоїстої задачі) визначимо за формулою: , де та міститься в стовпчику «сбаз» останньої симплекс-таблиці; Застосувавши для розвязування прямої задачі симплекс-метод, ми знайшли її оптимальний план, а потім визначили оптимальний розвязок двоїстої задачі за допомогою співвідношень першої теореми двоїстості. Розвязавши двоїсту задачу графічно, визначити оптимальний план прямої задачі. min Z = x1 2x2 2x3;Підставимо Y у систему обмежень двоїстої задачі і зясуємо, як виконуються обмеження цієї задачі: Оскільки перше обмеження для оптимального плану двоїстої задачі виконується як строга нерівність, то висновуємо, що перша змінна прямої задачі дорівнюватиме нулю х1 = 0 (перша частина другої теореми двоїстості). Тепер проаналізуємо оптимальний план двоїстої задачі. Обєднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х1 = 0, та визначити решту змінних: тобто Х = (0; 5/3; 2/3), min Z = 1 х 0 2 х 5/3 2 х 2/3 = 14/3. Умова min Z = max F = 14/3 виконується, і тому Х = (0; 5/3; 2/3); Y = (-2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розвязок двоїстої задачі.
План
Перший опорний план задачі:Оптимальний план прямої задачі визначимо за допомогою співвідношень другої теореми двоїстості.