Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Цілочислові задачі лінійного програмування. Деякі з Основних методів їх розв

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

Назва:
Цілочислові задачі лінійного програмування. Деякі з Основних методів їх розв
Тип:
Реферат
Мова:
Українська
Розмiр:
4,44 KB
Завантажень:
471
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3 
Реферат на тему:
Цілочислові задачі лінійного програмування. Деякі з Основних методів їх розв'язування та аналізу.


План.
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)
для xj, що можуть приймати тільки цілочислові значення,
при
 
при (39)
З викладеного вище випливає, що процесі визначення оптимального плану задачі цілочислового програмування методом Гоморі включає наступні основні етапи:
1. Використовуючи симплексний метод, знаходять рішення задачі (32) — (34) без обліку вимоги цілочисловості перемінних.
2. Складають додаткове обмеження для перемінної, котра в оптимальному плані задачі (32) — (34) має максимальне дробове значення, а в оптимальному плані задачі (32) — (35) повинна бути цілочисловою.
3. Використовуючи двоїстий симплекс-метод, знаходять рішення задачі, що виходить із задачі (32) — (34) у результаті приєднання додаткового обмеження.
4. У разі потреби складають ще одне додаткове обмеження і продовжують ітераційний процесі до одержання оптимального плану задачі (32) — (35) чи встановлення її нерозв'язності.
2.49. Методом Гоморі знайти максимальне значення функції
F = 3х1+2хг (40)
при умовах
(41)
(42)
хj – цілі (43)
Дати геометричну інтерпретацію розв’язку задачі.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок