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

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

Зміст

Введення

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) відповідає тому случаю, коли  для . ............