Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Задачі цілочисельного програмування та спеціальні методи знаходження їх оптимальних розв'язків
Задачі цілочисельного програмування та спеціальні методи знаходження їх оптимальних розв'язків
Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом, геометрична інтерпретація їх розв’язків на площині. Завдання складання розкладу занять на математичному факультеті. Математична модель розкладу.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | украинский |
| Дата добавления | 23.09.2012 |
| Размер файла | 933,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Розв'язування цілочислових задач методом гілок і меж можна значно прискорити. Очевидно, що кожна наступна задача, яку отримують в процесі розв'язування відрізняється від попередньої лише одним обмеженням. Тому за послідовного розв'язування задач немає сенсу розв'язувати їх симплексним методом спочатку. Досить буде почергово приєднати нові обмеження виду (1.18) і (1.23) до останньої симплекс-таблиці попередньої задачі та вилучити (в разі необхідності) непотрібні "старі" обмеження.
Геометрично введення додаткових лінійних обмежень виду (1.18) та (1.23) в систему обмежень початкової задачі означає проведення гіперплощин (прямих), що розтинають багатогранник (багатокутник) допустимих планів відповідної задачі лінійного програмування у такий спосіб, що уможливлюється включення в план найближчої цілої точки цього багатокутника (рис.6.4). Допустимо, що А - точка максимуму, тоді за методом гілок та меж багатокутник допустимих планів задачі ABCOD поділяється на дві частини прямими та , що виключає з розгляду точку А, координата якої є не цілим числом.
Опишемо алгоритм методу гілок та меж:
Симплексним методом розв'язують задачу (1.1) - (1.3) (без вимог цілочисловості змінних).
Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей розв'язок є оптимальним планом задачі цілочислового програмування (1.1) - (1.4).
Якщо задача (1.1) - (1.3) не має розв'язку (цільова функція необмежена, або система обмежень несумісна), то задача (1.1) - (1.4) також не має розв'язку.
Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних і визначають її цілу частину .
Записують два обмеження, що відтинають нецілочислові розв'язки:
,
Кожну з одержаних нерівностей приєднують до обмежень початкової задачі. В результаті отримують дві нові цілочислові задачі лінійного програмування.
У будь-якій послідовності розв'язують обидві задачі. У разі, коли отримано цілочисловий розв'язок хоча б однієї із задач, значення цільової функції цієї задачі зіставляють з початковим значенням. Якщо різниця не більша від заданого числа e, то процес розв'язування може бути закінчено. У разі, коли цілочисловий розв'язок одержано в обох задачах, то з розв'язком початкової зіставляється той, який дає краще значення цільової функції. Якщо ж в обох задачах одержано нецілочислові розв'язки, то для дальшого гілкування вибирають ту задачу, для якої здобуто краще значення цільової функції і здійснюють перехід до кроку 2.
Приклад 2.2 Розв'яжемо методом гілок і меж задачу з прикладу 2.1.
Розв'язання. Відкинувши умову цілочисловості, дістанемо розв'язок: , . Отже, допустиме ціле значення має задовольняти одну з нерівностей або . Приєднуємо до початкової задачі окремо кожне з обмежень, нехтуючи умовою цілочисловості, і розв'язуємо по черзі обидві утворені задачі:
|
Задача І |
Задача ІІ |
|
|
, |
, |
|
|
; |
; |
|
|
; |
; |
|
|
; |
; |
|
|
; |
; |
|
|
і - цілі числа. |
і - цілі числа. |
Для задачі І (з обмеженням ) оптимальним буде розв'язок , , а для задачі ІІ (з обмеженням) - розв'язок , . Оскільки цілочислового плану не знайдено, процес необхідно продовжити, узявши для дальшого розгалуження першу задачу, оптимальний план якої дає більше значення функціонала. Розв'язуємо задачу І, окремо приєднуючи до неї обмеження: і . Отримуємо такі дві задачі:
|
Задача ІІІ |
Задача ІV |
|
|
, |
||
|
; |
; |
|
|
; |
; |
|
|
; |
; |
|
|
; |
; |
|
|
; |
; |
|
|
і - цілі числа. |
і-цілі числа. |
Розв'язком задачі ІІІ є план , , а задачі IV план ,. Обидва розв'язки є цілочисловими, проте краще значення цільової функції забезпечує розв'язок задачі IV. Тому оптимальним планом початкової цілочислової задачі буде , , що збігається з розв'язком, отриманим за методом Гоморі.
Схема процесу розв'язування задачі з прикладу 2.1 (рис.2.5) досить наочно пояснює назву методу гілок та меж. Початкова задача розділяється (гілкується) на дві простіші, і, якщо серед них не існує задачі з цілочисловим оптимальним розв'язком, то процес гілкування продовжується. Отже, всі розглянуті дії можна зобразити у вигляді "дерева":
Рис.2.5
Кожен елемент такого "дерева" - це певна задача, що має відповідний оптимальний план. Після одержання нецілочислового розв'язку послабленої (тобто без умови цілочисловості) початкової задачі ми перетворили її на дві інші з додатковими умовами. З них кращим виявився розв'язок задачі І, однак оскільки він був не цілочисловим, то ми продовжили процес гілкування. Задачу І введенням додаткових обмежень перетворили в задачу ІІІ та задачу IV. Оптимальні плани обох цих задач цілочислові, але план задачі IV дає більше значення функціонала, тому цілочисловим оптимальним планом початкової задачі є розв'язок задачі IV.
Коротко розглянемо без наведення прикладів ще один цікавий метод, який можна віднести до типу комбінаторних - метод послідовного аналізу варіантів. Загальна схема цього методу розроблена українським вченим
В.С. Михалевичем, який працював у київському Інституті кібернетики. Ідея цього методу полягає в послідовному повторенні таких процедур:
1) розбиття множини варіантів розв'язків задачі на кілька підмножин, кожна з яких має специфічні властивості;
2) використання вищезазначених властивостей для пошуку логічних суперечностей в опису окремих підмножин;
3) виключення із дальшого розгляду тих підмножин варіантів розв'язків, в описах яких є логічні суперечності.
Отже, методика послідовного аналізу варіантів базується на відсіві неперспективних варіантів ще до їх побудови. Оскільки у разі відсіву неперспективних початкових частин варіантів відсівається і вся процедура продовжень їх розрахунків, то досягається значна економія часу через скорочення обчислювальних операцій. Відсів неперспективних елементів від
Зрозуміло, що для кожного типу задач цілочислового програмування формулюються специфічні правила для відсіву варіантів.
Метод послідовного аналізу варіантів успішно застосовувався для розв'язування різноманітних задач оптимального планування та проектування. Наприклад, для розрахунку транспортних мереж, розміщення на мережі типу дерева, проектування розподільних електричних мереж, вибору оптимальних параметрів магістральних газопроводів тощо.
Розділ 3. Розробка математичної моделі складання розкладу занять на математичному факультеті ВНУ
3.1 Формулювання завдання складання розкладу занять на математичному факультеті
Ефективність використання науково-педагогічного потенціалу і якість підготовки фахівців у вузах певною мірою залежать від рівня організації навчального процесу.
Одна з складових цього процесу, розклад занять, регламентує трудовий ритм, впливає на творчу віддачу викладачів, тому його можна розглядати як чинник оптимізації використання обмежених трудових ресурсів - викладацького складу. Технологію ж розробки розкладу слід сприймати не тільки як трудомісткий технічний прогрес або об'єкт автоматизації з використанням ЕОМ, але і як акцію оптимального управління. Таким чином, - проблема розробки оптимальних розкладів занять у вузах з очевидним економічним ефектом. Оскільки інтереси учасників учбового процесу багатогранні, то завдання складання розкладу є багатокритерійною.
Завдання складання розкладу не варто розглядати тільки як якусь програму, що реалізовує функцію механічного розподілу занять на початку семестру, на якій її (програми) використання і закінчується. Необхідно, щоб програма включала засоби для випадку зміни деяких вхідних даних.
Завдання теорії розкладів в загальній її постановці вважається вельми привабливим, хоча досягнення навіть невеликого прогресу на шляху до рішення зв'язане, як правило, з величезними труднощами. Не дивлячись на те, що завданнями теорії розкладів займалися багато кваліфікованих фахівців, до цих пір нікому не вдалося отримати якихось істотних результатів. Безуспішні спроби отримання таких результатів, як правило, не публікуються і це частково обумовлює той факт, що завдання продовжує привертати увагу багатьох дослідників простотою постановки, що здається.
Розвиток нових інформаційних технологій в області створення програмних web-додатків дозволив подивитися на проблему складання розкладу і комунікативної взаємодії в зв'язці: администрация-викладач-студент з іншої точки зору. Система складання розкладу у вузі обов'язково повинна реалізовувати ряд основних функцій:
вибір викладачів;
вибір дисциплін;
вибір днів тижня;
закріплення аудиторій;
об'єднання груп в потоки по будь-якій сукупності дисциплін;
після складання розкладу при необхідності здійснювати заміну викладачів або змінювати час проведення заняття.
Крім того, існують ще і специфічні для кожного вузу вимоги щодо функціональних можливостей програмного продукту. У випадку вузів попит на системи складання розкладів напевно навіть більший, ніж для шкіл, але справа ускладнюється великою специфікою організації учбового процесу в кожному окремо взятому вузі. Створити уніфіковане програмне забезпечення не представляється можливим, а вартість створення спеціалізованого програмного продукту у сторонніх розробників невиправдано велика.
Метою даної роботи було створення такої математичної моделі розкладу у вузі, яка дозволяла б ефективно (у задані терміни та з заданим ступенем оптимальності) вирішувати задачу автоматичного складання розкладу і володіла б гнучкістю (незначних змін у разі змін вхідній інформації) для адаптації системи в рамках конкретного практичного завдання.
Для деякого спрощення завдання на початковому етапі проектування були зроблені такі допущення:
розклад складається з розрахунку не більше двох пар в день (що цілком підходить для викладачів із півставки навантаження);
всі пари проводяться в одному корпусі;
завдання ставиться в термінах лінійного програмування;
подальша декомпозиція моделі не проводиться;
всі коефіцієнти моделі і шукані змінні цілочисельні;
Поставлене завдання повинне вирішуватися одним з універсальних (не залежних від цілочисельних значень коефіцієнтів) методів цілочисельного лінійного програмування.
3.2 Математична модель розкладу у вузі
Побудуємо математичну модель розкладу у вузі в термінах лінійного програмування. Введемо позначення і визначимо змінні та обмеження.
ГРУПИ
У вузі є N навчальних груп, об'єднаних в R потоків; r - номер потоку, r = 1., R, - номер учбової групи в потоці r, = 1.,
Розбиття на груп на потоки здійснюється виходячи з принципів:
1. Використання двома групами одного і того ж аудиторного фонду для своїх лекцій автоматично припускає приміщення їх в 1 потік (передбачається, що всі лекції учбових груп проходять разом).
2. Група (або її частина), як одиниця навчального процесу у вузі, може входити в різні потоки, але тільки поодинці раз в кожний з них.
3. Кількість потоків не лімітується.
ЗАНЯТТЯ
Заняття проводяться в робочі дні і триває 1,5год. (пара).
Позначимо:
t - номер робочого дня тижня, де
- безліч номерів робочих днів для групи ;
j - номер пари, j = 1., J;
J - загальна кількість пар.
З кожною учбовою групою потоку r протягом тижня, згідно учбовому плану, проводиться занять, з яких лекційних і практичних. Позначимо:
-номер дисципліни в списку лекційних занять для потоку r,
= 1.,;
- номер дисципліни в списку практичних занять для групи ,
= 1.,.
Передбачається, що лекції проводяться у всіх груп потоку одночасно і в одній аудиторії. Тоді, якщо по якійсь дисципліні протягом тижня проводиться більш ніж одне заняття, ця дисципліна згадується в списку лекцій або практичних занять стільки разів, скільки їх передбачається учбовим планом для кожного потоку або групи.
ВИКЛАДАЧІ
Хай p - номер (ім'я) викладача, p = 1., P. Введемо в розгляд булеві значення і:
{
={
Навчальне навантаження викладачів планується до складання розкладу занять, унаслідок чого на даному етапі величини і: можна вважати заданими. Для кожного викладача p, p = 1.,P, задано також його аудиторне навантаження - годин в тиждень.
АУДИТОРНИЙ ФОНД
Заняття кожного потоку можуть проводитися тільки в певних аудиторіях (наприклад, практичні заняття по інформатиці можуть проводиться тільки в дисплейних класах). Хай:
{ } - безліч аудиторій для лекцій на потоці r;
{} - безліч аудиторій для практичних занять на потоці r;
- число елементів множини {};
- число елементів множини {};
+ - число аудиторій об'єднання множин {}{}.
Аудиторний фонд визначається до початку складання розкладу, тому множини можна вважати заданими.
Завдання складання розкладу полягає у визначенні для кожної лекції (на потоці) і практичного заняття (у групі) дня тижня і пари цього дня з урахуванням виконання конструйованих нижче обмежень і мінімізації деякої цільової функції. Введемо наступні шукані булеві змінні:
= ,
У разі складання розкладу для груп вечірньої форми навчання J=2.
ОБМЕЖЕННЯ
Для кожної групи повинні виконуватися всі види аудиторної роботи протягом тижня:
; (1)
У будь-який день t на кожній парі j для кожної групи може проводитися не більш за одне заняття:
; (2)
Кожна лекція і практичне заняття відповідно для всіх потоків r і всіх груп можуть проводитися не більше одного разу в будь-який день t:
; (3)
Якщо змінні і пов'язують всі види занять з часом їх проведення, то і зв'язують час проведення з ім'ям викладача.
У кожен день і в кожній парі викладач може вести не більш за одне заняття по одній дисципліні на одному потоці або в одній групі:
; (4)
Кожен викладач протягом тижня повинен провести аудиторні заняття:
= (5)
Нарешті, в кожен день на кожній парі число лекцій і практичних занять не повинне перевищувати наявний на факультеті аудиторний фонд:
(6)
(7)
Крім того, для всіх сукупностей пересічних множин {} і {} повинні виконуватися умови:
(8)
Представленими співвідношеннями вичерпуються обмеження, яких дотримуються при складанні розкладу. Зрозуміло,що можуть бути і інші спеціальні умови, але для спрощення моделі вони не розглядалися.
ЦІЛЬВА ФУНКЦІЯ
Щоб повноцінно вести наукову, навчально-методичну роботу, готуватися до занять, викладач вузу повинен мати вільний час. Це умова недостатня, але необхідна. Очевидно, що вільним часом він повинен володітити не в "рваному" режимі, яким, наприклад, є "вікна" між заняттями із студентами, а по можливості в повністю вільні робочі дні. Цьому еквівалентна максимізація аудиторного навантаження викладачів в ті дні, коли вони її мають (формула. (5)). Проте, при цьому претензії на вільний час у викладачів нерівні, оскільки у них різний творчий потенціал. Тому необхідно ввести вагові коефіцієнти, за допомогою яких повинні враховуватися відповідний статус викладача - його вчені ступені і звання, посада, науково-суспільна активність і т.п. В деяких випадках можна на підставі експертних оцінок використовувати індивідуальні вагові коефіцієнти, що враховують інші чинники.
Отже, виберемо критерій якості складання розкладу занять у вигляді максимізації зваженого числа вільних від аудиторної роботи днів для всіх викладачів, що за умови фіксованої довжини робочого тижня еквівалентно максимальному сукупному ущільненню аудиторного навантаження.
Розглянемо вираз для величини аудиторного навантаження в день t викладача p:
(9)
Вводяться обмеження вигляду:
(10)
де M - довільне позитивне чимале число; - шукана булева змінна.
З (10) випливає, що якщо, то = 1, і якщо, то =0
З урахуванням вказаного вище змістовного сенсу критерію оптимізації в додаткових обмеженнях (10), а також вводячи вагові коефіцієнти статусу викладача, отримуємо шуканий критерій оптимальності:
(11)
Введена цільова функція не є єдино можливою. Введення інших цільових функцій не змінює обмежень математичної моделі та методів рішення задачі, але може істотно вплинути на результати обчислень.
МЕТОДИ РОЗВ'ЯЗАННЯ ПОСТАВЛЕНОЇ ЗАДАЧІ
Поставлене в попередньому пункті завдання максимізації лінійної цільової функції при заданій системі обмежень є завданням лінійного цілочисельного булева програмування, оскільки всі коефіцієнти обмежень цілочисельні через дискретність початкових даних завдання; окрім цього шукані змінні математичної моделі можуть приймати тільки два значення. На даний момент часу існує декілька можливих методів розв'язання такого роду завдань.
У (3) - (8) описані методи впорядкованої індексації і модифікованих позначок, засновані на лагранжевій декомпозиції початкової моделі, що розв'язуються відповідно методами упорядковучої індексації, або модифікованих позначок. На жаль кількість операцій кожного з методів не допускає поліноміальної оцінки; крім того, розмірність таблиці наборів (проміжних значень) методів різко зростає при збільшенні розмірності шуканої задачі, що недопускається в нашому випадку. Можливо, зміна алгоритму декомпозиції під конкретну математичну модель дозволить зменшити розмірність таблиць, але поки такого алгоритму не існує.
У зв'язку з цим в якості методів розв'язання були вибрані описані в [2] модифікації симплекс-методу для випадку задачі цілочисельного лінійного програмування. У загальному випадку кількість операцій симплекс-методу не допускає поліноміальной оцінки (був навіть показаний клас завдань, для яких кількість операцій складає), але для випадку нашого завдання середнє число операцій допускає поліноміальную оцінку: (n - кількість змінних; m - кількість обмежень).
ПОВНІСТЮ ЦІЛОЧИСЕЛЬНИЙ АЛГОРИТМ
Цей алгоритм названий повністю цілочисельним, тому що якщо початкова таблиця складається з цілочисельних елементів, то всі таблиці, що виходять в процесі роботи алгоритму, містять тільки цілочисельні елементи. Подібно до двоїстого симплекс-методу, алгоритм починає працювати з двоїсто допустимої таблиці. Якщо (i = 1., n+m; - коефіцієнти цільової функції) - невідємні,
цілі, то задача розвв'язана. Якщо для якого-небудь рядка <0, то складається нове рівняння і записується внизу таблиці. Після цього використовується двоїстий симплекс-метод. Всі елементи додаткового рядка повинні бути цілими числами, а ведучий елемент рівний - 1. Введений таким чином ведучий рядок збереже таблицю цілочисельною.
Хай дано задача цілочисельного лінійного програмування:
максимізувати
за умов
… … …
(12)
,
… … …
Умови (12) можуть бути записані як
(13)
Припустимо, що для t=0 (т.е. для початкової таблиці) все - цілі і стовпці (j = 1., n) - лексикографічно позитивні. Тоді всі стовпці впродовж обчислень залишаються лексикографічно позитивними.
Перш ніж викласти спосіб отримання додаткового обмеження з рядка, що проводить, введемо нове представлення чисел. Нехай [x] позначає найбільше ціле число, не перевишує x. Для будь-якого числа у (додатнього або від'ємного) і позитивного можна записати:
(14)
де (-ненегативний залишок від ділення без остачі у на). Зокрема . Тому якщо, то і r = 1. Якщо, то і r = 0.
Додаткова нерівність, що вводиться, повинна виконуватися при будь-якому цілому рішенні задачі (12). Розглянемо деяке рівняння в t - таблиці (опускаючи індекс рядка) з <0:
(15)
де x - відповідна компоненту вектора, а - поточні небазисні змінні. Можна виразити x, і використовуючи введене вище уявлення (14):
(16)
(17)
Підставивши вирази (16) і (17) в (15) і переставивши члени, отримаємо:
(18)
Оскільки, і на змінні x і накладена вимога позитивності, ліва частина рівняння (18) завжди невід'ємна. Розглянемо вираз в правій частині, поміщений у фігурні дужки. Коефіцієнти в цьому виразі є цілими числами, а змінні підпорядковані вимозі цілочисельності. Тому весь вираз в дужках повинен бути цілим. Позначимо його через s.:
(19).
Цілочисельна слабка змінна s є невід'ємна. Дійсно, якби s було від'ємним, тобто приймало б значення - 1, - 2,., то множення на зробило б всю праву частину рівняння (18), тоді як ліва частина від'ємна.
Розглянемо два випадки і . Для і . Підставляючи в рівняння (19) вираз для x з (15), отримаємо:
(20)
Отримане рівняння є не що інше як відсікання Гоморі. Для маємо і рівняння (19) набуває вигляд:
(21)
Рівняння (21) повинне виконуватися для будь-якого цілочисельного розв'яз-
ку задачі (12). Відмітимо, що якщо <0, то в рівнянні (21) Тому рівняння (21) може використовуватися як ведучий рядок в симплекс-методі. Зокрема, завжди можна вибрати достатньо великим, так щоб провідний елемент в рядку (21) став рівним - 1, що дозволить зберегти цілочисельність таблиці. Вибір відповідного впливатиме на швидкість збіжності алгоритму. Перш за все опишемо сам алгоритм. Як початковий необхідно узяти подвійно допустиме рішення, яке можна отримати додаванням обмеження , де M - достатнь велика стала, і проведенням однієї ітерації з доданим рядком і з лексикографічно мінімальним стовпцем, взятими за ведучих. Алгоритм складається з наступних кроків:
Крок 0. Почати з подвійно допустимої матриці в рівнянні (13), елементи якої - цілі числа (матриця може містити і нецілі елементи,).
Крок 1. Серед рядків з (i=1., n+m) вибрати рядок з найменшим значенням i; цей рядок стане ведучим. (Якщо (i=1., n+m), то задача розв'язана.)
Крок 2. Вибрати (правило вибору буде описано далі) і написати внизу таблиці додатковий рядок
Цей рядок вибирається як ведучій.
Крок 3. Провести крок двоїстого симплекс-метода, викреслити додатковий рядок і повернутися до кроку 1.
Доведення кінцівки алгоритму.
Правило вибору формулюється таким чином.
Крок 0. Хай рядок з номером v є ведучим.
Крок 1. Хай - лексикографічно мінімальний стовпець серед стовпців з . Крок 2. Для кожного хай - найбільше ціле, таке, що (лексикографічно менше). Крок 3. Хай, а (рядок v - що проводить). Тоді . . Крок 4. Покласти для
Правило вибору , описане вище, дозволяє зробити ведучий елемент рівним - 1, при цьому зберігається двоїста допустимість таблиці і в той же час нульовий стовпець буде максимально лексикографічно зменшуватися.
ПРЯМИЙ АЛГОРИТМ ЦІЛОЧИСЕЛЬНОГО ПРОГРАМУВАННЯ
Термін "прямий”, застосований до алгоритму цілочисельного програмування, позначає метод, який приводить до оптимального розв'язку за допомогою отримання послідовно "покращуючих" розв'язків. Кожному з цих розв'язків допустимо в тому сенсі, що він задовольняє як лінійним обмеженням, так і умові цілочисельності. Одним з вірогідних достатків алгоритму є можливість перервати обчислення, до того як отримано оптимальне рішення, і використовувати найкраще з отриманих розв'язків як наближене. Крім того, можна використовувати прямий алгоритм в з'єднанні з двоїстими алгоритмами, щоб отримувати різні складені алгоритми, які можуть переходити від фази, що дає подвійно допустимі розв'язки, до фази, що дає прямо допустимі розв'язки.
Природним прецедентом для прямого алгоритму є повністю цілочисельний алгоритм Гоморі, оскільки в процесі цього алгоритму виходить послідовність подвійно допустимих цілочисельних розв'язків. Слід нагадати, що повністю цілочисельний алгоритм Гоморі є модифікацією двоїстого симплекс-методу. Основна відмінність цього алгоритму полягає в тому, що як ведучий рядок використовується відсікання Гоморі з провідним елементом, рівним - 1. Це відсікання виходить з рядка, що проводить, який визначається як один з можливих провідних рядків в двоїстому симплекс-методі. Використання такого відсікання як ведучий рядок збереже після ітерації подвійну допустимість і цілочисельність таблиці.
Виявляється, можна аналогічно модифікувати симплекс-метод так, щоб отримати алгоритм, який зберігає пряму допустимість і цілочисельність таблиць. Для опису обчислювальної процедури розглянемо наступне завдання цілочисельного програмування:
максимізувати
(22)
за умов
(цілі)
де і - цілі числа і .
Припустимо, що стовпець вибраний як ведучого і рядок - провідний рядок в ітерації симплекс-метода , тобто для всіх рядків , в яких. Перш ніж провести процедуру виключення Гауса в симплекс-методі, додамо до таблиці відсікання Гоморі, отримане з рядка :
де - безліч індексів небазисних змінних в (22), - нова (базисна) слабка змінна і - невизначена (тимчасово) позитивна константа.
Відмітимо, що якщо покласти =, відсікання (23) володітиме двома важливими властивостями. По-перше
Це означає, що пряма допустимість таблиці збережеться, якщо використовувати відсікання (23) як ведучий рядок. По-друге, тобто ведучий елемент рівний 1 (якщо відсікання використовується як провідний рядок). Легко переконатися (шляхом дослідження формул зміни базисних змінних), що перетворення симплексної таблиці з одиничним вудучим елементом зберігає цілочисельність елементів симплексної таблиці.
Ці ідеї послужили підставою прямого алгоритму в цілочисельному програмуванні:
Крок 0. Почати із стовбцевої таблиці, в якій і всіх елементах і - цілі.
Крок 1. Перевірити виконання умов ; якщо вони виконані, то кінець, поточний базисний розв'язок оптимальний; якщо немає - перейти до кроку 2.
Крок 2. Вибрати провідний стовпець з . Вибрати рядок за правилом перевірки відношення серед рядків з . Цей рядок служить Гоморі, що проводить для відсікання.
Крок 3. Отримати відсікання Гоморі з рядка, що проводить, і дописати її внизу таблиці, тобто додати до обмежень завдання рівняння (23), де .
Крок 4. Провести перетворення таблиці, використовуючи відсікання (23) як ведучий рядок. Слабка змінна в (23) стане небазисною. Повернутися до кроку 1.
Висновки
Дана дипломна робота складається з трьох розділів, вступу, деякі історичні відомості, висновки, список використаної літератури, та додатки.
У першому розділі наведенні деякі історичні відомості. Цілочисельне програмування є складовою лінійного програмування основоположником якого вважають радянського вченого Л.В. Канторовича. Сам термін "лінійне програмування" був введений дещо пізніше, в 1951 році, у працях американських вчених Дж. Данцига та Г. Кумпанса. В 1947 році Дж. Данциг розробив основний метод розв'язування задач лінійного програмування - симплексний метод, що стало початком формування лінійного програмування як самостійного напрямку в математичному програмуванні.
Перша задача цілочислового типу яка була опублікована угорським математиком Б. Егерварі в 1932 році, задача про призначення персоналу.
Також в даному розділі наведена загальна постановка цілочисельної задачі та вказуються спеціальні методи для знаходження оптимальних розв'язків таких задач. Це методи відтинання та комбінаторні методи. Основна ідея методів відтинання - поступове "звуження" області допустимих розв'язків розглядуваної задачі. Пошук цілочислового оптимуму починається з розв'язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисловості змінних. Далі вводяться у модель спеціальні додаткові обмеження, що враховують цілочисловість змінних, многокутник допустимих розв'язків послабленої задачі поступово зменшуємо доти, доки змінні оптимального розв'язку не набудуть цілочислових значень. До цієї групи належать:
методи розв'язування повністю цілочислових задач (дробовий алгоритм Гоморі);
методи розв'язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).
Комбінаторні методи цілочислової оптимізації базуються на повному переборі всіх допустимих цілочислових розв'язків, тобто вони реалізують процедуру цілеспрямованого перебору, під час якої розглядається лише частина розв'язків (досить невелика), а решта враховується одним зі спеціальних методів.
В цьому розділі також наведенні конкретні приклади застосування цілочислових задач лінійного програмування у плануванні та управлінні виробництвом, зокрема задача про ранець, задача оптимального розкрою матеріалів, задача комівояжера, задача планування виробничої лінії і т. д
Другий розділ присвячений детальному розгляду методів задач цілочислового програмування. Спочатку було розглянуто графічний метод. Він є досить простий для розуміння. Недоліком є те, що графічним способом можна розв'язати задачу, в якій в обмеженнях є лише дві змінні, потрібно намагатися малювати лінії з найбільшою точністю, в протилежному випадку можна отримати велику похибку, а в результаті неправильне рішення.
Також розглянули алгоритм методу Гоморі, який можна описати за допомогою наступних кроків:
1) знаходимо розв'язок задачі без умов цілочисельності симплекс-методом;
2) якщо оптимальний план цілочисельний, то вибираємо базисну змінну з найбільшою дробовою частиною і за обмеженням цієї змінної будуємо нерівність Гоморі;
3) до обмежень задачі дописуємо побудову задачі нерівність Гоморі: розв'язуємо розширену задачу симплекс-методом і повертаємось до другого кроку. Процес повторюється до тих пір поки оптимальний розв'язок буде цілочисельним або симплекс-таблиці не покажуть що задача не має розв'язку.
Наступним кроком було розглянуто схему процесу розв'язування задачі методом гілок і меж. Вона полягає в тому, що початкова задача розділяється (гілкується) на дві простіші, і, якщо серед них не існує задачі з цілочисловим оптимальним розв'язком, то процес гілкування продовжується.
Третій розділ даної дипломної роботи присвячений розробці математичної моделі складання графіку занять на математичному факультеті ВНЗ.
Завдання теорії розкладів в загальній її постановці вважається дуже привабливим, хоча досягнення навіть невеликого прогресу на шляху до розв'язання зв'язане, як правило, з величезними труднощами. Не дивлячись на те, що завданнями теорії розкладів займалися багато вельми кваліфікованих фахівців, до цих пір нікому не вдалося отримати істотних результатів. Метою даної роботи було створення такої математичної моделі розкладу у вузі, яка дозволяла б ефективно (у задані терміни і із заданим ступенем оптимальності) знаходити задачу автоматичного складання розкладу занять і володіла б гнучкістю (незначних змін у разі змін вхідній інформації) для адаптації системи в рамках конкретного практичного завдання.
Література
1. Акулич И.Л. Математическое программирование в примерах и задачах. - М., 1986. - 320с.
2. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посіб. - К.: Вид-во КНЕУ, 2006-246с.
3. Вентцель Е.С., Исследование операцій. - М.: Сов. радіо, 1972. - 552с.
4. Жильцов О.Б. Кульян В.Р., Юнькова Е.А. Математичне програмування з елементами інформаційних технологій: Навч. посіб. \За ред. О.О. Юнькової. - К.: МАУП, 2006. - 184с.
5. Зайченко Ю. П Исследование операцій. - К. ”Вишая школа”, 1980Костевич Л.С., Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие. - Минск., 2003. - 424с.
6. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М., 1976. - 352с.
7. Кутковецький В.Я., Дослідження операцій: Навч. посіб. - К., 2004. - 350с.
8. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.,”Высшая школа”, 1980.
9. Карманов В.Г. Математическое программирование. - М., Наука, 1986.
10. Романюк Т.П., Терещенко Т.О., Городкова І.М. Математичне програмування.,-К.,ІЗМН., 1996.
11. Суворовський А.А. Математическое программирование. - К.: ІМКВО, 1992.
12. Цегелик Г.Г. Лінійне програмування. - Львів, Світ, 1995.
Додаток а. бібліографія
Леонід Віталійович Канторович (1912-1986) стояв у витоків формування сучасної обчислювальної математики. Перші роботи по наближених методах конформних відображень, варіаційних методах, квадратурних формулах, чисельним методам вирішення інтегральних рівнянь і рівнянь частинних похідних були виконані Л.В. Канторовичем на початку 30-х років.
Л.В. Канторович займався науково-організаційною роботою в Радіанському Союзі. Видатні заслуги Л.В. Канторовича були відмічені державою. Він нагороджений двома орденами Леніна - найвищими нагородами країни, трьома орденами Трудового Червоного Прапора, орденами "Знак Шани" і Вітчизняної війни II ступеня, багатьма медалями. Дослідження Л.В. Канторовича в області функціонального аналізу, обчислювальної математики, теорії екстремальних завдань, дескриптивній теорії функцій і теорії множин зробили вплив на становлення і розвиток вказаних математичних дисциплін, послужили основою для формування нових наукових напрямів.
Джон фон Нейман (при народженні - Янош Лайош Нейман 1903-1957р.).
Неймана вніс значний внесок в розвиток багатьох областей математики, йому належить строге математичне формулювання принципів квантової механіки, а його праця "Математичні основи квантової механіки" є класичним навчальним посібником. Учений став одним з творців теорії ігор, яка лягла в основу математичного підходу до явищ конкурентної економіки, теорії обчислювальних машин і аксіоматичної теорії автоматів. Він вніс великий внесок до створення перших ЕОМ і розробки методів їх застосування. У 1952 році учений розробив перший комп'ютер, що використовує програми, записані на гнучкому носієві.
Джон фон Нейман був членом Національної Академії наук США, Американської філософської спілки, а також почесним членом багатьх зарубіжних академій, наукових установ та об'єднань. Його видатні досягнення відмічені численними престижними преміями. Більше 150 праць вченого присвячено проблемам фізики, математики та їх практичним застосуванням, теорії ігор і комп'ютерної теорії, теорії топологічних груп та метеорології.
Глушков Віктор Михайлович (1923-1982) народився 24 серпня 1923 р. в Ростов-на-Дону в сім'ї гірського інженера. У 1948 р. В.М. Глушков отримав диплом математичного факультету Ростовського університету. З 1951 р. він працював над докторською дисертацією, присвяченій так званій "узагальненій п'ятій проблемі Гільберта" і в 1955 р. блискуче захистив дисертацію. Отримані молодим ученим фундаментальні результати відразу ж поставили його в перші ряди алгебристів країни. Проте несподівано він радикально міняє сферу своєї діяльності. За пропозицією директора Інституту математики АН УРСР Б.В. Гнеденко він в 1956 р. переїжджає до Києва і очолює лабораторію інституту, якою раніше керував академік С.А. Лебедев. З 1962 р. очолював Інститут кібернетики (ДІК) АН УРСР, керував науковими семінарами, мав велику кількість аспірантів і докторів, виступав з доповідями на різних симпозіумах і конференціях, був редактором створеного ним журналу "Кібернетика", консультував десятки організацій, читав лекції, вів велику суспільну роботу.
Круг його наукових інтересів був надзвичайно широкий: теорія цифрових автоматів, алгебра алгоритмів, мови програмування, автоматизація проектування ЕОМ, розпізнавання образів, імітаційне моделювання інтелектуальної діяльності, автоматизовані системи управління технологічними процесами, підприємствами, галузями, безпаперова інформатика і багато іншого.
Він залишив після себе величезну творчу спадщину, численних учнів, відому у всьому світі київську школу кібернетиків і добру пам'ять для нащадків. У 1996 р. міжнародним комп'ютерним співтовариством IEEE (International Electrical and Electronic Engineers) Computer Society академікові В.М. Глушкову присвоєно звання "Computer Pioneer" за його внесок в автоматику та обчислювальну техніку.
Данциг Джордж Бернард (08.11.1914-13.05.2005) американський математик, професор Каліфорнійського університету. Він розробив симплексний алгоритм, для розв'язання задач лінійного програмування, за що його називають "батьком лінійного програмування", (разом з радянським математиком Л.С. Канторовичем).
У 1936 р. отримав ступінь бакалавра по математиці і фізиці в Університеті Меріленда, ступінь магістра математики в Університеті Мічіган і доктора філософії в Університеті Берклі в 1946 р. Став почесним доктором наук від Університету Меріленд в 1976 р. Йому були присуджені: Національна наукова медаль США (1975), Приз Джона фон Неймана (1974), Премія Харві (Ізраїль, 1985). Був членом: Національній Академії Наук, Національної технічної Академії і американської Академії Мистецтв і Наук.
Шаталін Станіслав Сергійович (24.08.1934 - 03.03.1997). Економіст. Закінчив економічний факультет МГУ (1958). Доктор економічних наук (1970).
Професор (1972), завідувач кафедри математичних методів аналізу економіки (1972-1983) економічного факультету Московського університету.
Директор Інституту народногосподарського прогнозування (1986), академік РАН (1987). член Президії АН СРСР (1989-1991).
Нагороджений орденами "Знак Пошани" (1975, 1986), "Дружба народів" (1994). Лауреат Державної премії СРСР (1968), премії ім. B. C. Немчинова (АН СРСР, 1987).), член Президії АН СРСР (1989-1991), голова Наукової ради АН СРСР з проблеми "Соціально-культурний розвиток" (1987-1997), член Президентської ради СРСР (1990-1991), один з авторів економічної програми "500 днів" (1991), голова оргкомітету і президент Міжнародного фонду економічних і соціальних реформ "Реформа" (1992-1994), член Демократичної партії Росії, голова правління Московського союзу споживачів, член Комісії із зовнішньої політики при МЗС РФ (1992-1997), член Комісії при Президентові РФ (1992-1997), член Міжнародного економічного суспільства (1967).
Область наукових інтересів: методологія народно-господарського планування і прогнозування, комплексні проблеми соціально-культурного розвитку і підвищення народного добробуту, економіко-математичне моделювання, методи аналізу і планування міжгалузевих зв'язків і галузевої структури народного господарства.
Размещено на Allbest.ru
Подобные документы
Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
лекция [479,7 K], добавлен 10.10.2013Лінійне програмування як один з найбільш популярних апаратів математичної теорії оптимального управління рішень. Опис існуючих методів розв’язку задач лінійного програмування. Завдання, основні принципи, алгоритми і головна мета лінійного програмування.
курсовая работа [363,8 K], добавлен 03.12.2009Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
курсовая работа [359,5 K], добавлен 18.09.2013Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
контрольная работа [385,2 K], добавлен 04.06.2009Розв’язок багатокритеріальної задачі лінійного програмування з отриманням компромісного рішення (для задач з кількома функціями мети) за допомогою теоретико-ігрового підходу. Матриця мір неоптимальності та рядок функції мети. Модуль опису класу.
курсовая работа [588,8 K], добавлен 15.05.2011Основні визначення дослідження операцій. Модель "затрати-випуск" В.В. Леонтьєва. Загальний вигляд задачі лінійного програмування. Розв'язання за допомогою симплекс-методу. Економічна інтерпретація основної та спряженої задач. Поліпшення плану перевезень.
учебное пособие [1,1 M], добавлен 27.12.2010Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.
курсовая работа [437,9 K], добавлен 24.01.2011Системи автоматичного керування. Описання методу стикування розв'язків на основі теореми по n-інтервалів. Застосування методу динамічного програмування (рівняння Р. Белмана). Моделювання задачі синтезу та аналізу на електронній обчислювальній машині.
контрольная работа [632,5 K], добавлен 31.03.2014Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.
курсовая работа [993,9 K], добавлен 10.12.2010Відомості з теорії графів, методи отримання точних розв'язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп'ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
курсовая работа [335,6 K], добавлен 15.06.2015
