Економічна інтерпретація прямої та двоїстої задач лінійного програмування. Основні правила побудови двоїстих задач. Основні теореми двоїстості та їх економічний зміст. Приклади застосування для знаходження оптимальних планів прямої та двоїстої задач.
Аннотация к работе
Економічна інтерпретація прямої та двоїстої задач лінійного програмування лінійний програмування двоїстийЗадача (5.4)-(5.6) є двоїстою або спряженою до задачі (5.1)-(5.3), яку називають прямою (основною, початковою). Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду «», а для задачі на відшукання мінімального значення - до виду «». У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невідємних значень. Якщо одна з пари спряжених задач має оптимальний план, то й друга задача також має розвязок, причому для оптимальних розвязків значення цільових функцій обох задач збігаються, тобто .
План
Перший опорний план задачі: X0=(0; 0; 0; 5; 1), Z0= - M.
4. Подальше розвязування прямої задачі подано у вигляді симплексної таблиці:
З останньої симплекс-таблиці запишемо оптимальний план прямої задачі:
Х*=(0; 5/3; 2/3; 0), Zmax=10/3.
Згідно зі співвідношенням двоїстості за першою теоремою можна зробити висновок, що оптимальний план двоїстої задачі існує і min F = max Z = 10/3.
Компоненти вектора Y* (оптимальний план двоїстої задачі) визначимо за формулою: , де та міститься в стовпчику «Сбаз» останньої симплекс-таблиці;
.
Матриця D-1 також міститься в останній симплекс-таблиці у стовпчиках змінних «x5» та «x4», які утворювали початковий базис.
Отже, , min F = - 1 ? 0 5 ? 2/3 = 10/3.
Застосувавши для розвязування прямої задачі симплекс-метод, ми знайшли її оптимальний план, а потім визначили оптимальний розвязок двоїстої задачі за допомогою співвідношень першої теореми двоїстості.
Приклад 5.2. До заданої задачі лінійного програмування записати двоїсту задачу. Розвязавши двоїсту задачу графічно, визначити оптимальний план прямої задачі. min Z = x1 2x2 2x3;
Розвязання. За відповідними правилами побудуємо двоїсту задачу: мах F = y1 4y2;
Зауважимо, що задачі несиметричні, і тому змінна у1, що відповідає першому рівнянню в системі обмежень прямої задачі, може мати будь-який знак, а змінна у2 - лише невідємна.
Двоїста задача має дві змінні, а отже, її можна розвязати графічно (рис.5.2).
Рисунок 5.2
Найбільшого значення цільова функція двоїстої задачі F досягає в точці В багатокутника ABCD. Її координати визначимо розвязанням системи рівнянь:
Отже, Y* = (- 2/3; 4/3); max F = 1 ? (- 2/3) 4 ? 4/3 = 14/3.
Оптимальний план прямої задачі визначимо за допомогою співвідношень другої теореми двоїстості.
Підставимо Y* у систему обмежень двоїстої задачі і зясуємо, як виконуються обмеження цієї задачі: Оскільки перше обмеження для оптимального плану двоїстої задачі виконується як строга нерівність, то висновуємо, що перша змінна прямої задачі дорівнюватиме нулю х1=0 (перша частина другої теореми двоїстості).
Тепер проаналізуємо оптимальний план двоїстої задачі. Оскільки друга компонента плану у2=4/3 додатна, то друге обмеження прямої задачі для Х* виконуватиметься як строге рівняння (друга частина другої теореми двоїстості).
Обєднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х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) є оптимальними планами відповідно прямої та двоїстої задач.
Приклад 5.3. Визначити, чи є оптимальними такі плани сформульованої задачі лінійного програмування: min Z = 12x1 - 4x2 2x3;
а) Х = (8/7; 3/7; 0); б) Х = (0; 1/5; 8/5); в) Х = (1/3; 0; 1/3).
Розвязання. Принцип розвязування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розвязок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках: 1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.
2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.
3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.
Запишемо двоїсту задачу до прямої задачі лінійного програмування: max F = y1 2y2;
Перевіримо запропоновані плани на оптимальність.
1. Х = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі: Обидва обмеження виконуються, і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 ? 8/7 - 4 ? 3/7 2 ? 0 = 12.
Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 8/7 > 0; x2 = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у1 та у2: Підставимо ці значення в третє обмеження системи двоїстої задачі: ;
.
Для визначених значень у1 = 4; у2 = 4 це обмеження не виконується, і тому відповідний план у = (4; 4) є недопустимим планом двоїстої задачі. Внаслідок цього наше допущення, що Х = (8/7; 3/7; 0) є оптимальним планом прямої задачі, виявилося помилковим.
2. Х = (0; 1/5; 8/5). Підставимо цей план у систему обмежень прямої задачі: План допустимий, і для нього Z = 12 ? 0 - 4 ? 1/5 2 ? 8/5 = 12/5.
Визначимо відповідний план двоїстої задачі. Оскільки компоненти x2 та x3 додатні, то друге і третє обмеження двоїстої задачі можна записати як рівняння:
Перевіримо, чи виконується перше обмеження двоїстої задачі для визначених значень у1 та у2: 2 ? 8/5 2/5 = 18/5 < 12. Отже, перше обмеження виконується, і тому у = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього
F = 8/5 2 ? 2/5 = 12/5 = Z.
З огляду на викладене можна зробити висновок, що Y* = (8/5; 2/5) є оптимальним планом двоїстої задачі, а X* = (0; 1/5; 8/5) - оптимальним планом прямої задачі.
Наше припущення відносно запропонованого плану виявилося правильним.
3. Х = (1/3; 0; 1/3). Для цього плану обмеження прямої задачі виконуються так: Оскільки Х = (1/3; 0; 1/3) є недопустимим планом, то він не може бути також оптимальним планом прямої задачі.
Отже, перевірка запропонованих планів на оптимальність дала такі результати: а) ні;
б) так, Х* = (0; 1/5; 8/5), min Z = 12/5;
в) ні.
Приклади застосування теорем двоїстості для знаходження оптимальних планів задач лінійного програмування
Приклади застосування теорії двоїстості для знаходження оптимальних планів прямої та двоїстої задач [2, с.75-82],[3, с.122-128].