Цілочисельне програмування icon

Цілочисельне програмування




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




  1. Цілочисельне програмування


Цілочисельне програмування (ЦП) орієнтовано на рішення задач математичного

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

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

      Формуліровка задачі лінійного ЦП та її математична модель



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

Введемо в розглянення змінні хі, і=1..n, які визначаються умовою:

(1 - якщо предмет Пі перевозиться, 0 - якщо предмет Пі не перевозиться)

Звичайно цільова функція, яку необхідно максимізувати, має вид:

.

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

q1*x1 + q2*x2 + … +qn*xn  Q.

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

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

5.2. Рішення задачі лінійного повність ЦП методом відсікаючих площин


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

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

    1 + 3х2  6;

1 + х2  35;

де х1 та х2 невід"ємні цілі.


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




x2



N

4

3

2

1



0 1 2 3 4 5 6 x

-1 L=0

Мал.1

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

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

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

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


,

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

,

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

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

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

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

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

знайти max L = 7x1 + 9x2 при обумовленнях:

    1 + 3х2  6;

1 + х2  35;

х1  0;

х2  0.

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

БП

x1

x2

x3

x4

Ріш. bj

х2

0

1

7/22

1/22

7/2

х1

1

0

-1/22

3/22

9/2

L

0

0

-28/11

-15/11

-63



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

Для обрання строки відтворення та отримання рівняння відсікаючої площини необхідно виконати ряд операцій.

Подамо всі нецілоч. значення базісних змінних bі у вигляді:

. (5.1.)

де [bi] - означає приведення до цілого найменьшого числа, а

.

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

bi

31/2

¼

-21/3

-1/4

-1

[bi]

3

0

-3

-1

-1

fi

½

¼

2/3

¾

0

Звісно, що 0  fi<1.

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

Для приклада, що розглядається




Так як max fi =1/2 , тоді за строку відтворення можна взяти будь - яку.

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

xi = bi - , (5.2)

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

Якщо взяти в цьому прикладі за строку відтворення строку, яка відповідає базісной змінній x2 , отримаємо:

x2 = 7/2 - 7/22*x3 - 1/22*x4 .

При використанні відношення (5.1.), перепишемо вираз (5.2.) у вигляді:

xi - [bi] + , (5.3)

де fij = ij - [ij] .

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

Далі, так як fij и xj 0 для всіх i и j, то


,

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

fi - .

Тому що fi < 1 , то i fi - , але тоді ліва частина повинна приймати цілі значення, відкіля необхідна умова її цілочисленості має вид:

fi - .

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

fi - .

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

Тому, відсічення Гоморі для повністю ц. задачі задається рівнянням:

si - .

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

s1 - 7/22x3 - 1/22x4 = -1/2.

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

БП

x1

x2

x3

x4

s1

Ріш. bj

х2

0

1

7/22

1/22

0

7/2

х1

1

0

-1/22

3/22

0

9/2

s1

0

0

-7/22

-1/22

1

-1/2

L

0

0

-28/11

-15/11

0

-63


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

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

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

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

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

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

БП

x1

x2

x3

x4

s1

Рішj

х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



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

Строка відтворення (max fi = 4/7), яка відповідає базісній змінній x1 дає наступне рівняння:

Õ1 = 4 4/7 - 1/7x4 + 1/7s1.

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

s2 - 1/7x4 - 6/7s1 = -4/7.

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

БП

x1

x2

x3

x4

s1

s2

Ріш

х2

0

1

0

0

1

0

3

х1

1

0

0

1/7

-1/7

0

32/7

x3

0

0

1

1/7

-22/7

0

11/7

s2

0

0

0

-1/7

-6/7

1

-4/7

L

0

0

0

-1

-8

0

-59

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

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

БП

x1

x2

x3

x4

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

s2

0

0

0

1

6

-7

4

L

0

0

0

0

-2

-7

-55

Отримана таблиця дає оптимальне цілочисельне рішення вихідної задачі

x1 = 4 ; x2 = 3 ; L = 55.

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

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

s1 - 7/22x3 - 1/22x4 = -1/2 ,

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

s1 - 7/22(6 + x1 - 3x2 ) - 1/22(35 - 7x1 - x2)= -1/2 або s1-x2=3.

Це рівняння еквівалентно нерівності x23. Аналогічним чином друге відсічення:

s2 - 1/7x4 - 6/7s1 = -4/7 .

породжує еквівалентне обумовлення у змінних x1 та x2.

x1 + x2 7

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


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

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

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

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

xk = bk - .

Для цілочисельної змінної повинно виконуватися одна з двох нерівностей:

або . З урахуванням рівняння, яке отримано із строки відтворення, запишемо ці умови у наступному вигляді:

, -1.

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

    I- - множина значеннь, для яких kj < 0.

Із формул (5.7.) та (5.8.) отримуємо:

, ,

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

s1 = -fk , (5.11.) ,

де se0 є невід"ємна додаткова змінна.

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

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

Із строки відтворення, яка відповідає x1, запишемо співвідношення:

x1 – 1/22x3 + 3/22x4 = 41/2 ,

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

У відповідності з виразом (5.11.) відповидне обумовлення Гоморі для часково цілочисельної задачі приймає вигляд:

s1 ,

або

s1 – 1/22x3 – 3/22x4 = -1/2 .

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

БП

x1

x2

x3

x4

s1

Ріш

х2

0

1

7/22

1/22

0

7/2

х1

1

0

-1/22

3/22

0

9/2

s1

0

0

-1/22

-3/22

1

-1/2

L

0

0

-28/11

-15/11

0

-63

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

БП

x1

x2

x3

x4

s1

Ріш

х2

0

1

10/33

0

1/3

10/3

х1

1

0

-1/11

0

1

4

s1

0

0

1/3

1

-22/3

11/3

L

0

0

-23/11

0

-10

-58
^

Оптимальне рішення отримується в точці з координатами x1 = 4; x2 = 10/2.


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

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

jxj.

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

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

Тести.

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

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

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

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

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

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

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

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

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

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

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

ЗАДАЧІ



Вирішіть наступни задаччі ЦП.

5.1 max L = 20x1+10x2+10x3; 2x1+20x2+4x315;



    1. max L = 2x1+x2; x1+2x23;

3x1+y23 x0, цілі.

4x1+3x26

    1. Взадачі розподілу капіталовкладень розглядається 5 проектів які можуть бути проваджені в наступних 3-х роках. Очикувальні величини прибутку від реалізації кожного з проектів та розподіл капітало вкладень по роках (в 1000 гр. приведені в таблиці). Передбачається, що кожний затверджений проект буде реалізован за трьох річрий період. Треба обрати сукупність проектів, якій відповідає максимум прибутку.




Проект
^

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


Прибуток від проекту



рік1

рік 2

рік 3

1

5+ і

1+ і

8+ і

20+ і

2

4+ і

7+ і

10+ і

40+ і

3

3+ і

9+ і

2+ і

20+ і

4

7+ і

4+ і

1+ і

15+ і

5

8+ і

6+ і

10+ і

30+ і

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

25+ і

25+ і

25+ і

25+ і


і – власний номер кожного студента.

Отримайте математичну модель задачі ЦП та вирішить ії.

Схожі:

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

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

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


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