Введення
Під двоїстої завданням розуміється допоміжна задача лінійного програмування, формулируемая за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального рішення прямої задачі шляхом рішення двоїстої до неї завдання обумовлена ​​тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними. Трудомісткість обчислень при вирішенні ЗЛП в більшій мірі залежить від числа обмежень, а не від кількості змінних.
Метою курсового проекту є вивчити літературу по обраній темі і навчитися застосовувати на практиці симплекс - метод для вирішення прямої і двоїстої задачі лінійного програмування, а також вирішити двоїсту задачу лінійного програмування за допомогою програми MS Excel.
Курсовий проект складається з вступу, двох розділів і висновку.
У першій главі розглядаються основні поняття і пропозиції теорії подвійності ЗЛП, види математичних моделей двоїстих задач і їх економічна інтерпретація.
У другій розділі розглядається рішення двоїстої задачі за допомогою програми MS Excel.
1. Двоїстість в лінійному програмуванні
1.1 Прямі та двоїсті задачі лінійного програмування
З економічної точки зору двоїсту задачу можна інтерпретувати так: яка повинна бути ціна одиниці кожного з ресурсів, щоб при заданих кількостях ресурсів b i і величинах вартості одиниці продукції C j мінімізувати загальну вартість затрат? А вихідну завдання визначимо наступним, чином: скільки і якої продукції x j ( j = 1,2, ..., n) необхідно зробити, щоб при заданих вартостях C j (j = 1,2, ..., n) одиниці продукції і
розмірах наявних ресурсів b i ( i = 1,2, ..., n) максимізувати випуск продукції у вартісному вираженні. Більшість завдань лінійного програмування спочатку визначаються як вихідні або двоїсті задачі. Зробивши висновок можна говорити про пару двоїстих задач лінійного програмування.
Кожній задачі лінійного програмування можна певним чином зіставити деяку іншу задачу (лінійного програмування), звану двоїстої або сполученої по відношенню до вихідної або прямої задачі. Дамо визначення двоїстої задачі по відношенню до загальної задачі лінійного програмування , складається, як ми вже знаємо, в знаходженні максимального значення функції:
F = c 1 x 1 + c 2 x 2 + ... c n x n
при умовах
Порівнюючи два сформульовані завдання, бачимо, що двоїста задача складається згідно з такими правилами:
1. Цільова функція вихідної завдання задається на максимум, а цільова функція двоїстої на мінімум.
2. Матриця
складена з коефіцієнтів при невідомих у системі обмежень вихідної задачі, і аналогічна матриця
в двоїстої завданню виходять один з одного транспонування (тобто заміною рядків стовпцями, а стовпців - рядками).
3. Число змінних в двоїстої завданню дорівнює числу обмежень у системі початкової задачі, а число обмежень у системі двоїстої задачі - числу змінних у вихідній задачі.
4. Коефіцієнтами при невідомих у цільовій функції двоїстої задачі є вільні члени в системі початкової задачі, а правими частинами в співвідношеннях системи двоїстої завдання - коефіцієнти при невідомих у цільовій функції вихідної задачі.
5. Якщо змінна x j вихідної задачі може приймати тільки лише позитивні значення, то j -е умова в системі двоїстої задачі є нерівністю виду В«>В». Якщо ж змінна x j може приймати як позитивні, так і негативні значення, то 1 - співвідношення в системі являє собою рівняння. Аналогічні зв'язки мають місце між обмеженнями вихідної задачі і змінними двоїстої задачі. Якщо i - співвідношення в системі початкової завдання є нерівністю, то i -я змінна двоїстої задачі . В іншому випадку змінна у j може приймати як позитивні, так і негативні значення.
Двоїсті пари задач зазвичай поділяють на симетричні і несиметричні. У симетричній парі двоїстих задач обмеження прямої задачі і співвідношення двоїстої завдання є нерівностями виду ««. Таким чином, змінні обох задач можуть приймати тільки лише невід'ємні значення.
Двоїста задача тісно пов'язана задачею лінійного програмування. Завдання первісна називається вихідною. Рішення двоїстої задачі може бути отримано з рішення вихідної і навпаки. Сполучною фактом цих двох завдань є коефіцієнти C j функції вихідної задачі. Дані коефіцієнти називаються вільними членами системи обмежень двоїстої задачі. Коефіцієнти B i системи обмежень вихідної задачі називаються коефіцієнтами двоїстої задачі. Транспонована матриця коефіцієнтів системи обмежень вихідної задачі є матрицею коефіцієнтів системи обмежень двоїстої задачі.
Розглянемо задачу використання ресурсів. У підприємства є t видів ресурсів в кількості b i (i = 1, 2, ..., m) одиниць, з яких випускається n видів продукції. На виготовлення 1 од. i-й продукції витрачається a ij од. t-гo ресурсу, її вартість становить C j од. Необхідно визначити план випуску продукції, що забезпечує її максимальний випуск в вартісному вираженні. Приймемо за x j (j = 1,2, ..., n) кількість од. j-й продукций і становить максимальне значення лінійної функції
Z = C 1 x 1 + C 2 x 2 + ... + C n x n
Визначимо ресурси, які потрібні для виготовлення товару. Позначимо за одиницю вартості ресурсів одиницю вартості товару, що випускається. А через у i (j = 1,2, ..., m) вартість одиниці i-го ресурсу. Тобто вартість всіх витрачених ресурсів, які використовуються для винаходу одиниці j-ї продукції, складає. Ціна витрачених ресурсів не повинна перевищувати ціни остаточного товару.
1.2 Основи теореми двоїстості
1.2.1. Несиметричні подвійні задачі
Теорема подвійності:
Система обмежень вихідної задачі в несиметричних двоїстих задачах визначається як рівність. Двоїста ж завдання задається, як нерівність, причому змінні можуть бути і негативними. Що б простіше розуміти постановку задачі будемо інтерпретувати її в матричній формі.
Сформулюємо двоїсту задачу. Необхідно визначити матрицю-рядок Y = (y 1 , y 2 , ..., y m ), яка максимізує лінійну функцію f = YA 0 і задовольняє обмеженням
YA> З (1.1)
Сформулюємо вихідну завдання. Визначити матрицю-стовпець X = (x 1 , x 2 , ..., x n ), яка мінімізує лінійну функцію Z = СХ і. задовольняє обмеженням
AX = A0, Х> 0 (1.2)
Як у вихідній так і в двоїстої задачах А = (a ij ) - матриця коефіцієнтів системи обмежень, A 0 = (b 1 , b 2 , ..., b m) - матриця-стовпець, C = (c 1 , c 2 , ..., c n ) - Матриця-рядок. Теорема подвійності встановлює зв'язок між оптимальними планами пари двоїстих задач.
Теорема подвійності говорить: якщо з пари двоїстих завдання одне володіє оптимальним планом, те й інша має рішення, причому для екстремальних значень лінійних функцій виконується співвідношення minZ = maxf. Якщо лінійна функція однієї з задач не обмежена, то інша не має рішення
Доказ.
Будемо вважати, що вихідна задача має оптимальний план. План визначений симплексним методом. Можна вважати, що...
