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

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

Курсова робота:

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

Зміст


Введення

1. Постановка лінійної цілочисленної задачі

2. Теоретичні основи методів відсікання

3. Перший алгоритм Гомори

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

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

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

7. Деякі висновки

Висновок

Список літератури

Введення


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

Історично першою задачею цілочисленного типу є опублікована угорським математиком Е. Егервари в 1932 р. задача про призначення персоналу.

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

1. Постановка лінійної цілочисленної задачі


Серед сукупності п неподільних предметів, кожний i-і (i=1,2,…,п) з яких володіє по i-й характеристиці показником Рішення задач цілочисленного програмування і корисністю Рішення задач цілочисленного програмування знайти такий набір, що дозволяє максимізувати ефективність використання ресурсів величини Рішення задач цілочисленного програмування.

Математична модель цієї задачі може бути представлена в такий спосіб:

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


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

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

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


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


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


Якщо Рішення задач цілочисленного програмування, то (1–4) є моделлю задачі цілочисленного програмування, якщо Рішення задач цілочисленного програмуванняРішення задач цілочисленного програмування- моделлю задачі частково цілочисленного програмування.

Часткою случаємо задачі цілочисленного програмування є задача з булевими змінними. Її математична модель у загальному виді записується в такий спосіб:

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

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

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


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


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


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

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

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


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

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


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

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


Умова (9) визначило назву цього класу; задач. Якщо Рішення задач цілочисленного програмування, то (8–10) називається задачею дискретного програмування; якщо Рішення задач цілочисленного програмування, те (8–10) називається задачею частково дискретного програмування.

Неважко бачити, що умова (2–3) задачі (1–4) і умова (6) задачі (5–7) є часткою случаємо умови (9) задачі (8–10). Дійсно, (2–3) відповідає тому случаю, коли Рішення задач цілочисленного програмування для Рішення задач цілочисленного програмування. Умова (9) відповідає випадку, коли Рішення задач цілочисленного програмування.

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

Вектор Рішення задач цілочисленного програмування, що задовольняє умовам (1–3) (відповідно (8–9)), називається припустимим рішенням задачі (1–4) (відповідно (8–10)). Припустиме рішення, при якому функція (4) (відповідно (10)) досягає найбільшого (найменшого) значення, називається оптимальним рішенням.

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

ПРИКЛАД. В області, певної умовами


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

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

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

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


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

(мал. 1)


Однак нас цікавлять лише крапки із цілочисленними координатами, отже, ні А, ні В не є припустимим рішенням задачі. Округляючи значення координат А, одержимо Рішення задач цілочисленного програмування Але крапка А' не належить області пошуку. Можна показати, що цілочисленний оптимум досягається в крапках N (3; 2) і M (2; 3) і дорівнює 5. Обидві крапки усередині області пошуку.

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

2. Теоретичні основи методів відсікання


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


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

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

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


максимізувати функцію


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


Назвемо для кратності задачу (11–14) (Јц, C) – задачею. Відповідну їй задачу без вимоги цілочисленності змінних, тобто задачу (11, 12, 14) назвемо (Ј, C) – задачею. Порушимо питання: чи не можна рішення (Јц, C) – задачі одержати шляхом рішення якоїсь спеціальним образом побудованої задачі без вимоги цілочисленності змінних і такий, що оптимальні рішення вихідної (Јц, C) – задачі й задачі без вимог цілочисленності змінних будуть збігатися. Іншими словами: чи не можна добре вивчений апарат рішення задач лінійного програмування пристосувати до рішення цілочисленних задач. Принципова відповідь на це питання дає наступна теорема.

Теорема. Нехай Ј – багатогранник, Јц – множина його цілих крапок, R – опукла, лінійна оболонка множини Јц, тоді:


1) R=Rц – цілочисленний багатогранник;

2) Rц = Јц;

3) R* – множина опорних рішень задачі (Јц, C) утримується в багатограннику Rц.

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

По самому визначенню опуклої лінійної оболонки, вона містить всі опорні плани множини, на яке вона натягнута, тобто багатогранник R містить всі целочисленные крапки Јц. Тому R – цілочисленний багатогранник. Позначимо його через Rц. Перша частина теореми доведена.

Доведемо, що Rц збігається з Јц. Тому що R – опукла оболонка крапок множини Јц, те Јц НRц.

Покажемо, що справедливо також і протилежна нерівність-включення, т.е. RцНЈц. Для цього виберемо деякий довільний елемент х°ОRц. Оскільки Rц містить всі опорні рішення задачі (Јц, C), те х° задовольняє умовам задачі (Јц, C), тобто х°ОЈц. Але оскільки довільний елемент із Rц належить Јц, те очевидно, що справедливо RцНЈц. Зіставляючи протилежні включення RцНЈц і ЈцНRц доходимо висновку: що Јц=Rц. Друга частина теореми також доведена.

Доказ 3-го пункти теореми є зовсім очевидним. Тому що R* – множина опорних рішень задачі (Јц, C), те R*НЈц але Јц=Rц, тому R*НRц

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

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

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

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

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

Алгоритм Р. Гомори складається з наступних процедур:

Вирішується (Ј, C) – задача, що відповідає вихідної (Јц, C) – задачі.

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

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

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

додаткове обмеження повинне бути лінійним, щоб залишатися в області застосовності апарата лінійного програмування;

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

Нехай х (Ј, C) – оптимальне рішення (Ј, C) – задачі, що є неприпустимим рішенням для (Јц, C) – задачі. Нерівність


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


визначає правильне відсікання, якщо задовольняє

а) умові відсікання: x(?, C) задовольняє нерівності (15)

б) умові правильності: будь-яке припустиме рішення задачі (Јц, C), задовольняє нерівності (15).

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


3. Перший алгоритм Гомори


Випливаючи загальній схемі методів відсікання, вирішимо (Ј, C) – задачу (11, 12, 14), що відповідає (Јц, C) – задачі (11–14). Нехай x(Ј, C) – її оптимальне рішення. Проаналізуємо координати x(Ј, C) на цілочисленність. Якщо всі координати вектора x(Ј, C) цілі, то x(Ј, C) = x(Јц, C). Якщо хоча б одна координата, нехай xi, буде нецілої, надійдемо в такий спосіб.

Позначимо через N сукупність небазисних змінних і на підставі останньої симплексної таблиці запишемо розкладання xi по небазисним змінним xi, jОN


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


Тому що xi – неціла величина, позначимо найближче ціле число, що не перевершує xi, через [xi] і визначимо дробову частину: {xi}= xi - [xi]. Очевидно, (xi)>0.

Покажемо, що по i-і рядку симплексної таблиці (?, C) - задачі (у якій коштує неціла координата рішення) можна визначити додаткове лінійне обмеження, що володіє властивостями правильності.

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


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


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

визначають правильне відсікання.

Доказ.

Запишемо вираження (16) у вигляді:


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


Використовуючи для цього вираження формулу (17), одержимо:


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


або


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


На підставі припущень теореми про допустимість рішення

(Јц, C) – задачі xi – ціле. Величини [xio], Рішення задач цілочисленного програмування- цілі по визначенню, отже, zi – теж ціле.

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

Це значить, що Рішення задач цілочисленного програмування. По визначенню дробової частини Рішення задач цілочисленного програмування. За умовою теореми x – припустиме рішення (Јц, C) – задачі, тому Рішення задач цілочисленного програмування. Отже,


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


Тоді повинне виконуватися:


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


Отже, із припущення заперечності zi, відразу ж одержуємо Рішення задач цілочисленного програмування тобто zi – неціле. Оскільки раніше було показано, що zi, певне формулою (17), є цілим, те тим самим ми прийшли до протиріччя. Отже, припущення, що zi < 0, невірне. Теорема доведена.

Наслідок. Будь-яке оптимальне рішення x(Ј, C) (Ј, C) – задачі, що не є припустимим рішенням (Јц, C) – задачі, не задовольняє умові правильного відсікання (17).

Доказ. Нехай х (Ј, C) – оптимальне рішення (Ј, C) – задачі, xi0 – дробове.

Покажемо, що х (Ј, C) не задовольняє умові відсікання. Оскільки план оптимальний, всі небазисні змінні xi, для jОN дорівнюють нулю. Тому Рішення задач цілочисленного програмування. З огляду на це, підставимо xio у формулу (17):


zi(x (Ј, C))= – {xi0}+0<0,

що суперечить умові незаперечності zi. Наслідок доведений.

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

Р. Гомори запропонував прийом, що дозволяє обмежити розміри розглянутих симплексних таблиць допоміжних задач величиною (n+2) (k+1), де n – кількість змінних (Ј, C) – задачі, k – число небазисних змінних її. Цей прийом ґрунтується на тім, що нас цікавить додаткове обмеження лише як спосіб відсікання нецілочисленного оптимального рішення допоміжної задачі, отриманої на даному кроці, і переходу до наступної задачі.

Послідовність (Ј, C) – задач позначимо індексом k=0,1,…,відповідному номеру ітерації в послідовному наближенні до рішення вихідної (Јц, C) – задачі, і позначимо (Јk, C). При цьому (Ј0, C) – задача відповідає (Ј, C) – задачі (задачі без вимоги цілочисленності).

Змінну zi, що визначається додатковим лінійним обмеженням (7) і будується по деякої нецілочисленної координаті оптимального рішення (Јk, C) – задачі (k =0, 1, 2,…)позначимо xn+k+l.

Щоб розмірність послідовності (Јk, C) – задач не зростала, викреслимо із симплекс-таблиці змінну, по якій побудоване додаткове лінійне обмеження.

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

1. Вирішимо (Јk, C) – задачу (спочатку k = 0) методом послідовного поліпшення плану.

Нехай у базис оптимального рішення ввійшли вектори As1,…,Asm... Параметри останньої симплексної таблиці позначимо через xij:


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


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

2. Якщо серед сукупності координат оптимального рішення x(Јk, C) є єдина неціла координата, то додаткове лінійне обмеження (17) будується по цій координаті. Якщо нецілих координат в x(Јk, C) більше однієї, то виберемо координату з найменшим номером. Нехай нею виявилася xi0. Складемо додаткове лінійне обмеження


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

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


3. Додамо умови (18, 19) до умов (Јk, C) – задачі. Одержимо нову (Јk+1, C) – задачу. Тому що оптимальне рішення x(Јk, C) (Јk, C) – задачі визначало одну з вершин багатогранника умов, то воно може бути обране в якості первісного опорного рішення для знову отриманої задачі. А це означає, що останню симплексну таблицю (Јk, C) – задачі можна взяти в якості вихідної для (Јk+1, C) – задачі, доповнивши її умовою (18).

Отже, симплексна таблиця для (Јk+1, C) – задачі виходить із останньої симплексної таблиці для (Јk, C) – задачі шляхом облямівки (i+1) – й рядком з елементами:


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

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


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


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

Одержимо нову задачу, змінними якої є Рішення задач цілочисленного програмування. Умови цієї задачі дозволені відносно xsl,…,xsmзмінних і нова змінної xn+k+1, а лінійна форма виражена через небазисні змінні (Јk, C) – задачі. Тому що ми займаємося максимізацією F(x) і рішення х* для (Јk, C) – задачі оптимально, те всі Di > 0. Тому процес переходу до нового рішення (Јk+1, C) – задачі не може бути здійснений по методу уточнення плану. У той же час Рішення задач цілочисленного програмування і тому вектор А0 симплексної таблиці не є опорним рішенням для (Јk+1, C) – задачі, тому що рішенням називається вектор, всі координати якого ненегативні й задовольняють умові приналежності області Јk+l. Тому назвемо отриманий вектор Рішення задач цілочисленного програмування псевдо рішенням задачі (Јk+1, C) і перейдемо до подальшого перетворення симплекса-таблиці.

Позначимо через k номер псевдо рішення (Јk, C) – задачі; тоді напрямним рядком є i+k+ 1-я рядок, k =0, 1, 2,…... Тому на кожному етапі перетворення таблиці вектор Ai+k+i буде виводитися з таблиці. Можна довести, що через кінцеве число кроків або буде знайдене цілочисленне рішення, або буде виявлена її нерозв'язність, а тим самим нерозв'язність (Јц, C) – задачі.

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

Процедуру рішення (Јk, C) – задачі (k=0, 1,…)і аналізу отриманого рішення назвемо великою ітерацією. Номер великої ітерації збігається з номером розв'язуваної (Јk, C) – задачі.

Результатом великої ітерації є перехід до нового (Јk+1, C) – задачі або закінчення рішення задачі.

Уведемо: 1) осередок i, у якій будемо запам'ятовувати номер рядка, на підставі якої будується чергове додаткове лінійне

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

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

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

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