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

Зміст

Введення

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) називається задачею частково дискретного програмування.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--