WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

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

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


Реферат на тему:
Цілочислові задачі лінійного програмування. Деякі з основних методів їх розв'язування та аналізу.
План.
1. Економічна і геометрична інтерпретація задачі цілочислового програмування.
2. Приклади розв'язування задач.
3. Література
Цілочислові задачі лінійного програмування.
1. Економічна і геометрична інтерпретація задачі цілочислового програмування. Екстремальна задача, перемінні якої приймають лише цілочислові значення, називається задачею цілочислового програмування.
У математичній моделі задачі цілочислового програмування, як цільова функція, так і функції в системі обмеженні можуть бути лінійними, нелінійними і змішаними. Обмежимося випадком, коли цільова функція і система обмежень задачі є лінійними.
2.40. У цеху підприємства вирішено установити додаткове устаткування, для розміщення якого виділено 19/3 м2 площі. На придбання устаткування підприємство може витратити 10 тис. грн.., при цьому воно може купити устаткування двох видів. Комплект устаткування І виду коштує 1000 грн., а II виду - 3000 грн. Придбання одного комплекту устаткування І виду дозволяє збільшити випуск продукції в зміну на 2 од., а одному комплекті устаткування II виду - на 4 од. Знаючи, що для установки одному комплекті устаткування І виду потрібно 2 м2 площі, а устаткування II виду-1 м2 площі, визначити такий набір додаткового устаткування, що дає можливість максимально збільшити випуск продукції.
Рішення. Складемо математичну модель задачі. Припустимо, що підприємство придбає х1 комплектів устаткування І виду і х2 комплектів устаткування II виду. Тоді перемінні х1 і х2 повинні задовольняти наступним нерівностям:
Якщо підприємство придбає зазначену кількість устаткування, то загальне збільшення випуску продукції складе
F=2x1+4x2 (25)
По своєму економічному змісті перемінні х1 і х2 можуть приймати лише цілі ненегативні значення, тобто
(26)
цілі. (27)
Таким чином, приходимо до наступного математичного задачі: знайти максимальне значення лінійної функції (25) при виконанні умові (24), (26) і (27). Тому що невідомі можуть приймати тільки цілі значення, то задача (24) - (27) є задачею цілочислового програмування. Оскільки число невідомих задачі дорівнює двом, рішення даної задачі можна знайти, використовуючи її геометричну інтерпретацію. Для цього, насамперед, побудуємо багатокутник рішення задачі, що складає у визначенні максимального значення лінійної функції (25) при виконанні умові (24) і (26) (мал. 2.2). Координати всіх точок побудованого багатокутника рішення ОАЕВС задовольняють систему лінійних нерівностей (24) при умові незаперечності перемінних (26). Разом з тим умові (27), тобто умові цілочисловості перемінних, задовольняють координати лише 12 крапок, відзначених на мал. 2.2.
Щоб знайти точку, координати якої визначають рішення вихідної задачі, замінимо багатокутник ОАВС багатокутником ОКЕММР, що містить усі припустимі точки з цілочисловими координатами і таким, що координати кожної з вершин є цілими числами. Виходить, якщо знайти точку максимуму функції (25) на багатокутнику ОКЕМNР, то координати цієї точки і визначать оптимальний план задачі.
Для цього побудуємо вектор =(2; 4) і пряму 2х1 + 4х2 =12, що проходить через багатокутник рішенні ОКЕМNР (число 12 узяте довільно). Побудовану пряму пересуваємо в напрямку вектора З доти, поки вона не пройде через останню загальну точку її з даним багатокутником. Координати цієї точки і визначають оптимальний план, а значення цільової функції в ній є максимальним.
У даному випадку шуканої є точка Е(1;3), у якій цільова функція приймає максимальне значення Fмах=14. Отже, координати точки Е визначають оптимальний план задачі (24) - (27). Відповідно до цього плану підприємству варто придбати один комплект устаткування І виду і три комплекти устаткування II виду. Це забезпечить підприємству при наявних у нього обмеженнях на виробничі площі і кошти максимальне збільшення випуску продукції, рівне 14 од. у зміну.
2.41. Для виконання робіт можуть бути використані п механізмів. Продуктивність і-го механізму (і=1,п) при виконанні j-и роботи ( ) дорівнює сij. Припускаючи, що кожен механізм може бути використаний тільки на одній роботі і кожній роботі може виконуватися тільки одним механізмом, визначити закріплення механізмів за роботами, що забезпечує максимальну продуктивність. Побудувати математичну модель задачі.
Рішення. Уведемо перемінну хij, значення якої дорівнює 1, якщо при виконанні і-и роботи використовується j-и механізм, і дорівнює 0 у противному випадку. Тоді умови використання кожного механізму тільки на одній роботі виражаються рівностями
(28)
а умови виконання роботи тільки одним механізмом - рівностями
(29)
якщо i-у роботу виконує j-и механізм;
у противному випадку.
Таким чином, завдання полягає у визначенні таких значенні невідомих хij (j = ; j = ), що задовольняють системам рівнянні (28) і (29) і умові (З0), при яких досягається максимальне значення функції
(31)
Сформульована задача є задачею цілочислового програмування.
Знайдіть рішення задач цілочислового програмування 2.42- 2.44.
2.42.
2.43.
2.44.
х1, х2, х3, х4, х5 ?0,
х1, х2, х3, х4, х5 - цілі.
Складіть математичні моделі задач 2.45-2.48.
2.45. Міністерству необхідно скласти план розвитку кожного з т підприємстві, що випускають однорідну продукцію. Число можливих варіантів розвитку ?-го підприємства по-різному і дорівнює п?. Реалізація ј-го варіанта розвитку і-го підприємства ( ) вимагає капітальних витрат, рівних ДО?ј, і забезпечує випуск продукції в обсязі b?ј одиниць. При цьому економічний ефект від капітальних вкладений на розвиток і-го підприємства по ј-му варіанті дорівнює з?ј. З огляду на, що необхідно випустити продукції в кількості В одиниць і що загальна величина капіталовкладенні обмежена і дорівнює ДО, скласти такий план розвитку підприємстві, при якому економічний ефект від реалізації обраних варіантів розвитку підприємстві є максимальним.
2.46. В аеропорті для перевезення пасажирів по п маршрутах може бути використано т типів літаків. Місткість літака і-го типу дорівнює а, людина, а кількість пасажирів, перевезених по ј-му маршруті за сезон, складає bј людина. Витрати, зв'язані з використанням літака і-го типу на ј-м маршруті, складають сіј руб.
Визначити, скільки літаків даного типу і на якому з маршрутів варто використовувати, щоб задовольнити потреби в перевезеннях при найменших загальних витратах.
2.47. У взуттєвому виробничому об'єднанні виробляються розкрої т різні партії матеріалів, причому кожна з партії складається з bіј, одиниць матеріалу, що має однакову форму (наприклад, пластини) і розмір. З матеріалів усіх партії потрібно викроїти максимальна кількість комплектів деталей взуття, у кожний з який входить деталей ј-говиду, якщо при розкрої одиниці матеріалу і-и партії по k-му варіанті виходить аіј, деталей ј-го виду.
2.48. Мається п міст, відстань між будь-якими двома з який дорівнює сіј. Знайти маршрут, що має мінімальну довжину, що починається і кінчається в тому самому місті і включає по одному разі всі інші міста.
Література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти) "Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.270-274.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с.
Loading...

 
 

Цікаве