загрузка...

трусы женские
загрузка...

Дослідження операцій

Московський державний

Гірничий університет

Курсовий проект з дослідження операцій.

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

Виконав студент групи

ПМ - 1 - 97
Солодовников Д. А.

Науковий керівник:
Багрова Г.І.

Москва 1999 г.

Зміст:

Мета курсової роботи .......................................... ........................... ..3
Лінійне програмування ............................................................ ..4
Рішення завдання методом лінійного програмування ........................... .6
Цілочисельне лінійне програмування ....................................... ... 9
Рішення завдання методом цілочисельного лінійного програмування ... ... 10
Нелінійне програмування ......................................................... .15
Рішення завдання нелінійного програмування .................................... 15
Динамічне програмування ................................. ..................... ..20
Рішення завдання динамічного програмування ................................. .21
Графічна інтерпретація рішень ...... ............................................. 25
Трудомісткість і ефективність рішення моделі різними методами ...... .27
Про проект ......... ........................................................................... ... 28

Мета курсової роботи.

Вирішити задачу методами лінійного, цілочисельного, нелінійного і динамічного програмування. Зіставити трудомісткість і ефективність рішення моделі різними методами.
Завдання:
Визначити планові завдання добувним підприємствам, якщо в роботі знаходиться N = 12 складів.
Ціна готової продукції 50 у.о. за тонну.
Руда, яка надходить на збагачувальну фабрику повинна мати зміст 29,8 -
29,9%.

| | | |
| Найменування | Одиниці | Підприємства |
| е | Вимірювання | |
| показника | | |
| | | | | |
| | | 1 | 2 | 3 |
| | | | | |
| | | | | |
| Max видобуток | тис. тонн | 740 | 680 | 600 |
| ПІ | | | | |
| Зміст | | | | |
| корисного |% | 29,1 | 29,8 | 30,8 |
| компонента | | | | |
| | | | | |
| Витяг |% | 80 | 75 | 70 |
| Витрати на | | | | |
| видобуток, | у.е . / Т | 6 | 7 | 8 |
| транс-псуй | | | | |
| ровку і | | | | |
| переробку | | | | |
| Проводьте | | | | |
| льность | тис. тонн | 120 | 110 | 106 |
| Складу | | | | |
| Коефіцієнт | | | | |
| збільшення | | | | |
| затрат при | | | | |
| навантаженні: | | | | |
| До 30% - | | 1,8 | 1,7 | 1,9 |
| | | 1,7 | 1,5 | 1,7 |
| 31 - 50% - | | 1,6 | 1,4 | 1,6 |
| | | 1,4 | 1,2 | 1,3 |
| 51 - 70% - | | 1 | 1 | 1 |
| | | | | |
| 71 - 100% - | | | | |
| максимально | | | | |
| й | | | | |

В курсовому проекті введено такі умовні позначення:
ЛП - лінійне програмування;
ЦЛП - целочисленное лінійне програмування;
ДП - динамічне програмування.

Лінійне програмування.

Основне завдання лінійного програмування:
Знайти невід'ємне рішення системи обмежень (1,2) забезпечує максимум (мінімум) цільової функції.
1) Перший канонічний вигляд: a11x1 + a12x2 + ... + a1jxj + ... + a1nxnb1 a21x1 + a22x2 + ... + a2jxj + ... + a2nxnb2

........................ .................. ai1x1 + ai2x2 + ... + aijxj + ... + ainxnbi

. .......................................... am1x1 + am2x2 + ... + amjxj + ... + amnxnbn

xj0; j = 1, n; i = 1, m;

Z = C1x1 + C2x2 + ... + Cjxj + ... + Cnxnmax (min);

2) Другий канонічний вигляд: a11x1 + a12x2 + ... + a1jxj + ... + a1nxn + y1 = b1 a21x1 + a22x2 + ... + a2jxj + ... + a2nxn + y2 = b2

............................................. ai1x1 + ai2x2 + ... + aijxj + ... + ainxn + yi = bi

. ................................. ............ am1x1 + am2x2 + ... + amjxj + ... + amnxn + ym = bn

xj0; j = 1, n; i = 1, m;

Z = C1x1 + C2x2 + ... + Cjxj + ... + Cnxnmax (min);

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

Теореми лінійного програмирования:

Теорема 1 Безліч допустимих рішень основного завдання лінійного програмування опукло.

Теорема 2 Лінійна функція задачі лінійного програмування досягає свого екстремального значення в крайній точці безлічі рішень.


При вирішенні системи обмежень можуть виникнути такі випадки:
1) Система обмежень несовместна, тому відшукати оптимальне рішення неможливо (рис. 1.1).
2) Система обмежень має єдине рішення (рис. 1.2).
3) Система обмежень має кінцеве число рішень (мається замкнута область допустимих рішень). Оптимальне рішення відшукується серед рішень, що належать даній області (рис. 1.3).
4) Система обмежень має незліченну безліч рішень (рис. 1.4).

Рис. 1.1 Рис. 1.2 Рис. 1.3

Рис. 1.4

C

a b

Рис. 2

Симплекс - метод.
Рішення завдання лінійного програмування включає в себе 3 етапи:

1) Відшукання базисного рішення - якійсь точки А (рис. 2) лежачої на функції.
2) Відшукання опорного рішення - якійсь точки B (рис. 2) що належить області, утвореної обмеженнями.
3) Пошук оптимальної рішення - якійсь точки С (рис. 2) що належить тій - же області, і в якій цільова функція досягає свого екстремуму.
Пошук оптимальної рішення з використанням симплекс - методу зводиться до послідовного спрямованого перебору вершин багатогранника, утвореного обмеженнями при якому монотонно збільшується
(зменшується) значення цільової функції.

В даний час рішення задач ЛП за допомогою симплекс - методу реалізується за допомогою ЕОМ.

Рішення завдання методом лінійного програмування.

Симплекс - метод.

Визначити планове завдання добувним підприємствам, якщо в роботі знаходиться N = 12 складів. Ціна готової продукції 50 у.о. за тонну. Руда надходить на збагачувальну фабрику повинна мати зміст Ме (корисного компонента) в межах 29,9 - 29,9%


| | | |
| Найменування | Одиниці | Підприємства |
| е | Вимірювання | |
| показника | | |
| | | | | |
| | | 1 | 2 | 3 |
| | | | | |
| | | | | |
| Max видобуток | тис. тонн | 740 | 680 | 600 |
| ПІ | | | | |
| Зміст | | | | |
| корисного |% | 29,1 | 29,8 | 30,8 |
| компонента | | | | |
| | | | | |
| Витяг |% | 80 | 75 | 70 |
| Витрати на | | | | |
| видобуток, | у.е . / Т | 6 | 7 | 8 |
| транс-псуй | | | | |
| ровку і | | | | |
| переробку | | | | |
| Продуктивність т | | | | |
| ельность | тис. тонн | 120 | 110 | 106 |
| | | | | |
| Складу | | | | |

x1, x2, x3 - кількість складів виділених відповідно підприємствам
1, 2 і 3

Обмеження:
. За кількістю складів:

, де n - кількість підприємств, N - кількість складів.
1. x1 + x2 + x312
. За максимальним обсягом видобутку руди з кожного з підприємств:

, де
2. 120x1 740 або x16,16666 (для підприємства 1);
3. 110x2 680 або x2 6,18181 (для підприємства 2);
4. 106x3 600 або x3 5,6603 (для підприємства 3).
. За змістом корисного компонента в руді: за формулою:

де
(min - мінімально допустимий вміст корисного компонента в руді,
( max - максимально допустимий вміст корисного компонента в руді,
(i - вміст корисного компонента в руді i - того підприємства, qi - продуктивність складу i - того підприємства, маємо:

Спростимо нерівності 5, 6:
5. 34,92x1 + 32,78x2 + 32,648x3 - 35,76x1 - 32,78x2 - 31,588x30

- 0,84x1 + 1,06x30; (обмеження по мінімально допустимому вмісту корисного компонента в руді);
6. 34,92x1 + 32,78x2 + 32,648x3 - 35,88x1 - 32,89x2 - 31,694x30

-0,96x1 - 0,11x2 + 0,954x30

0,96 x1 + 0,11x2 - 0,954x30; (обмеження по максимально допустимому вмісту корисного компонента в руді);

Цільова функція:

, де - ціна готової продукції (у.о. за тонну);

Z = 676800x1 + 459250x2 + 294660x3
Або в тис. тонн:

Z = 676,8x1 + 459,25x2 + 294,66x3

Висновок:
В результаті рішення даної задачі було отримано значення цільової функції
Z = 6048,2412; x1 = 6,16667 - кількість складів для підприємства 1; x2 = 0,94654 - кількість складів для підприємства 2; x3 = 4,88679 - кількість складів для підприємства 3;
Для отримання найбільшої вигоди (цільова функція прагне до максимуму досягає свого екстремуму) необхідно виконання підприємствами наступного плану:
Підприємство 1 - Р (план) = 740 - y2 = 740 - 0 = 740 тис. тонн,
Підприємство 2 - Р (план) = 680 - y3 = 680 - 575,88043 = 104,11957 тис. тонн,
Підприємство 3 - Р (план) = 600 - y4 = 600 - 82,00002 = 517,99998 тис. тонн.

Цілочисельне лінійне програмування.
При вирішенні деяких задач лінійного програмування буває необхідно отримати цілочисельне рішення, яке знаходиться методами цілочисельного лінійного програмування.
Задача цілочислового лінійного програмування це задача, де деякі або всі змінні повинні приймати строго цілочисельні значення, а цільова функція й обмеження - лінійні.
В деяких завданнях цілочисельні значення можуть бути рівні тільки 0 або
1, тоді такі завдання називаються завданнями з булевими змінними.
Задачу целочисленного лінійного програмування можна вирішити як задачу лінійного програмування, а потім округлити отримане рішення. Однак такий спосіб допустимо тільки за умови, що значення змінних настільки великі, що похибкою, спричиненої округленням можна знехтувати. Якщо ж в результаті рішення мінлива приймає мале значення, то її округлення може привести до дуже далекому від оптимального рішення. Застосовуються два способи вирішення задач ЦЛП - метод відсікань і метод гілок і меж.

Рішення завдання ЦЛП методом відсікання:
1. Рішення завдання як завдання ЛП.
2. Якщо ми отримали цілочисельне рішення, то воно і є вирішенням завдання ЦЛП.
3. Якщо ми отримуємо нецелочисленное рішення, то ми до системи обмежень задачі ЛП додаємо таке обмеження, що отримане нецелочисленное оптимальне рішення не може міститися в безлічі допустимих рішень і, таким чином, формуємо нову задачу

Сторінки: 1 2
загрузка...
ur.co.ua

енциклопедія  з сиру  аджапсандалі  ананаси  узвар