Зміст практичного заняття та вихідні дані до його виконання

САМОСТІЙНА РОБОТА №1

ДВОЇСТІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

Стисла теоретична довідка

Кожній задачі лінійного програмування (вона називається прямою задачею)відповідає двоїста.Формування двоїстої задачівиконується за певними правилами.

Наприклад, якщо пряма задача має вигляд:

максимізувати Z=c₁x₁+c₂x₂+...+c_nx_n⇒max

за умови обмежень на змінні

то двоїста задача записується наступним чином:

мінімізувати F=b₁y₁+b₂y₂+...+b_m y_m⇒min

за умови обмежень на змінні

4

Двоїста задача лінійного програмування утворюється з прямої задачі за наступними правилами:

а ) кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі;

б) кожній змінній прямої задачі відповідає обмеження двоїстої задачі. Кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі;

в) якщо у прямій задачі цільова функція максимізується, то у двоїстій – мінімізується і навпаки;

г) коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі;

д) вільними членами системи обмежень двоїстої задачі є коефіцієнти при змінних прямої задачі.

Двоїсті пари задач лінійного програмування можуть бути

симетричними та несиметричними.У симетричних задачахобмеження прямої та двоїстої задачі представлені нерівностями, а змінні можуть набувати тільки невід’ємних значень. У несиметричних задачах обмеження прямої задачі можуть бути подані рівняннями, а двоїстої – лише нерівностями, при цьому змінні двоїстої задачі можуть набувати будь-яких (у тому числі і від’ємних значень).

У таблиці 1.1 наведені можливі форми прямих та двоїстих задач лінійного програмування.

Зв’язок між прямою та двоїстою задачами визначається наступними теоремами двоїстості.

Теорема 1. Якщо одна з пари двоїстих задач має оптимальнийплан, то інша задача теж має оптимальний план, причому значення цільових функцій обох задач співпадають. Якщо ж цільова функція однієї задачі є необмеженою, то друга задача немає жодного допустимого рішення.

Теорема 2. Якщо в результаті рішення прямої задачі її деякеі-теобмеження виконується як строга рівність, то відповідний і-й компонент оптимального плану двоїстої задачі дорівнює нулю.

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

5

Таблиця 1.1 – Можливі форми прямої та двоїстої задач

Якщо пряма задача лінійного програмування має оптимальний план Х^* , визначений симплекс-методом , то оптимальний план двоїстої задачі визначається співвідношенням

Y^*=C′⋅D⁻¹

6

де C′ – вектор-рядок, що складається з коефіцієнтів цільової функції прямої задачі при змінних, які є базисними в оптимальному плані;

D⁻¹–матриця,обернена до матриціD,складеної з базиснихвекторів оптимального плану, компоненти яких взято з початкового опорного плану задачі.

Зміст практичного заняття та вихідні дані до його виконання

Для пакування виробів на складі готової продукції підприємства використовуються однотипні рулони паперу, які необхідно розрізати на заготовки двох видів (І та ІІ) у заданій кількості. Кількість заготовок, що отримують за чотирма (1–4) різними варіантами розкрою рулонів та відходи паперу за цими варіантами подані у вигляді таблиці 1.2.

Таблиця 1.2 – Варіанти розкрою рулонів паперу

Сформулювати пряму та двоїсту задачі побудови оптимального плану розкрою рулонів паперу. Вирішити двоїсту задачу графічним методом , та знайти рішення прямої задачі, використовуючи другу теорему двоїстості.

Вихідні дані до виконання роботи по варіантах наведені у таблиці 1.3.

Таблиця 1.3 – Вихідні дані до виконання самостійної роботи 1

7

Продовження таблиці 1.3.

Приклад виконання завдання

Розглянемо приклад виконання завдання за вихідних даних, наведених у таблиці 1.4.

Таблиця 1.4 – Вихідні дані задачі

8

Розв’язок.

Складемо математичну модель задачі. Нехай х_і ( i=1,4 ) кількість рулонів, що розкроюються за і-м варіантом. Тоді, за умовою задачі, необхідно мінімізувати відходи від розкрою паперу

Z=25x₁+15x₂+25x₃+12x₄⇒min

при обмеженнях назаданий план виходу заготовок кожного виду

5x₁+ 4x₃+ 2 x₄≥80 ; 7x₂+x₃+ 4 x₄≥ 60 .

– на невід’ємність змінних задачі

x₁≥0;x₂≥0;x₃≥0;x₄≥0.

Запишемо для цієї прямої задачі двоїсту. Максимізувати

F=80y₁+60y₂⇒max,

при обмеженнях

5 y₁≤ 25 ;

7 y₂≤15 ;

4 y₁+y₂≤ 25 ; 2 y₁+ 4 y₂≤12 ; y₁≥0;y₂≥0.

Двоїста задача має дві незалежні змінні, тому може бути вирішена графічним методом. Рішення двоїстої задачі графічним методом наведено на рис. 1.1.

Оптимальне рішення двоїстої задачі досягається у точці перетину прямих

4 y₁+y₂≤ 25; 5 y₁≤ 25.

9

Рисунок 1.1 – Рішення двоїстої задачі графічним методом

Вирішивши цю систему рівнянь отримаємо оптимальний план двоїстої задачі: y₁=5 ; y₂=0,5 ; F_max = 430.

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

Підставимо оптимальні значення змінних двоїстої задачі до її системи обмежень та перевіримо, як виконуються обмеження цієї задачі:

5 ⋅5 = 25 ;

7 ⋅0,5 = 3,2 ≠ 15 ; 4 ⋅5 + 1 ⋅ 0,5 = 20,5 ≠ 25 _;

2 ⋅5 + 4 ⋅ 0,5 =12 ;

Таким чином бачимо, що друге та третє обмеження двоїстої задачі виконуються як нерівності. З цього на підставі другої теореми двоїстості робимо висновок, що друга та третя змінна оптимального плану прямої задачі дорівнюють нулю. Далі, оскільки всі компоненти оптимального плану двоїстої задачі є додатними, то обидва обмеження оптимального плану прямої задачі виконуються як строгі рівняння.

10

Покладаючи x₂=0 та x₃=0 у системі обмежень прямої задачі

та замінивши знаки нерівностей на знаки рівностей отримаємо систему рівнянь

5 x₁+ 2 x₄=80 ; 4 x₄= 60 .

Звідки знаходимо оптимальне рішення прямої задачі: x₁=10 ;

x₄=15;Z_min=430.

Таким чином, необхідно розкроїти 10 рулонів паперу за першим варіантом та 15 рулонів паперу за третім варіантом. При цьому мінімальна кількість відходів складе 430 см².

Контрольні запитання

1. У чому полягає сутність двоїстості у лінійному програмуванні ?

2. Які двоїсті задачі називають симетричними, а які – несиметричними ? У чому полягає їх відмінність ?

3. Як визначається кількість змінних та обмежень двоїстої задачі

у відповідності до прямої задачі ?

4 Сформулюйте теореми двоїстості.

5 Сформулюйте правила побудови двоїстих задач лінійного програмування.

6 Запишіть всі види прямих та двоїстих задач.

САМОСТІЙНА РОБОТА №2

ДВОЇСТИЙ СИМПЛЕКС-МЕТОД

Мета заняття:вивчення алгоритму рішення задач лінійногопрограмування двоїстим симплекс-методом.

Стисла теоретична довідка

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

11

початковому опорному плані задачі, але для задачі мінімізації необхідно, щоб всі коефіцієнти при змінних цільової функції були невід’ємними. Тобто, у стовпчику С вільних членів симплекс-таблиці

допустимі від’ємні значення базисних змінних,при цьому всі значення індексного рядка повинні бути невід’ємними.

Процедура двоїстого симплекс-методу полягає виконанні наступних кроків:

а) перевірка поточного опорного плану задачі наоптимальність.Якщо всі базисні змінні невід’ємні,то данийопорний план є оптимальнимрішенням задачі і процес рішення припиняється. Інакше виконують крок 2;

б) знаходження змінної для виключення з базису. Відшукують найменшу від’ємну базисну змінну. Рядок, що відповідає цій змінній називається провідним рядком , а базисна змінна, що відповідає цьому рядку, у наступному опорному плані задачі стане небазисною;

в) знаходження змінної для включення до базису. У

провідному рядку відшукують від’ ємні значення. Якщо не знайдено жодного від’ємного значення, то не існує жодного допустимого плану задачі і рішення припиняється. Якщо від’ємних значень декілька, то вибирається стовпчик, у якому досягається найменше за абсолютною величиною відношення числа з індексного рядка до цих значень. Знайдений таким чином стовпчик називається провіднимстовпчиком,а вільна змінна,що відповідає цьому стовпчику,унаступному опорному плані стане базисною. На перетині провідного рядка та провідного стовпчика знаходиться провідний елемент.

г) побудова нового опорного плану задачі. Виконується аналогічно симплекс-перетворенням звичайного симплекс-методу.

Зміст практичного заняття та вихідні дані до його виконання

Для перевезення вантажів за трьома маршрутами (І–ІІІ) автотранспортне підприємство може використати чотири типи автомобілів (ГАЗ-53, ЗІЛ-4315, КАМАЗ-5320, КАМАЗ-53212). Мінімальний змінний обсяг перевезення вантажів на маршрутах, продуктивність транспортних засобів та витрати на експлуатацію автомобілів кожного типу наведені у таблиці 2.1.

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

Вихідні дані для виконання роботи по варіантах наведені у таблиці 2.2.

Таблиця 2.2 – Вихідні дані до виконання самостійної роботи 2

13

Продовження таблиці 2.2

Приклад виконання завдання

Розглянемо приклад виконання завдання для вихідних даних, заданих у таблиці 2.3.

Таблиця 2.3 – Вихідні дані (приклад)

використовуються для виконання перевезень. Тоді економіко-математична модель задачі матиме вигляд:

14

мінімізувати змінні витрати на експлуатацію автомобілів

Z=175x₁+210x₂+250x₃+275x₄⇒min,

при обмеженнях на планові мінімальні обсяги перевезень

15 x₁+ 19 x₂+ 24 x₃+ 26 x₄≥ 250 ; 8 x₁+ 10 x₂+ 11x₃+ 14 x₄≥120 ; 12 x₁+ 14 x₂+ 18 x₃+ 21x₄≥175 ;

та умову невід’ємності змінних задачі

x₁≥0;x₂≥0;x₃≥0;x₄≥0.

Для застосування симплекс-методу зведемо задачу доканонічного виду:

мінімізувати

Z=175x₁+210x₂+250x₃+275x₄⇒min,

при обмеженнях

15 x₁+ 19 x₂+ 24 x₃+ 26 x₄−x₅= 250 ; 8 x₁+ 10 x₂+ 11x₃+ 14 x₄−x₆=120 ; 12 x₁+ 14 x₂+ 18 x₃+ 21x₄−x₇=175 ;

x₁≥0;x₂≥0;x₃≥0;x₄≥0;x₅≥0;x₆≥0;x₇≥0.

Початкове базисне рішення

x₁=0;x₂=0;x₃=0;x₄=0;x₅=−250;x₆=−120;x₇=−175

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

15

−15 x₁− 19 x₂− 24 x₃− 26 x₄+x₅=−250 ;−8 x₁− 10 x₂− 11x₃− 14 x₄+x₆=−120 ; −12 x₁− 14 x₂− 18 x₃− 21x₄+x₇=−175 ;

Складемо початкову симплекс-таблицю (таблиця 2.4).

Таблиця 2.4 – Початкова симплекс-таблиця

Оскільки у базисі наявні від’ємні значення, план не є оптимальним. Вибираємо для виключення з базису змінну x₅ , що має найменше від’ємне значення. Переглядаємо рядок x₅ і для всіх стовпчиків, що містять від ’ємні значення знаходимо відношення елементу у індексному рядку до цих значень. Маємо:

стовпчик x₁ : 175/(–15) = –11,67; стовпчик x₂ : 210/(–19) = –11,05; стовпчик x₃ : 250/(–24) = –10,42; стовпчик x₄ : 275/(–26) = –10,58.

Найменше за абсолютною величиною значення досягається у стовпчику x₃ , тому цей стовпчик буде провідним, а змінну x₃ включаємо до базису.

Проводячи звичайні симплекс-перетворення отримуємо наступний опорний план задачі (таблиця 2.5).

Таблиця 2.5 – Новий опорний план задачі

16

Цей опорний план задачі не є оптимальним, оскільки в базисі присутня від’ємна змінна x₆. Провідним рядком на цій ітерації буде рядок x₆ , провідним стовпчиком – стовпчик x₄ (для нього досягається найменше за абсолютною величиною відношення значення індексного рядка до значення у рядку x₆ : (4,167)/(–2,083) = –2). Новий опорний план задачі показаний у таблиці 2.6.

Таблиця 2.6 – Оптимальний план задачі

КАМАЗ-5320. При цьому змінні витрати на експлуатацію парку складуть приблизно 2615 грн. Зауважимо, що зважаючи на достатньо великі значення змінних задачі, округлення їх до цілого числа є виправданим.

Контрольні запитання

1. Які умови у задачі лінійного програмування повинні бути виконані для застосування при її рішенні двоїстого симплекс-методу ?

2. Сформулюйте ознаку оптимальності опорного плану при рішенні задачі двоїстим симплекс-методом.

3. Як у двоїстому симплекс-методі обирається змінна, що включається до базису та змінна, що виключається з базису ?

4. Викладіть двоїстий симплекс-алгоритм.

17

САМОСТІЙНА РОБОТА №4