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

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

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

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


Реферат на тему:
Цілочислові задачі лінійного програмування. Деякі з Основних методів їх розв'язування та аналізу.
План.
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 визначаються з наступних співвідношенні:
1) для хj, що можуть приймати не цілочислові значення,
при ?*ij ?0,
при ?*ij<0; (38)
2) для 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)
Таблиця

 
 

Цікаве

Загрузка...