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

План.
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<0; (38)
для xj, що можуть приймати тільки цілочислові значення,
при

при (39)
З викладеного вище випливає, що процесі визначення оптимального плану задачі цілочислового програмування методом Гоморі включає наступні основні етапи:
1. Використовуючи симплексний метод, знаходять рішення задачі (32) — (34) без обліку вимоги цілочисловості перемінних.
2. Складають додаткове обмеження для перемінної, котра в оптимальному плані задачі (32) — (34) має максимальне дробове значення, а в оптимальному плані задачі (32) — (35) повинна бути цілочисловою.
3. Використовуючи двоїстий симплекс-метод, знаходять рішення задачі, що виходить із задачі (32) — (34) у результаті приєднання додаткового обмеження.
4. У разі потреби складають ще одне додаткове обмеження і продовжують ітераційний процесі до одержання оптимального плану задачі (32) — (35) чи встановлення її нерозв'язності.
2.49. Методом Гоморі знайти максимальне значення функції
F = 3х1+2хг (40)
при умовах
(41)
(42)
хj – цілі (43)
Дати геометричну інтерпретацію розв’язку задачі.
Розв’язання. Для визначення оптимального плану задачі (40) — (43) спочатку знаходимо оптимальний план задачі (40) — (42) (табл. 2.28).


Т а б л и ц я 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)
не є оптимальним планом задачі (40) — (43) (числа 19/2 і 7/2 — дробові), те вводиться додаткове обмеження .Виключаючи з нього х3 і х4 способом підстановки замість них відповідних значень з рівнянь системи обмеження (41), одержимо . Цій нерівності відповідає напівплощина, обмежена прямої х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 с.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать