трусики женские украина

На головну

 Дослідження операцій - Теорія організації

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

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

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

Рішення завдання методами лінійного,

целочисленного, нелінійного і динамічного

програмування.

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

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

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

Москва 1999

Зміст:

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

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

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

Целочисленное лінійне програмування ....................................... ... 9

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

Нелінійне програмування ......................................................... .15

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

Динамічне програмування ...................................................... ..20

Рішення завдання динамічного програмування ................................. .21

Графічна інтерпретація рішень ................................................... 25

Трудомісткість і ефективність рішення моделі різними методами ...... .27

Про проект .................................................................................... ... 28

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

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

Завдання:

Визначити планові завдання добувним підприємствам, якщо в роботі знаходиться N = 12 складів.

Ціна готової продукції 50 у.о. за тонну.

Руда, яка надходить на збагачувальну фабрику повинна мати зміст 29,8 - 29,9%.

 Найменування показника

 Одиниці

 Вимірювання Підприємства

1

 2 Березня

 Max видобуток

 ПІ тис. Тонн 740680600

 Вміст корисного компонента% 29,1 29,8 30,8

 Витяг% 80 75 70

 Витрати на видобуток, транс-портування і переробку у.о. / Т 6 7 8

 Продуктивність

 Складу тис. Тонн 120110

 106

 Коефіцієнт збільшення витрат при навантаженні:

 До 30% -

 31 - 50% -

 51 - 70% -

 71 - 100% -

 максимальної

 1,8

 1,7

 1,6

 1,4

1

 1,7

 1,5

 1,4

 1,2

1

 1,9

 1,7

 1,6

 1,3

1

У курсовому проекті введені такі умовні позначення:

ЛП - лінійне програмування;

ЦЛП - целочисленное лінійне програмування;

ДП - динамічне програмування.

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

Основна задача лінійного програмування:

Знайти невід'ємне рішення системи обмежень (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 Березня

 Max видобуток

 ПІ тис. Тонн 740680600

 Вміст корисного компонента% 29,1 29,8 30,8

 Витяг% 80 75 70

 Витрати на видобуток, транс-портування і переробку у.о. / Т 6 7 8

 Продуктивність

 Складу тис. Тонн 120110

 106

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

Обмеження:

· За кількістю складів:

,

де n - кількість підприємств, N - кількість складів.

1. x1 + x2 + x312

· По максимального обсягу видобутку руди з кожного з підприємств:

, Де

2. 120x1740 або x16,16666 (для підприємства 1);

3. 110x2680 або x26,18181 (для підприємства 2);

4. 106x3600 або x35,6603 (для підприємства 3).

· За змістом корисного компонента в руді:

за формулою:

де

amin- мінімально допустимий вміст корисного компонента в руді,

amax- максимально допустимий вміст корисного компонента в руді,

ai- вміст корисного компонента в руді 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. Якщо ми отримаємо оптимальні цілочисельні рішення задачі ЛП, то вони є також і оптимальними рішеннями завдання ЦЛП.

3. Якщо ми не отримаємо цілочисельних рішень, то цільова функція Z1задачі ЛП стає верхньою межею оптимального значення Z завдання ЦЛП, тому що значення цільової функції Z при введенні надалі нових обмежень для отримання оптимальних цілочисельних рішень зменшується.

4. Потім проводиться розгалуження по одному з нецілочисельне оптимальних рішень задачі ЛП. Розгалуження здійснюється з використанням деяких правил за наступною схемою: якщо nxn + 1, то 1) xn; 2) xn + 1, де х - нецілочисельне оптимальне рішення задачі ЛП, за яким ми здійснюємо розгалуження, n - найближче ціле до х що не перевищує х.

Правила розгалуження:

1) Вибирається змінна, у якої дрібна частина найбільш близька до 0,5.

2) Вибирається змінна з найбільшим пріоритетом за будь - яким якісному або кількісному значенню.

3) Мінлива вибирається довільно.

Обмеження введені при розгалуження додаються до обмежень задачі ЛП.

У кожній з вершин знаходимо оптимальні рішення отриманих шляхом додавання нових обмежень задач ЛП - 2 і ЛП - 3. Якщо не в однієї з них ми не отримали цілочисельних оптимальних рішень, то ми вибираємо ту вершину, в якій отримано найбільше значення цільової функції і робимо подальший розгалуження. Так продовжується до отримання цілочисельного оптимального рішення одним із завдань ЛП.

Вершина називається прозондувати, якщо:

1) Ми знайшли в ній оптимальне цілочисельне рішення - рішення задачі ЦЛП.

2) У даній вершині немає оптимальних рішень задачі ЛП.

3) Значення Z в оптимальному рішенні задачі ЛП не більш поточної нижньої межі.

Інші вершини називаються висячими.

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

Метод гілок і меж.

Початкові умови беруться з рішення задачі ЛП (рішення див. Вище).

1. Вершина 1 x1 = 6,17 x2 = 0,9 x3 = 4,9 Z1 = 6048,24

Почнемо розгалуження по x1 = 6,17, тоді отримуємо додаткові обмеження а) x16 (1 гілка) б) x27 (2 гілка).

Вирішуємо спочатку гілку 1. До обмежень задачі ЛП додаємо обмеження а.

Отримуємо сьомим обмеженням обмеження x16;

Рішення:

2. Вершина 2 x1 = 6 x2 = 1,2 x3 = 4,8 Z2 = 6033,7212

Ми отримали одне цілочисельне рішення x1 = 6, отже подальше розгалуження ми будемо проводити по x2ілі x3.

Вирішуємо гілку 2. До обмежень задачі ЛП додаємо обмеження б.

Сьомим обмеженням стає обмеження x17.

Рішення:

Другий рядком є ??обмеження задачі ЛП за максимально можливого обсягу руди з 2 підприємства:

120x1740 або x16,16666, що суперечить введеному нами умовою 6 (б) x17. Подальше розгалуження з вершини 3 неможливо.

Продовжимо розгалуження з вершини 2. Як було вже сказано вище, ми можемо продовжити розгалуження по x2ілі x3. Продовжимо розгалуження по x2. x2 = 1,2, отже восьме обмеження для 1 гілки буде x21, а для іншої x2. Рухаємося спочатку по гілці 1 у вершину 4.

Рішення:

X1 = 6 x2 = 1 x3 = 5 Z4 = 5993,3501

Ми отримали, що всі три змінних мають цілочисельне значення,

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

Z5 = 5991,0396, отже Z5 Інтерпретація рішення за допомогою блок - схеми:

x1 = 6,1

Z1 = 6048 x2 = 0,9

x3 = 4,9

x16 x17

x1 = 6

x2 = 1,2 Система

x3 = 4,8 несовместна

x21 x22

x1 = 6 x1 = 5,6

x2 = 1 x2 = 2

x3 = 5 x3 = 4

Z = 5993 Z = 5991

 Вершина Обмеження № обмеження

2

 x 1 6 липня

3

 x 1 7 липня

4

 x 6 січня

 x 1 лютого

7

8

5

 x 6 січня

 x 2 лютого

7

8

Висновок:

В результаті рішення я отримав, що целочисленное оптимальне рішення виходить у вершині 4, так як всі значення x1 = 6, x2 = 1, x3 = 5 в цій вершині цілочисельні і Z5 (5991)Планові завдання:

, Де P - планове завдання тис. Тонн, q - продуктивність складу, x - кількість складів, i - номер підприємства.

Для підприємства 1:

тис. тонн;

Для підприємства 2:

тис. тонн;

Для підприємства 3:

тис. тонн.

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

Завдання математичного програмування називається нелінійною, якщо нелінійні обмеження або цільова функція.

Задачі нелінійного програмування бувають опуклого і неопуклого програмування, з обмеженнями і без обмежень, з квадратичними або сепарабельного цільовими функціями. Задачі нелінійного програмування мають безліч екстремальних точок, і складність рішення полягає у виділенні глобального оптимуму, а не локального як це робиться в більшості класичних методів.

Поділяють задачі безумовної та умовної оптимізації. Завданнями безумовної оптимізації називаються задачі оптимізації функції багатьох змінних без додаткових обмежень. Існують наступні методи безумовної оптимізації: покоордінатного спуску, градієнтні, поєднаних напрямів, метод Ньютона. Завданнями умовної оптимізації називаються задачі про оптимізації цільової функції багатьох змінних f (x1, ..., xn) за умови, що ці змінні задовольняють наступним обмеженням:

qi (x1, ..., xn) = 0,

або

dj (x1, ..., xn) 0,

Рішення задачі грунтується на лінійній або квадратичної апроксимації цільової функції для визначення збільшень x1, ..., xnна кожній ітерації.

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

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

Метод кусково - лінійної апроксимації.

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

Складемо таблицю:

 № підприємства

 Коефі-

 Ціент

 витрат% Количе-ство складів

 Переходи.

 зраді-ня витрат Витрати на 1т у.о. Дохід

 Прибуток

 На 1т

 у.о.

 Прибуток на 1 склад

 у.о.

 1 2 3 4 5 6 7 8

 ? 100 6,17 1 6 11,64 5,64 676,8

 70 - 100 4.31-6,16 1,4 8,4 3,24 388,8

 50 - 70 3,08-4,31 1,6 9,6 2,04 244,8

 30 - 50 1,85-3,08 1,7 10,2 1,44 172,8

 до 30 до 1,85 1,8 10,8 0,84 100,8

 ? 100 6,18 1 7 11,175 4,175 459,25

 70 - 100 4,33-6,18 1,2 8,4 2,775 305,25

 50 - 70 3,09-4,33 1,4 9,8 1,375 151,25

 30 - 50 1,85-3,09 1,5 10,5 0,675 74,25

 до 30 до 1,85 1,7 11,9 - 0,725 - 79,75

 Z 100 5,66 1 8 10,78 2,78 294,66

 70 - 100 3,96-5,66 1,3 10,4 0,38 40,28

 50 - 70 2,83-3,96 1,6 12,8 - 2,02 - 214,12

 30 - 50 1,7 - 2,83 1,7 13,6 - 2,82 - 298,92

 до 30 до 1,7 1,9 15,2 - 4,42 - 458,52

Де дохід (Д) розраховується за формулою:

, Де

Ц - ціна готової продукції, Е - витяг, a - вміст корисного компонента.

Прибуток (П) розраховується за формулою:

П = Д - З, де Д - дохід, З - витрати.

Витрати (З) розраховуються за формулою:

, Де С - витрати на видобуток, транспортування та переробку, - коефіцієнт зміни витрат.

1. Нехай x1, x2, x3прінімают свої максимальні значення, тоді

Z1 = 676,8x1 + 459,25x2 + 294,66x3MAX

Обмеження:

x1 + x2 + x3 = 12 - за кількістю складів;

x16,17 - максимальний обсяг видобутку руди з підприємства 1;

x26,18 - максимальний обсяг видобутку руди з підприємства 2;

x35,66 - максимальний обсяг видобутку руди з підприємства 3;

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

-0,84x1 + 1,06x30 - по мінімально допустимому вмісту

корисного компонента в руді.

Рішення 1.

x1 = 6,17 x2 = 0,95 x3 = 4,88 Z1 = 6048,24

2. Так як x1 = 6,17 - максимально можливий, то коефіцієнт при x1в

цільової функції Z2будет дорівнює 676, 8.

Так як x2 = 0,95; x2 <1,87, то коефіцієнт при x2в цільової функції Z2будет равнятся -79,75.

Так як x3 = 4,88; 3,96 <4,88 <5,66, отже x3попадает в інтервал 3,96 - 5,66, отже коефіцієнт при x3в цільової функції Z2будет дорівнює 40,28.

Отже Z2 = 676,8x1- 79,75x2 + 40,28x3

Рішення 2.

x1 = 6,17 x2 = 0,17 x3 = 5,66 Z2 = 4387,26

3. Так як x1 = 6,17 - максимально можливий, то коефіцієнт при x1в

цільової функції Z3будет дорівнює 676, 8.

Так як x2 = 0,17; x2 <1,87, то коефіцієнт при x2в цільової функції Z3будет равнятся -79,75.

Так як x3 = 5,66 - максимально можливий, то коефіцієнт при x3в

цільової функції Z3будет дорівнює 294,68.

Отже Z3 = 676,8x1- 79,75x2 + 294,68x3

Рішення 3.

x1 = 6,166 x2 = 0,17 x3 = 5,66 Z3 = 5827,16

Висновок:

Так як на третьому кроці ми отримали значення змінних рівних значень змінних на другому кроці, то ми отримали шукане рішення задачі нелінійного програмування. Третій крок, за рахунок того, що значення коефіцієнта при x3билі збільшені з 40,28 до 294,68, поліпшив цільову функцію Z3на 5827,16 - 4387,26 = 1439,9 у.о.

Планові завдання підприємствам.

, Де P - планове завдання тис. Тонн, q - продуктивність складу, x - кількість складів, i - номер підприємства.

Для підприємства 1:

тис. тонн;

Для підприємства 2:

тис. тонн;

Для підприємства 3:

тис. тонн.

Апроксимація кривої залежності витрат від кількості складів. Приклади графіків для підприємств 1 і 2.

Динамічне програмування. (ДП)

Динамічними називаються завдання економіки, організації та управління, в яких необхідно розподіляти ресурси на кожному етапі якого - або проміжку (часу). Формулювання завдання ДП:

Є якась система S, що знаходиться в первісному стані S. Дана система має будь - які параметри. При переході системи з однієї точки в іншу необхідно в кожен момент часу вибирати напрямок подальшого руху з декількох допустимих напрямів за умови, що кожному напрямку відповідає своя ефективність (параметри системи змінюються по різному), і необхідно таким чином спланувати маршрут з початкової точки в кінцеву, щоб критерій ефективності досягав екстремального значення.

Іншими словами з безлічі допустимих управлінь U = (U1, U2, ..., Un) необхідно знайти оптимальне, при якому система переходить зі свого початкового стану в кінцеве таким чином, що критерій оптимальності W досягає свого максимуму.

Динамічне програмування являє собою метод оптимізації багатокрокових процесів по кроках. Локальний оптимум на кожному кроці повинен розраховуватися не як оптимальний на даному етапі, а як дає максимальне значення критерію оптимальності в кінці руху. Недотримання цього правила призводить до серйозних помилок, тому при вирішенні завдань ДП рухаються зазвичай з кінця шляху в початок, розраховуючи витрати при русі в кожному напрямку, а потім з початку в кінець, знаходячи локальний оптимум з розрахованих витрат на кожному кроці. Таким чином отримуємо максимальне значення критерію оптимальності.

В основі розрахунків методом динамічного програмування лежить принцип Беллмана. Він звучить:

оптимальне управління володіє тим властивістю, що Какава б не були досягнуті стану та рішення до даного моменту, подальше рішення має становити оптимальну поведінку щодо стану, досягнутого на даний момент.

Рішення задачі динамічного програмування.

Розподіл ресурсів підприємствам.

Дані візьмемо з задачі нелінійного програмування: кількість складів і прибуток на 1 склад для кожного підприємства:

Підприємство 1.

 Кількість складів Прибуток на 1 склад

 6,17 676,8

 4,31 - 6,17 388,8

 3,08 - 4,31 244,8

 1,85 - 3,08 172,8

 до 1,85 100,8

Підприємство 2.

 Кількість складів Прибуток на 1 склад

 6,18 459,25

 4,33 - 6,18 305,25

 3,09 - 4,33 151,25

 1,85 - 3,09 74,25

 до 1,85 -78,75

Підприємство 3.

 Кількість складів Прибуток на 1 склад

 5,66 294,68

 3,96 - 5,66 40,28

 2,83 - 3,96 -214,12

 1,7 - 2,83 -298,92

 до 1,7 -458,52

Кількість складів, виділених всім трьом підприємствам (N), дорівнює 14.

Розрахуємо ефективність використання коштів підприємствами. Для цього прибуток на один склад помножимо на кількість складів, при яких досягається цей прибуток на кожному з підприємств.

, Де n - кількість складів, Pn- прибуток при цьому кількості складів.

 Кількість складів Підприємство 1 Підприємство 2 Підприємство 3

 1 100,8 -78,15 -458,52

 2 345,6 148,5 -597,94

 3 518,4 222,75 -642,36

 4 979,2 605 161,12

 Травня 1944 1526,25 201,40

 6 2332,8 1831,5 1768,08

Рассчітаем- максимально можливу кількість складів для підприємств 1 і 2.составов. Тепер розрахуємо мінімально можливу кількість складів для підприємств 1 і 2, виходячи з того, що максимально можлива кількість складів для підприємства 3 одно = 6 складів, тогдасоставов. Складемо таблицю виділення коштів двом підприємствам (1 і 2). Тут x - загальна кількість ресурсів (складів) для двох підприємств; x = x1 + x2; 0x16 - допустима кількість складів для підприємства 1; 0x26 - допустима кількість складів для підприємства 2. Звідси видно, що 0x, проте кількість складів для підприємства 3 не може перевищувати 6, отже x, следовательноx; 8x12. q1, q2- ефективність використання коштів підприємствами 1 і 2 відповідно взята з попередньої таблиці. W2 = q1 + q2- сумарна ефективність обох предпріятій.Наібольшую сумарну ефективність для кожного значення x будемо підкреслювати.

x

 x 1

 X 2 Ефективність

 q 1

 q 2

 W 2

 8 2 6 345,6 1831,5 2177,1

 3 5 518,4 1526,25 2044,65

 4 4 979,2 605 1584,2

 3 травня 1944 222,75 2166,75

 2 червня 2332,8 148,5

 2481,3

 9 3 6 518,4 1831,5 2349,9

 4 5 979,2 1526,25 2505,45

 5 4 1944 605 2549

 3 червень 2332,8 222,75

 2555,55

 10 4 6 979,2 1831,5 2810,7

 5 травня 1944 1526,25

 3470,25

 6 4 2332,8 605 2937,8

 11 5 6 1944 1831,5 3775,5

 5 червня 2332,8 1526,25

 3859,05

 12 6 6 2332,8 1831,5

 4164,3

Тепер складемо таблицю виділення коштів всім трьом підприємствам. Так як N - загальна кількість складів одно 14, а максимально можливу кількість складів для підприємств 1 і 2 = 12, то всім трьом підприємствам може бути виділено 13 або 14 складів. W3- сумарна ефективність всіх трьох підприємств.

 Кількість

 Складів

 x 3 x Ефективність використання ресурсів

 q 3

 W 2

 W 3

 13 1 12 -458,52 4164,3

 3705,78

 2 11 -597,94 3859,05 3261,11

 3 10 -642,36 3470,25 2827,89

 4 9 161,12 2555,55 2716,67

 5 8 201,4 2481,3 2682,7

 14 2 12 -597,94 4161,3 3563,36

 3 11 -642,36 3859,05 3216,69

 4 10 161,12 3470,25 3631,12

 5 9 201,4 2555,55 2756,95

 8 червні 1768,08 2481,3

 4249,38

W3максімальное одно 4249,38, отже Z = 4249,38.

x3 = 6; x2 = 2; x3 = 6.

Висновок:

В результаті рішення задачі динамічного програмування я отримав, що максимальне значення цільової функції Z == 4249,38 виходить при кількості складів, виділених 3 підприємствам N = 14, і кількості складів виділених підприємству 3 x3 = 6. При цьому кількість складів для підприємств 1 і 2 дорівнює 8. Максимальна ефективності використання 8 складів підприємствами 1 і 2 досягається при виділенні підприємству 1 - 6 складів, а підприємству 2 - 2 складу, і вона дорівнює 2481,3. Отже x1 = 6, x2 = 2, x3 = 6, Z = 4249,38.

Планові завдання підприємствам:

, Де P - планове завдання тис. Тонн, q - продуктивність складу, x - кількість складів, i - номер підприємства.

Для підприємства 1:

тис. тонн;

тис. тонн;

тис. тонн.

Графічна інтерпретація рішень.

1. Рішення завдання ЛП.

З обмеження 1 задачі ЛП:

Висловимо

Обмеження:

1) x16,17, значить 12 - x2- x36,17;

x2 + x35,84

y1 = x2 + x3 = 5,84

x3 = 5,84 - x2;

2) x26,18

y2 = x2 = 6,18;

3) x35,66

y3 = x3 = 5,66;

4) 0,96 x1 + 0,12 x2- 0,95 x30

0,96 (12 - x2- x3) + 0,12 x2- 0,95 x30

-0,84 X2- 1,9 x311,52

0,84 x2 + 1,9 x311,52

y4 = 0,84 x2 + 1,9 x3 = 11,52

;

5) -0,84 x1 + 1,06 x30

-0,84 (12 - x2- x3) + 1,06 x30

0,84 x2 + 0,84 x3 + 1,06 x310,08

0,84 x2 + 1,9 x3 = 10,08

;

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

Z = 676,8 (12 - x2- x3) + 459,25 x2 + 294,66 x3 = 8121,6 - 217,55 x2- 382,14 x3;

Розглянемо, що відбувається з графіком цільової функції при її збільшенні:

1) Z1 = 8000

8121,6 - 217,55 x2- 382,14 x3 = 8000

-217,55 X2- 382,14 x3 = 8000 - 8121,6

217,55 x2 + 382,14 x3 = 121,6

;

 X 2 0 3

 X 3 0,32 -1,39

2) Z2 = 9000

-217,55 X2- 382,14 x3 = 9000 - 8121,6

217,55 x2 + 382,14 x3 = - 878,4

 x 2 0 -3

 x 3 -2,3 -0,6

Ми отримали, що графік функції Z2расположен нижче ніж графік функції Z1. Однак Z2> Z1 (9000> 8000). Отже свого максимального значення цільова функція досягає в самій нижній точці області щодо цільової функції (в тій точці, через яку графік цільової функції буде проходити перший при зменшенні цільової функції). Позначимо цю точку на графіку A. Координати точки A (0,95; 4,89). x2 = 0,95; x3 = 4,89, що відповідає рішенню за допомогою симплекс - методу.

2. Завдання ЦЛП.

Максимального значення цільова функція задачі ЦЛП досягає при x2 = 1, x3 = 5. На графіку вирішення завдання ЦЛП - точка B з координатами (1; 5).

3. Завдання нелінійного програмування.

x2 = 0,17, x3 = 5,66. На графіку точка C з координатами (0,17; 5,66).

4. Завдання ДП.

x2 = 2, x3 = 6. На графіку точка D з координатами (2; 6).

Трудомісткість і ефективність рішення моделі різними методами.

 Метод

 Властивість ЛП ЦЛП Нелінійне ДП

 Використання

 Симплекс - методу і ПК Невелике (1 прохід) Велике (багато проходів) Велике (багато проходів) НІ

 Розмір розрахунків без ПК Низький (тільки розрахунок планових завдань) Низький (тільки розрахунок планових завдань) Середній (розрахунок доходу, прибутку, витрат, планових завдань) Великий (всі розрахунки проводяться вручну)

 Розмір підготовчих і проміжних розрахунків Низький (тільки обмеження) Середній (обмеження ЛП + розгалуження) Високий (обмеження ЛП + складання таблиці + проміжний-ні підстановки коеффіціен-тів) Дуже великий

 Загальний час вирішення Низьке Середнє Середнє Висока

 Чувствитель-ність до обмежень за змістом корисного компонента в руді Є Є Є Немає

 Використання коефіцієнта збільшення витрат при навантаженні Ні Ні Так Так

 Розмір цільової функції

 Максимальний

 6048,2412

 Середній

 5993,3501

 Середній

 5827,1611

 Низький

 4249,38

 Загальна ефективність і наближеність умов до реальних

 Низька (не враховується

 коефіцієнт зміни витрат і целочіслен-

 ність рішення) Середня (не враховується коефіцієнт зміни витрат) Середня (не враховується целочіслен-ність рішення) Середня (низький прибуток)

Про проект.

Проект виконаний студентом другого курсу факультету РПМ Московського державного гірничого університету Солодовникова Дмитром.

Використана література:

· Резниченко С.С., Ашихміна А.А. Математичні методи та моделювання в гірській промисловості. - М .: Видавництво Московського гірничого університету, 1997, 404 c.

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка