Xreferat.com » Рефераты по информатике и программированию » Рішення задач цілочисленного програмування

Рішення задач цілочисленного програмування

обмеження, 2) лічильник r, що відповідає номеру проведеної великої ітерації. Позначимо x*(Јr, C) оптимальне рішення (Јr, C) – задачі. Помітимо, що позначення (Јr, C) – задача, еквівалентне (Јr, C), уведено в блок-схемі для зручності запису.

При деяких умовах вдається довести теорему про кінцівку першого алгоритму Гомори, що ми приведемо без доказу.

Теорема. Нехай множина оптимальних планів задачі (Ј0, C) обмежено й виконуються наступні умови:

1) сi – цілі коефіцієнти цільової функції F(x) (i =1,2,…,n),рядок цільової функції в симплексній таблиці враховується при виборі рядка для побудови правильного відсікання;

2) справедливо одне із двох тверджень: або цільова функція Рішення задач цілочисленного програмування обмежена знизу на Сo, або задача (Јц, C) має хоча б один план х'.

Тоді перший алгоритм Гомори вимагає кінцевого числа більших ітерацій.


4. Другий алгоритм Гомори


Другий алгоритм Р. Гомори призначається для рішення задач, у яких вимога цілочисленності накладена на деякі змінні (зокрема й на все). Ми його розглянемо стосовно до задач частково цілочисленного типу, розуміючи, що обчислювальна схема буде справедливої й для задач, повністю цілочисленних.

Нехай в області, певної умовами:


Рішення задач цілочисленного програмування (20)

Рішення задач цілочисленного програмування (21)

Рішення задач цілочисленного програмування – цілі, Рішення задач цілочисленного програмування (22)


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


Рішення задач цілочисленного програмування (23)


Метод рішення задачі (20–23) ґрунтується на тій же ідеї, що й метод рішення повністю цілочисленних задач. А саме: будується область Јk, що при k = 0 визначається умовами (20–21); вирішується отримана при цьому задача лінійного програмування (20–21, 23). Якщо задача (20–21, 23) виявляється розв'язної, то отримане оптимальне рішення її аналізується на допустимість для вихідної задачі цілочисленного програмування (20–23). Якщо знайдене рішення виявляється целочисленным, то одночасно воно буде оптимальним для (20–23). Якщо оптимальне рішення (Јk, C) – задачі виявляється неприпустимим для вихідної задачі (20–23), те здійснюється побудова правильного відсікання й перехід до рішення нової задачі,

Другий алгоритм Р. Гомори формулюється у вигляді наступної теореми:

Теорема. Нехай х(Јk, C) – оптимальне рішення (Јk, C) – задачі, Рішення задач цілочисленного програмування – елементи відповідної йому симплексної таблиці. Якщо Рішення задач цілочисленного програмування – неціле Рішення задач цілочисленного програмування, то


Рішення задач цілочисленного програмування (24)

Рішення задач цілочисленного програмування – ціле, (25)


де

Рішення задач цілочисленного програмування (26)


визначає правильне відсікання. Блок-схема другого алгоритму Р. Гомори аналогічна блок-схемі першого алгоритму Р. Гомори й відрізняється лише правилом побудови коефіцієнтів правильного відсікання.

Правило побудови правильного відсікання

Нехай x(Јk, C) не задовольняє умові цілочисленності, Рішення задач цілочисленного програмування – елементи симплексної таблиці, що відповідає отриманому оптимальному рішенню (Јk, C) – задачі. Виберемо i0=min {i | i О (1, 2,…,n),xi0k–неціле} і будуємо правильне відсікання по формулах (24 – 26).

Умови кінцівки другого алгоритму Гомори:

1) Цільова функція F(x) задовольняє умові цілочисленності. Це враховується при виборі рядка k для побудови правильного відсікання.

2) Виконано принаймні одне із двох умов:

2') цільова функція обмежена знизу на багатогранній множині Ј= Ј0;

2») задача (Ј0ц, C) має принаймні один план.

За допомогою другого алгоритму Гомори можна (у випадку n1=n) вирішувати й повністю цілочисленну задачу лінійного програмування. Однак у цьому випадку немає підстав для порівняння ефективності другого й першого алгоритмів Гомори.


5. Алгоритм Дальтона й Ллевелина


Другий алгоритм Гомори має справа із частково цілочисленними задачами лінійного програмування. Дальтон і Ллевелин розглядають широкий клас задач - частково дискретні задачі лінійного програмування й стосовно до них модифікують другий алгоритм Гомори.

Нагадаємо, що рішенням задачі дискретного програмування будемо називати вектор, координати якого належать Јц області виду:


Рішення задач цілочисленного програмування (27)

Рішення задач цілочисленного програмування (28)

Рішення задач цілочисленного програмування (29)


і максимізує значення функції


Рішення задач цілочисленного програмування (30)


Будемо припускати, що Рішення задач цілочисленного програмування, тобто Рішення задач цілочисленного програмування і є наперед заданими числами.

Теорема. Нехай x(Јk, C) – оптимальне рішення задачі (27–28, 30), Рішення задач цілочисленного програмування – елементи симплексної таблиці, що відповідає йому.

Якщо x(Јk, C) є неприпустимим рішенням задачі (27–30) і Рішення задач цілочисленного програмування, тоді, використовуючи i-ю рядок симплексної таблиці, можна побудувати відсікання, що володіє властивістю правильності по формулах:


Рішення задач цілочисленного програмування (31)

Рішення задач цілочисленного програмування (32)


де

Рішення задач цілочисленного програмування

Рішення задач цілочисленного програмування (33)


Доказ. Перевіримо спочатку умову відсікання. Нехай в оптимальному рішенні x(Јk, C) координата Рішення задач цілочисленного програмування не задовольняє умові (29). Покажемо, що в цьому випадку вектор х(Јk, C) не задовольняє умовам (31, 32). Оскільки Nk – множина індексів небазисних змінних xi, які в оптимальному рішенні дорівнюють нулю, то рівність (31) приймає вид Рішення задач цілочисленного програмування і буде негативним відповідно до умови теореми. Отже, Рішення задач цілочисленного програмування, тобто умова відсікання не виконується.

Перевіримо умову правильності. Для цього покажемо, що будь-яке припустиме рішення задачі (27-30) задовольняє умовам (31, 32).

Запишемо розкладання для координати припустимого рішення задачі (27-30) по небазисним змінним


Рішення задач цілочисленного програмування (34)


і розглянемо два випадки: a) Рішення задач цілочисленного програмування; б) Рішення задач цілочисленного програмування. Уведемо позначення:


Рішення задач цілочисленного програмування


і представимо (34) у вигляді


Рішення задач цілочисленного програмування

де


Рішення задач цілочисленного програмування


Очевидно, Рішення задач цілочисленного програмування тому що Рішення задач цілочисленного програмування.

Розглянемо випадок а): Рішення задач цілочисленного програмування, або що однаково, Рішення задач цілочисленного програмування.

Звідси Рішення задач цілочисленного програмуванняАле Рішення задач цілочисленного програмуванняРішення задач цілочисленного програмуваннятому


Рішення задач цілочисленного програмування (35)


Помножимо обидві частини (35) на ненегативну величину Рішення задач цілочисленного програмування й складемо з ненегативною величиною Рішення задач цілочисленного програмування:


Рішення задач цілочисленного програмування (36)


Розглянемо випадок б): Рішення задач цілочисленного програмування або, що однаково, Рішення задач цілочисленного програмування Тому що по визначенню Рішення задач цілочисленного програмування, то Рішення задач цілочисленного програмування Помножимо обидві частини нерівності Рішення задач цілочисленного програмування на ненегативну величину Рішення задач цілочисленного програмування й на -1, одержимо Рішення задач цілочисленного програмування. Додаючи до отриманого вираження нерівність Рішення задач цілочисленного програмування, одержимо


Рішення задач цілочисленного програмування (37)

Таким чином, в а) і в б) випадках прийшли до тому самому нерівності (36) і (37). Користуючись раніше уведеними позначеннями, їх можна записати


Рішення задач цілочисленного програмування (38)


Формула (38) визначає правильні відсікання. Порівнюючи її з вираженням (31–32), доходимо висновку, що коефіцієнти Рішення задач цілочисленного програмуваннявизначаються в такий спосіб:


Рішення задач цілочисленного програмування


Теорема доведена.

Алгоритм Дальтона - Ллевелина може бути описаний у такий спосіб.

1. Вирішується (Јk, C) – задача (27–30) (спочатку k = 0). Нехай x(Јk, C), k = 0, 1, 2,…оптимальне рішення (Јk, C) – задачі, Рішення задач цілочисленного програмування – симплексна таблиця.

2. Перевіряється умова допустимості по всіх координатах оптимального вектора рішення х(Јk, C) (Јk, C) – задачі. Якщо умова допустимості виконується, то отримане рішення є оптимальним рішенням вихідної задачі (27-30). Якщо умова допустимості не виконується хоча б по одній координаті, здійснюється перехід до 3.

3. Нехай Рішення задач цілочисленного програмування не задовольняє умові допустимості. Тоді вибирається


i0 = min {i| 1<i<n1, хj0k – не задовольняє (29)}.

4. Для обраного номера i=i0 будується правильне відсікання, тобто вводиться додаткова змінна


Рішення задач цілочисленного програмування


де Рішення задач цілочисленного програмуваннявизначається формулою (33),

5. Додаємо лінійне обмеження, що визначає правильне відсікання, до умов (Јk, C) – задачі й одержуємо нову (Јk+1, C) – задачу. Думаючи k = k + 1, переходимо до п. 1.

Приведемо без доказу теорему про кінцівку алгоритму.

Теорема. Якщо: коефіцієнти цільової функції дискретні; F(x) обмежена знизу на багатогранній множині Ј; задача (Ј, C) має принаймні одне рішення; вибір рядка для побудови правильного відсікання виробляється за правилом мінімального номера й (Јk, C) – задачі вирішуються методом послідовного уточнення оцінок, то алгоритм Дальтона й Ллевелина сходиться.


6. Алгоритм Данцига


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

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

Максимізувати


Рішення задач цілочисленного програмування (39)

при умовах


Рішення задач цілочисленного програмування (40)

Рішення задач цілочисленного програмування (41)

Рішення задач цілочисленного програмування – цілі, Рішення задач цілочисленного програмування (42)


Ранг матриці Рішення задач цілочисленного програмування вважаємо рівним m.

Теорема. Нехай x(Јr, C)=xr є оптимальним опорним планом задачі (Јr, C) і xr не задовольняє умові цілочисленності, Nr – множина індексів, що нумерують небазисні змінні, відповідні xr.

Тоді нерівність


Рішення задач цілочисленного програмування (43)


є правильним відсіканням.

Правильне відсікання, що відтинає нецілочисленний оптимум x(Јr, C) задачі (Јr, C), можна записати в такий спосіб:


Рішення задач цілочисленного програмування

Рішення задач цілочисленного програмування – ціле.


Помітимо, що кожна із знову змінних Рішення задач цілочисленного програмування однозначно визначається завданням змінних Рішення задач цілочисленного програмування, так що Рішення задач цілочисленного програмування.

Позначимо через Рішення задач цілочисленного програмування упорядковані в порядку зростання компоненти Рішення задач цілочисленного програмування плану x задачі (39) – (41), так що

Рішення задач цілочисленного програмування (44)


Покладемо


Рішення задач цілочисленного програмування (45)


Лема. Якщо для деякого плану x задачі (39) - (41)


Рішення задач цілочисленного програмування, (46)


те


Рішення задач цілочисленного програмування (47)


Доказ проведемо по індукції. Спочатку доведемо, що


Рішення задач цілочисленного програмування (47ў)


По визначенню


Рішення задач цілочисленного програмування (48)


Тому що ранг матриці Рішення задач цілочисленного програмування дорівнює m, те

Рішення задач цілочисленного програмування

де Рішення задач цілочисленного програмування – число елементів множини Рішення задач цілочисленного програмування. З визначення чисел Рішення задач цілочисленного програмування одержуємо

Рішення задач цілочисленного програмування (49)

Рішення задач цілочисленного програмування (50)


З (48), (49), (50) і (46) маємо


Рішення задач цілочисленного програмування


Лема доведена при р=1.

Тепер допустимо, що лема вірна при Рішення задач цілочисленного програмування, і доведемо неї при Рішення задач цілочисленного програмування:


Рішення задач цілочисленного програмування


Лема доведена.

Користуючись лемою, доведемо дві теореми.

Теорема 1. Якщо кожний оптимальний план задачі (39) – (42) містить не менш (m+2) позитивних компонентів, то алгоритм Данцига не буде кінцевим.

Доказ. Допустимо, що на s-й ітерації алгоритму Данцига вийде шуканий оптимальний план Рішення задач цілочисленного програмування. Розглянемо числа


Рішення задач цілочисленного програмування (51)


Всі вони цілі й серед них повинне бути (n-m) нулів – це небазисні змінні Рішення задач цілочисленного програмування. Крім того, за умовою серед чисел Рішення задач цілочисленного програмування, повинне бути принаймні (m+2) позитивні числа, тобто не більше чим (n-m-2) нулів.

По визначенню чисел Рішення задач цілочисленного програмування звідси треба, що


Рішення задач цілочисленного програмування


а тому що Рішення задач цілочисленного програмування повинне бути цілим, те


Рішення задач цілочисленного програмування (52)


Але по визначенню чисел Рішення задач цілочисленного програмування


Рішення задач цілочисленного програмування (53)


З (52) одержуємо


Рішення задач цілочисленного програмування (54)


і по лемі


Рішення задач цілочисленного програмування (55)


З (52), (53) і (55) треба, що серед чисел (51) принаймні [1+(m+1)+s] = [m+2+s] позитивних, а отже, не більше чим [n+s – (m+2+s)] = (n-m-2) нулів. Але вище було відзначено, що серед чисел (51) повинне бути (n-m) нулів. Вийшло протиріччя. Теорема 1 доведена.

Наслідок (з теореми 1). Для того щоб алгоритм Данцига був кінцевим, необхідно, щоб шуканий оптимальний план лежав на ребрі багатогранної множини (40) - (41) (передбачається, що задача (39) - (41) невиродженна).

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

Максимізувати


Рішення задач цілочисленного програмування (56)


при умовах


Рішення задач цілочисленного програмування (57)

Рішення задач цілочисленного програмування (58)

Рішення задач цілочисленного програмування (59)

Рішення задач цілочисленного програмування – ціле, Рішення задач цілочисленного програмуванняРішення задач цілочисленного програмуванняРішення задач цілочисленного програмування (60)


А це важливий клас задач.

Однак наведене в наслідку необхідна умова кінцівки алгоритму Данцига не є достатнім. Дійсно, має місце наступна

Теорема 2. Якщо для деякого оптимального плану x' задачі (39) - (42) і деякого плану x» задачі (39) - (41) мають місце нерівності


Рішення задач цілочисленного програмування (61)

и


Рішення задач цілочисленного програмування (62)

те алгоритм Данцига не буде кінцевим.

Доказ. Допустимо, що алгоритм Данцига кінцевий. Тоді з (61) треба, що крапка x» була відсічена на якійсь (скажемо, р-й) ітерації, так що


Рішення задач цілочисленного програмування (63)


Але з (62) і леми одержимо


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: