Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Kursovik_ISPукр.doc
Скачиваний:
5
Добавлен:
17.11.2018
Размер:
352.77 Кб
Скачать

Зміст:

1. Двойственность в линейном программировании 2

1.1. Несиметричні двоїсті задачі. Теорема двоїстості. 3

1.2. Симетричні двоїсті задачі 8

1.3.Види математичних моделей двоїстих задач 10

3. Алгоритм розв’язку двоїстим симплексим методом. 21

1. Двойственность в линейном программировании

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

Зв'язок вихідної і двоїстої задач полягає в тому, що коефіцієнти Cj функції мети вихідної завдання є вільними членами системи обмежень двоїстої задачі, вільні члени Bi системи обмежень вихідної завдання служать коефіцієнтами функції мети двоїстої завдання, а матриця коефіцієнтів системи обмежень двоїстої задачі є транспонованої матрицею коефіцієнтів системи обмежень вихідної задачі. Рішення двоїстої задачі може бути отримано з рішення вихідної і навпаки.

Як приклад розглянемо завдання використання ресурсів. Підприємство має т видів ресурсів у кількості bi (i = 1, 2, ..., m) одиниць, з яких виробляється n видів продукцій. Для виробництва 1 од. i-й продукції витрачається aij од. t-гo ресурсу, а її вартість становить Cj од. Скласти план випуску продукції, що забезпечує її максимальний випуск у вартісному вираженні. Позначимо через xj (j = 1,2, ..., n) кількість од. j-й продукций, Тоді вихідне завдання сформулюємо так.

Знайти вектор Х =(x1, x2, …, xn), котрий задовольняє обмеженням

a11x1 + a12x2 + … + a1nxn  b1,

a21x1 + a22x2 + … + a2nxn  b2, xj  0 (j =1,2, ..., n)

…………………………………

am1x1 + am2x2 + … + amnxn  bm,

і доставляє максимальне значення лінійної функції

Z = C1x1 + C2x2 + … + Cnxn,

Оцінимо ресурси, необхідні для виготовлення продукції. За одиницю вартості ресурсів приймемо одиницю вартості своєї продукції. Позначимо через уi (j = 1,2, ..., m) вартість одиниці i-го ресурсу. Тоді вартість всіх витрачених ресурсів, що йдуть на виготовлення одиниці j-й продукції, дорівнює . Вартість витрачених ресурсів не може бути менше вартості остаточного продукту, тому має виконуватися нерівність  Cj, j =1,2, ..., n. Вартість усіх наявних ресурсів виразиться величиною . Отже, двоїсту задачу можна сформулювати наступним чином.

Знайти вектор Y =(y1, y2, …, yn), котрий задовольняє обмеженням

a11y1 + a12y2 + … + am1ym  C1,

a12y1 + a22y2 + … + am2ym  C2, yj  0 (i =1,2, ..., m)

…………………………………

a1ny1 + a2ny2 + … + amnym  Cm,

і доставляє мінімальне значення лінійної функції

f = b1y1 + b2y2 + … + bmym.

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

Вихідне завдання. Скільки і якої продукції xj (j = 1,2, ..., n) необхідно зробити, щоб при заданих вартостях Cj (j = 1,2, ..., n) одиниці продукції і розмірах наявних ресурсів bi (i = 1 , 2, ..., n) максимізувати випуск продукції у вартісному вираженні.

Двоїста задача. Яка повинна бути ціна одиниці кожного з ресурсів, щоб при заданих кількостях ресурсів bi і величинах вартості одиниці продукції Ci мінімізувати загальну вартість затрат?

Змінні уi називаються оцінками або обліковими, неявними цінами.

Багато задач лінійного програмування спочатку ставляться як вихідних чи двоїстих задач, тому має сенс говорити про пару двоїстих задач лінійного програмування.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]