5. Цілісне програмування icon

5. Цілісне програмування




Скачати 303.78 Kb.
Назва5. Цілісне програмування
Дата06.09.2012
Розмір303.78 Kb.
ТипЗадача

5. Цілісне програмування


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

Задача називається цілком цілісною, якщо умова цілісності накладена на усі її перемінні; коли ця умова відноситься лише до деяким перемінним, задача називається частково цілісною. Якщо при цьому цільова функція і функції, що входять в обмеження, лінійні, то задача є лінійно цілісною.


5.1. Формулювання задачі лінійного цілісного програмування і її математичної моделі

Розглянемо один приклад такої задачі. Нехай має ряд неподільних предметів (цінностей) П1, П2, ... , Пn, що необхідно відвезти з небезпечного району. Відомі вартості цих предметів: с1, с2, ... , сn і їхньої ваги q1, q2, ... , qn. Кількість і вид предметів, що ми можемо відвезти, лімітується вантажопідіймальністю Q перевізних засобів. Потрібно з усього набору предметів вибрати найбільше цінний набір (із максимальною сумарною вартістю предметів), вага якого укладається в Q.

Введемо в розгляд перемінні xi, i=1;n, обумовлені умовою



Очевидно, що цільова функція, що необхідно максимізувати, имеет вид

.

Умова обмеження вантажопідіймальності запишеться у виді нерівності:

q1x1+q2x2+... +qnxnQ.

На перший погляд може показуватися, що вирішувати дану задачу треба як задачу лінійного програмування. Однак, знайдене рішення може виявитися не цілим, а дрібним, а значить нездійсненним (не можна завантажити в машину половину картини або третина рояля). Не можна й округляти отримані перемінні до найближчого з цілих чисел 0 або 1, тому що отримане в такий спосіб рішення може бути зовсім не оптимальним або не задовольняти вихідному обмеженню.

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


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

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

максимізувати L=7x1+9x2 при обмеженнях:



x1 і x2 - позитивні цілі.

Область припустимих рішень задачі з ослабленими обмеженнями, одержуваними шляхом відкидання цілісності перемінних, подане на мал.5.1.



Мал. 5.1.


Оптимальне значення цільових функції hmax=63 досягається в точці N із дрібними координатами х1=9/2; х2=7/2.

У основі методу площин , що відтиняють , лежить перетворення області рішень задачі з ослабленими обмеженнями в опуклий багатогранник, екстремальна точка якого є оптимальним рішенням вихідної цілісної задачі. При цьому всі припустимі цілісні рішення вихідної задачі повинні лежати усередині або на межі побудованого багатогранника. На мал.5.1. показане, як уведення двох додаткових обмежень дозволяє одержати нову точку з координатами х1=4; х2=3, що є оптимальним рішенням сформульованої вище задачі цілісного програмування. Додаткові обмеження введені таким чином, щоб область, відсічена від множини припустимих рішень ослабленої задачі, не містить точок із цілісними координатами, а в новій області припустимих значень, вершини, доторконня з відсіченою областю, мають цілісні координати (відсічена область на рис 5.1. заштрихована).

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

Наприклад, обмеження

,

необхідно записати у виді

,

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

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

Крок 2. Вводиться додаткове обмеження ( площина, щовідтиняє,), що породжує разом із вихідними обмеженнями нову задачу лінійного програмування. Якщо рішення нової задачі виявляється не цілісним, то крок 2 із новими обмеженнями повторюється, поки рішення не виявляється цілісним. При правильному введенні додаткових обмежень отримане цілісне рішення збігається з оптимальним рішенням вихідної задачі.

Проілюструємо метод площин , що відтиняють , на задачі, вирішеної вище графічним шляхом.

З ослабленими обмеженнями (без накладення умови цілісності перемінних) ця задача формулюється в такий спосіб:



Оптимальне рішення даної задачі, отримане симплексом-методом задається таблицею:

БП

х1

х2

х3

х4

Ріш. bi

x2

0

1

7/22

1/22

7/2

x1

1

0

-(1/22)

3/22

9/2

L

0

0





-63

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

Для вибору виробляючого рядка й одержання рівняння площини , що відтиняє , необхідно виконати ряд операцій.

Представимо, усі нецілісні значення базисних перемінних bi у виді

bi=[bi]+fi. (5.1.)

де [bi] - означає округлення до цілого найменшого числа, а fi=bi-[bi].

Як приклад у наведемо наступну таблицю


bi









-1

[bi]

3

0

-3

-1

-1

fi









0


Очевидно, що 0fi<1.

Правило. Тому що ефективність відсікання області припустимих значень, характеризується розмірами що відтиняється області, то в якості виробляючого рядка треба взяти ту, у якої значення fi максимально.

Для розглянутого приклада

і отже,

и.

Тому що , те в якості виробляючого рядка можна взяти будь-яку.

Рівняння площини , що відтиняє , утворюється в такий спосіб. Базисна перемінна xi виробляючого рядка виражається через небазисні перемінні:

(5.2.)

де ij - відповідні коефіцієнти і-й рядки оптимальної симплекса-таблиці.

Якщо взяти в розглянутому прикладі в якості виробляючого рядка рядок, що відповідає базисної перемінної x2, отримаємо



Використовуючи співвідношення (5.1.), перепишемо вираження (5.2.) у виді

(5.3.)

де .

Оскільки всі перемінні хі і=1, n повинні приймати цілі значення, ліва частина вираження (5.3.) повинні бути цілісною, відкіля випливає, що і права частина цього вираження повинна приймати цілі значення.

Далі, тому що fij0 і xj0 для всіх i і j, те

.

І, отже, виконується нерівність

. (5.4.)

Оскільки fi1, те і , але так ліва частина повинна приймати цілі значення, то необхідна умова її цілісності має вид

.

Останнє обмеження і визначає відсекаючу поверхню. Ввівши нову перемінну, запишемо це обмеження у виді рівності

. (5.5.)

де sk - позитивна додаткова перемінна, що повинна приймати цілі значення.

Отже, відсікання Гомори для цілком цілісної задачі задається рівнянням

. (5.6.)

Для розглянутого приклада, отримаємо

.

Складаємо нову симплекс-таблицю, уводячи нову базисну перемінну s1:



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

Виконання умови оптимальності гарантує оптимальність послідовно одержуваних рішень, а виконання умови допустимості забезпечує ітераційне наближення до області припустимих значень. На цьому заснований двоїстий симплекс-метод. Умови допустимості й оптимальності двоїстого симплекса-методу формуються наступним разом.

Умови допустимості. У якості що виключається з базисних перемінних вибирається найбільша по модулі негативна базисна перемінна. При наявності альтернатив вибір робиться довільно.

Умова оптимальності. Що включається в базис перемінна вибирається з числа небазисних перемінних у такий спосіб. Обчислюються відношення коефіцієнтів L рівняння до відповідних коефіцієнтів рівняння, асоційованого з що виключається перемінної. Відношення з позитивним або нульовим значенням знаменника не враховуються. У задачі максимізації вводимої перемінної повинне відповідати найменше з зазначених відношень, а в задачі мінімізації - відношення, найменше але абсолютному розміру. При наявності альтернатив вибір робиться довільно. Якщо знаменники усіх відношень рівні нулю або позитивні, задача не має припустимих рішень. У розглянутій задачі виведеної перемінної є s1, а вводимої перемінної - х3.

Після вибору вводимої і виведеної з базисних перемінних для одержання наступного рішення здійснюється звичайна операція одержання нових рядків симплекса-таблиці.

Для розглянутої задачі використання двоїстого симплекса-методу приводить до таблиці

БП

х1

х2

х3

х4

s1

Ріш.

х2

0

1

0

0

1

3

х1

1

0

0

1/7

-1/7

32/7

s1

0

0

1

1/7

-22/7

11/7

L

0

0

0

-1

-8

-59


Дане рішення знову не є цілісними, тому необхідно ввести нове відсекаюче обмеження.

Виробляючий рядок , що відповідає базисної перемінної х1, дає наступне рівняння

.

Тоді відсікання Гомори визначається рівнянням із нової невідомої s2:

.

Складаємо нову симплекс таблицю, уводячи нову базисну перемінну s2: що




виключається перемінної для цієї таблиці відповідно до умови допустимості є s2, вводимої відповідно до умови оптимальності - х4.

У результаті використання двоїстого симплекса-методу отримуємо нову таблицю



БП

х1

х2

х3

х4

s1

s2

Ріш.

х2

0

1

0

0

1

0

3

х1

1

0

0

0

-1

1

4

x3

0

0

1

0

-4

1

1

х4

0

0

0

1

6

-7

4

L

0

0

0

0

-2

-7

-55


Отримана таблиця дає оптимальне цілісне рішення вихідної задачі х1=4; х2=3; L=55.

Відзначимо, що загальні число обмежень, що відтиняють, не може перевищувати кількості перемінних вихідна задача, як-от (m+n).

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

,

записане в перемінних х1 і х2, після відповідної заміни приймає наступний вид:

або s1-x2=3.

Це рівняння еквівалентно нерівності х23. Аналогічним способом друге відсікання

.

породжує еквівалентне обмеження в перемінних х1 і х2:

.

На мал. 5.1. показане, як уведення цих двох обмежень дозволяє одержати нову оптимальну точку з координатами (4,3) у який досягається оптимум вихідної цілісної задачі.


^ 5.3. Рішення частково цілісних задач

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

У даній задачі потрібно будувати відсікання іншого типу, хоча загальна ідея рішення частково цілісних задач зберігається.

Нехай xk - перемінна частково цілісної задачі, що приймає цілі значення. Відповідний рядок симплекса-таблиці, що відповідає оптимальному рішенню задачі з ослабленими обмеженнями, породжує рівність

.

Для цілісної перемінної xk повинно виконуватися одне з двох нерівностей: або , або . З обліком рівність, отриманої з виробляючого рядка, запишемо ці умови в наступному виді:

, (5.7.)

. (5.8.)

Нехай I+ - множина значень j, для яких ;

I- - множина значень j, для яких .

З формул (5.7.) і (5.8.) получаем

, (5.9.)

. (5.10.)

Тому що співвідношення (5.7.) і (5.8.), а отже, (5.9.) і (5.10.) не можуть виконуватися одночасно, є можливість об'єднати (5.9.) і (5.10.) в одне обмеження виду

, (5.11.)

де se0 є додатня додаткова перемінна.

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

Розглянемо приклад попереднього параграфа, але вимога цілісності наложимо тільки на перемінну х1.

З виробляючого рядка відповідної х1, запишемо співвідношення

,

відкіля I-={3}; I+={4}; f1= .

Відповідно до вираження (5.11.) відповідне обмеження Гомори для частково цілісної задачі принимает вид



або

.

Додамо це обмеження в симплекс-таблицю:



У результаті застосування двоїстого симплекса-методу отримаємо таблицю

БП

х1

х2

х3

х4

s1

Реш.

х2

0

1

10/33

0

1/3

10/3

х1

1

0

-1/11

0

1

4

х4

0

0

1/3

1

-22/3

11/3

L

0

0

-23/11

0

-10

-58


Оптимальне рішення досягається в точці з координатами х1=4; ;

max L=58.

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

Можна використовувати рівняння більш ефективного відсікання [1]:

,

де




Цілком цілісну задачу також можна вирішити шляхом уведення відсікань Гомори для частково цілісной задачі.

У висновку відзначимо, що метод відсікання не забезпечує бажаної ефективності обчислювальних процедур при великих розмірностях задача, що зв'язана з ефектом помилки округлення, що виникає при використанні цифрових ЕОМ.


ТЕСТИ

(вірно (У) або невірно (Н))

5.1. Не можна в загальному випадку одержати припустиме цілісне рішення шляхом округлення задачі з ослабленими обмеженнями, одержуваної шляхом відкидання вимоги цілісності перемінних.

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

5.3. Значення цільової функції в оптимальному рішенні цілісної задачі максимізації (мінімізації) може бути більше (менше) оптимального значення цільової функції відповідної задачі з ослабленими обмеженнями.

5.4. При побудові відсікання Гомори для цілком цілісної задачі на додаткову перемінну також накладається умова цілісності.

5.5. Відсікання може виключити деяке припустиме цілісне рішення свідомо яке є не оптимальним.

5.6. Цілком цілісну задачу можна вирішити шляхом уведення відсікань Гомори для частково цілісної задачі.

5.7. Основна нестача методу площин, що відтиняють, Гомори полягає в його низкою ефективності при великих розмірностях задача, зв'язаної з ефектом помилки округлення.

5.8. При рішенні задача цілісного програмування використовується двоїстий симплекс-метод.

5.9. Умови допустимості й оптимальності двоїстого симплекса-методу не відрізняються від умов допустимості й оптимальності симплекса-методу.

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


ЗАВДАННЯ


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

5.1.




5.2.




5.3.




5.4.



5.5.



5.6.



5.7.



5.8.

.

На основі оптимального плану з ослабленими обмеженнями (умова цілісності перемінних відсутніх), знайти цілісне рішення задачі:

5.9.

БП

х1

х2

х3

х4

x5

Ріш.

х3

5/11

9/11

0

0

1

7/11

х4

2/11

3/11

1

0

0

10/11

х5

16/11

-4/11

0

1

0

3/11

L

-3

-4

0

0

0

0


5.10.

БП

х1

х2

х3

х4

x5

Ріш.

х3

0

0

1

-7/3

5/6

1/6

х1

1

0

0

-1/6

-2/3

1/2

х2

0

1

0

2/3

1/3

5/6

L

0

0

0

-7/6

-5/3

-67/6


5.11.

БП

х1

х2

х3

х4

x5

Ріш.

х4

0

-2/7

-1

1

6/7

13/7

х1

1

8/7

2

0

-3/7

4/7

L

0

-(20/7)

3

0

-(10/7)

39/7


5.12.

БП

х1

х2

х3

х4

x5

Ріш.

х2

6/5

1

0

0

1/5

1/5

х3

8/5

0

1

0

-13/5

7/5

х4

3/5

0

0

1

2/5

3/5

L

17/5

0

0

0

2/5

2/6


5.13.

БП

х1

х2

х3

х4

x5

Ріш.

х3

-1

0

1

0

4

2

х2

-2/9

1

0

0

16/9

14/9

х1

15/9

0

0

1

-7/9

41/9

L

-16/9

0

0

0

-(115/9)

-50/9


5.14.

БП

х1

х2

х3

х4

x5

Ріш.

х2

0

1

5/7

0

1/7

1/7

х4

0

0

13/7

1

-(20/7)

15/7

х1

1

0

-9/7

0

4/7

2/7

L

0

0

-3/7

0

-18/7

-12/7


5.15.

БП

х1

х2

х3

х4

x5

Ріш.

х1

1

4/3

-17/3

0

0

1/3

х4

0

-7/6

1/6

1

0

5/6

х5

0

-1/3

8/3

0

1

2/3

L

0

1/3

46/3

0

0

2/3



5.16.

БП

х1

х2

х3

х4

x5

Ріш.

х1

1

1/4

-3/4

7/2

0

7/4

х5

0

1/2

5/2

-(1/2)

1

3/2

L

0

19/4

47/4

9/4

0

37/4


5.17.

БП

х1

х2

х3

х4

x5

Ріш.

х5

0

0

5/2

7/3

1

1/2

х1

1

0

2

-(20/3)

0

2/3

х2

1/6

0

1

17/6

-1/3

0

L

0

0

13/3

2/3

0

-1


5.18.

БП

х1

х2

х3

х4

x5

Ріш.

х1

1

1/3

0

-2/3

0

1/3

х3

2/3

0

5/3

1

7/3

0

х5

4/3

0

13/3

0

8/3

1

L

0

-2

0

-7/3

0

-1




5.19.



5.20.

.

5.21.



5.22.




5.23.



5.24.



5.25. У задачі розподіли капіталовкладень розглядається п'ять проектів, що можуть бути здійснені протягом наступних трьох років. Очікувані розміри прибули від реалізації кожного і проектів і розподіл капіталовкладень по роках (у тис. гривнею) доводяться в таблиці. Передбачається, що кожний тверджень проект буде реалізований за трирічний період. Потрібно вибрати сукупність проектів, якої відповідає максимум сумарної прибули.


Проект

Розподіл капіталовкладень

Прибуток від



рік 1

рік 2

рік 3

проекти

1

5+i

1+i

8+i

20+i

2

4+i

7+i

10+i

40+i

3

3+i

9+i

2+i

20+i

4

7+i

4+i

1+i

15+i

5

8+i

6+i

10+i

30+i

Максимально можливий об'єм капіталовкладень


25+i


25+i


25+i


25+i


i - особистий номер кожного студента.

Одержите математичну модель задачі цілісного програмування і вирішите її.





Схожі:

5. Цілісне програмування iconКритерії оцінювання знань І вмінь студентів
«Інформатика» денної та заочної форми навчання. Фахове вступне випробування базується на матеріалах навчальних дисциплін з програмування:...
5. Цілісне програмування iconДокументи
1. /Математичне програмування/~$Р_2_8.doc
2. /Математичне...

5. Цілісне програмування iconДокументи
1. /Математичне програмування/~$Р_2_8.doc
2. /Математичне...

5. Цілісне програмування iconЗадача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,"умовно", в іншому- "безумовно".
Але на відміну від лінійного програмування, динамічне програмування не зводиться до будь-якої стандартної обчислювальної процедури;...
5. Цілісне програмування icon6. Динамічне програмування
Динамічне програмування являє собою математичний апарат, розроблений із метою підвищення ефективності при рішенні деякого класу задач...
5. Цілісне програмування icon6. Динамічне програмування
Динамічне програмування являє собою математичний апарат, розроблений з метою підвищення ефективності при рішенні деякого класу задач...
5. Цілісне програмування iconЗадача динамічного програмування. Загальний випадок
Але у відмінності від лінійного програмування динамічне програмування не зводиться до якийсь стандартної обчислювальної процедури;...
5. Цілісне програмування iconПро проведення ІІ етапу Всеукраїнської студентської олімпіади з програмування
Олімпіада проводиться згідно з правилами чемпіонату світу з програмування серед студентських команд під егідою Association for Computing...
5. Цілісне програмування iconПро проведення ІІ етапу Всеукраїнської студентської олімпіади з програмування
Олімпіада проводиться згідно з правилами чемпіонату світу з програмування серед студентських команд під егідою Association for Computing...
5. Цілісне програмування iconКонтрольна робота по дисципліні «Математичне програмування» Лінійне програмування

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи