UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЦілочислові задачі лінійного програмування. Деякі з Основних методів їх розв\'язування та аналізу (реферат)
АвторPetya
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось3069
Скачало406
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Цілочислові задачі лінійного програмування. Деякі з Основних методів їх

розв'язування та аналізу.

 

План.

 

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

 

2. Метод Гоморі

 

3. приклади розв'язування задач.

 

4. Література

 

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

 

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

функція, так і функції в системі обмеженні є лінійними. У зв'язку з цим

сформулюємо основну задачу лінійного програмування, у якій перемінні

можуть приймати тільки цілі значення. У загальному виді цю задачу можна

записати так: знайти максимум функції.

 

(32)

 

при умовах

 

(33)

 

(34)

 

(35)

 

Якщо знайти рішення задачі (32) — (35) симплексним методом, то воно може

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

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

задача). У загальному ж випадку для визначення оптимального плану задачі

(32) — (35) вимагаються спеціальні методи. В даний час існує кілька

таких методів, з яких найбільш відомим є метод Гоморі, в основі якого

лежить описаними вище симплексний метод.

 

М е т о д Г о м о р і. Перебування рішення задачі цілочислового

програмування методом Гоморі починають з визначення симплексним методом

оптимального плану задачі (32) —(34) без обліку цілочисловості змінних.

Після того як той план знайдений, переглядають його компоненти. Якщо

серед компонентів немає дробових чисел, то знайденими план є оптимальним

планом задачі цілочислового програмування (32) —(35). Якщо ж в

оптимальному плані задачі (32) — (34) перемінна хј приймає дробове

значення, то до системи рівнянні (33) додають нерівність

 

(36)

 

і знаходять рішення задачі (32) — (34), (36).

 

У нерівності (36) ?*ij і bi* — перетворені вихідні величини ?ij і bi,

значення яких узяті з останньої симплекса-таблиці, а f(?*ij) і f (b*ij)

— дробові частини чисел (під дробовою частиною деякого числа ?

розуміється найменше ненегативне число b таке, що різниця між ? і b є

ціле). Якщо в оптимальному плані задачі (32) — (34) дробові значення

приймають трохи перемінних, то додаткова нерівність (36) визначається

дробовою найбільшою частиною.

 

Якщо в знайденому плані задачі (32) — (34), (36) перемінні приймають

дробові значення, то знову додають, одне додаткове обмеження процесі

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

оптимальний план задачі цілочислового програмування (32) — (35), або

встановлюють її нерозв'язність.

 

Якщо вимога цілочисловості (35) відноситься лише до деяким перемінної,

то також задачі називаються - частково цілочисловими. Їхнє рішення також

знаходять послідовним рішенням задач, кожна з який виходить з

попередньої за допомогою введення додаткового обмеження. У цьому випадку

таке обмеження має вид

 

(37)

 

де ?ij визначаються з наступних співвідношенні:

 

для хj, що можуть приймати не цілочислові значення,

 

при ?*ij ?0,

 

при ?*ij<0; (38)

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ