WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Цілочислові задачі лінійного програмування. Деякі з Основних методів їх розв'язування та аналізу - Реферат

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

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.
Література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти) "Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.270-274.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для
Loading...

 
 

Цікаве