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

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

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


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


План.
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  2  3 



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

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