Реферат на тему:
Цілочислові задачі лінійного програмування. Деякі з Основних методів їх
розв’язування та аналізу.
План.
1. визначення оптимального плану задачі цілочислового програмування.
2. Метод Гоморі
3. приклади розв’язування задач.
4. Література
. Визначення оптимального плану задачі цілочислового програмування.
Розглянемо задачі цілочислового програмування, у яких як цільова
функція, так і функції в системі обмеженні є лінійними. У зв’язку з цим
сформулюємо основну задачу лінійного програмування, у якій перемінні
можуть приймати тільки цілі значення. У загальному виді цю задачу можна
записати так: знайти максимум функції.
(32)
при умовах
(33)
(34)
(35)
Якщо знайти рішення задачі (32) — (35) симплексним методом, то воно може
позначитися як цілочисловим, так і немає (прикладом задачі лінійного
програмування, рішення якої завжди є цілочисловим, служить транспортна
задача). У загальному ж випадку для визначення оптимального плану задачі
(32) — (35) вимагаються спеціальні методи. В даний час існує кілька
таких методів, з яких найбільш відомим є метод Гоморі, в основі якого
лежить описаними вище симплексний метод.
М е т о д Г о м о р і. Перебування рішення задачі цілочислового
програмування методом Гоморі починають з визначення симплексним методом
оптимального плану задачі (32) —(34) без обліку цілочисловості змінних.
Після того як той план знайдений, переглядають його компоненти. Якщо
серед компонентів немає дробових чисел, то знайденими план є оптимальним
планом задачі цілочислового програмування (32) —(35). Якщо ж в
оптимальному плані задачі (32) — (34) перемінна хј приймає дробове
значення, то до системи рівнянні (33) додають нерівність
(36)
і знаходять рішення задачі (32) — (34), (36).
У нерівності (36) ?*ij і bi* — перетворені вихідні величини ?ij і bi,
значення яких узяті з останньої симплекса-таблиці, а f(?*ij) і f (b*ij)
— дробові частини чисел (під дробовою частиною деякого числа ?
розуміється найменше ненегативне число b таке, що різниця між ? і b є
ціле). Якщо в оптимальному плані задачі (32) — (34) дробові значення
приймають трохи перемінних, то додаткова нерівність (36) визначається
дробовою найбільшою частиною.
Якщо в знайденому плані задачі (32) — (34), (36) перемінні приймають
дробові значення, то знову додають, одне додаткове обмеження процесі
обчисленні повторюють. Проводячи кінцеве число ітерації, або одержують
оптимальний план задачі цілочислового програмування (32) — (35), або
встановлюють її нерозв’язність.
Якщо вимога цілочисловості (35) відноситься лише до деяким перемінної,
то також задачі називаються – частково цілочисловими. Їхнє рішення також
знаходять послідовним рішенням задач, кожна з який виходить з
попередньої за допомогою введення додаткового обмеження. У цьому випадку
таке обмеження має вид
(37)
де ?ij визначаються з наступних співвідношенні:
для хj, що можуть приймати не цілочислові значення,
при ?*ij ?0,
при ?*ijТ а б л и ц я 2.28 і Базис С5 Р0 3 2 0 0 0 Р1 Р2 Р3 Р4 Р5 1 Р3 0 13 1 1 1 0 0 2 Р4 0 6 1 -1 0 1 0 3 Р5 0 9 -3 1 0 0 1 4 0 - 3 -2 0 0 0 1 Р3 0 7 0 2 1 -1 0 2 Р4 3 6 1 -1 0 1 0 3 Р5 0 27 0 -2 0 3 1 4 18 0 -5 0 3 0 І Р2 2 7/2 0 1 1/2 -1/2 0 2 Р1 3 19/2 1 0 1/2 1/2 0 3 Р5 0 34 0 0 1 2 1 4 71/2 0 0 5/2 1/2 0 Як бачимо з табл. 2.28, знайдений оптимальний план Х = (19/2; 7/2; 0; 0; 10) задачі (40) —(42) не є оптимальним планом задачі (40) —(43), оскільки два компоненти x1 і х2 мають не цілочислові значення. При цьому дробові частини цих чисел рівні між собою. Тому для однієї з цих змінних складається додаткове обмеження. Складемо, наприклад, таке обмеження для перемінної х2. З останньої симплекс-таблиці (табл. 2.28) маємо x2+(1/2)x3-(1/2)x4=7/2. Таким чином, до системи обмежень задачі (40)—(42) додаємо нерівність f(1)x2+f(1/2)x3+f(-1/2)x4?f(7/2), чи (1/2)x3+(1/2)x4?1/2 x3+x4?1 (44) Таблиця 2.29 1 Базис С5 Р0 3 2 0 0 0 0 Р1 Р2 Р3 Р4 Р5 Р6 1 Р2 2 7/2 0 1 1/2 -1/2 0 0 2 Р1 3 19/2 1 0 1/2 1/2 0 0 3 Р5 0 34 0 0 1 2 1 0 4 Р6 0 -1 0 0 -1 -1 0 1 5 71/2 0 0 5/2 1/2 0 0 1 Р2 2 4 0 1 1 0 0 -1/2 2 Р1 3 9 1 0 0 0 0 1/2 3 Р5 0 32 0 0 -1 0 1 2 4 Р4 0 1 0 0 1 1 0 -1 5 35 0 0 2 0 0 1/2 Знаходимо тепер максимальне значення функції (40) при виконанні умови (41), (42) і (44) (табл. 2.29). З табл. 2.29 видно, що вихідна задача цілочислового програмування має оптимальний план Х* = (9; 4; 0; 1; 32). При цьому плані значення цільової функції дорівнює Fтак = 35. Дамо геометричну інтерпретацію розв’язку задачі. Областю припустимих рішень задачі (40) — (42) є багатокутник ОАВС (мал. 2.3). З мал. 2.3 видно, що максимальне значення цільова функція приймає в крапці З (19/2; 7/2), тобто що Х = = (19/2; 7/2; 0; 0; 34) є оптимальним планом. Це безпосередньо видно з табл. 2.28. Тому що Х = (19/2; 7/2; 0; 0; 34) . Цій нерівності відповідає напівплощина, обмежена прямої х1 =9, що відтинає від багатокутника ОАВСО трикутник ЕРС. Як видно з мал. 2.3, область» припустимого розв’язку отриманої задачі є багатокутник ОАВЕРО. У крапці Е (9; 4) цього багатокутника цільова функція даної задачі приймає максимальне значення. Тому що координати точки Е — цілі числа і невідомі х3, х4 і х5 приймають цілочислові значення при підстановці в рівняння (41) значення х1=9 і х2=4, те Х*= (9; 4; 0; 0; 32) є оптимальним планом задачі (40) — (43). Це випливає і з табл. 2.29. 2.50. Методом Гоморі знайти розв’язок задачі, що складається у визначенні максимального значення функції F= x1+4x2 (45) при умовах x1, x2 -цілі (48) Дати геометричну інтерпретацію розв’язку задачі. Розв’язання. Сформульовану задачу перепишемо так: знайти максимальне значення функції F= x1+4x2 (49) при умовах (50) (51) x1, x2 - цілі Задача (49) — (52) є частково цілочисловою, тому що перемінні х3 і х4 можуть приймати не цілочислові значення. Знаходимо симплексним методом рішення задачі (49) — (51) (табл. 2.30). Після II ітерації одержуємо оптимальний план даної задачі Х=(0; 4/3; 5; 0). При цьому плані змінна х2 прийняла не цілочислове значення. Тому необхідно перейти до нової Т а б л и ц я 2.30 і Базис С6, Р0 1 4 0 0 Р1 Р2 Р3 Р4 1 Р3 0 19/3 2 1 1 0 2 Р4 0 4 1 3 0 1 3 0 -1 - 4 0 0 1 Р3 0 5 5/3 0 1 -1/3 2 Р2 4 4/3 1/3 1 0, 1/3 3 16/3 1/3 0 0 4/3 задачі, додавши до системи обмеження (49)—(51) ще одне обмеження: (1/3)х1-(1/3)х4? 1/3, чи x1+x4-x5 = 1 (x5?0) (53) Знаходимо тепер розв’язок задачі, що складається у визначенні максимального значення функції (49) при умовах (50), (51) і (53). Дану задачу вирішуємо двоїстим симплекс-методом (табл. 2.31). Та б л и ц я 2.31 і Базис С5 Р0 1 4 0 0 0 Р1 Р2 Р3 Р4 Р5 1 Р3 0 5 5/3 0 1 -1/3 0 2 Р2 4 4/3 1/3 1 0 1/3 0 3 Р5 0 -1 - 1 0 0 -1 1 4 16/3 1/3 0 0 4/3 0 1 Р3 0 10/3 0 0 1 -2 5/3 2 Р2 4 1 0 1 0 0 1/3 3 Р1 1 1 1 0 0 1 -1 4 5 0 0 0 0 1/3 З табл. 2.31 видно, що X* =( 1; 1; 10/3; 0; 0) є оптимальним планом побудованої задачі. Тому що при цьому плані змінні х1 і х2 приймають цілі значення, то він також є оптимальним планом вихідної задачі (49)—(52). Дамо геометричну інтерпретацію розв’язку задачі. На мал. 2.4 показана область припустимих розв’язків задачі (49)—(51). З малюнка видно, що максимальне значення цільова функція приймає в точці А (0; 4/3), тобто що Х= (0; 4/3; 5; 0) є оптимальним планом задачі (49) — (51). У той же час Х=(0; 4/3; 5; 0) не є планом задачі (49) — (52), тому що змінна х2 приймає дробове значення. Тому вводимо Мал. 2.4 додаткове обмеження х1+х4?1, звідки, підставляючи замість х4 його значення з другого рівняння системи рівнянь (50) , одержуємо х2?1. Цій нерівності на мал. 2.4 відповідає площина, обмежена прямою х2=1, що відтинає від багатокутника СМВС трикутник ADE. В області ООЕВС знаходимо точку Е (1; 1), у якій функція (49) приймає максимальне значення. Тому що координати точки Е — цілі числа, те Х*= (1; 1; 10/3; 0) є оптимальним планом задачі (49) — (52). Це видно з табл.2.31. Література. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:КНЕУ, 2003.- 452 с. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут післядипломної освіти) “Інтелект - Захід”, 2004. – 448 с. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. – Вища школа, 1985-319с.,ст.270-274. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: „Рута”, 1998.-168 с. 18 16 14 12 10 8 6 4 2 0 -4 -6 -8 -10 -12 -14 -16 х2 -14 –12 –10 –8 –6 –4 –2 2 4 6 8 10 12 14 х1 В А С D F E C -3x1+x2=9 3x1+2x2=18 x1=9 x1-x2=6 x1+x2=13
Нашли опечатку? Выделите и нажмите CTRL+Enter
