Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Різновидом задач лінійного програмування є транспортні задачі. Нехай потрібно перевезти деяку кількість одиниць однорідного товару з різних складів в декілька магазинів. Приймемо слідуючі позначення: k – число складів, n – число магазинів, аі – кількість товару на і-ому складі, bj - кількість товару, необхідного j-ому магазину, xij - кількість одиниць товару, що перевозиться з і-го складу в j-ий магазин. Передбачається, що a1
+ … + ak = b1 + …bn і що відомі вартості cij перевезення одиниці товару з і-го складу до j-го магазину (вважається, що загальна вартість перевезення пропорційна загальному обсягу перевезення cijxij при перевезенні з і-го складу до j-го магазину). Потрібно знайти такі обсяги перевезень, щоб F(x)
= (c11x11 + … + c1nx1n) + (ci1xi1 + … + cinxin) +
+ (ck1xk1 + … + cknxkn) -> min при обмеженнях:

[pic] (II).
Для нас важливим є те, що всі невідомі змінні входять до цільової функції, а також в обмеження в першому ступені і являються неперервно знінюваними величинами. Рівності n=k не вимагається.

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

На практиці в сферах фінансів, маркетингу, інвестування та інших дуже часто виникає проблема раціонального розподілу якихось ресурсів
(капіталовкладень, товару тощо). Щоб прийняти вірне рішення щодо оптимального розподілу ресурсів застосовується математична модель динамічного програмування. Динамічне програмування використовується для дослідження багатоетапних процесів. Стан системи, якою керують, характеризується певним набором параметрів (фазовими координатами). Процес переміщення в фазовому просторі розподіляють на ряд послідовних етапів і здійснюють послідовну оптимізацію кожного з них, починаючи з останнього. На кожному етапі знаходять умовно оптимальне управління при всеможливих передбаченнях про результати попереднього кроку. Коли процес доходить до вихідного стану, знову проходять всі етапи, але вже з множини умовних оптимальних управлінь обирається одне найкраще [8, с.32]. В простому випадку задача динамічного програмування може вирішуватися наступним методом.

Нехай є n функцій з невід’ємними значеннями f1(x1), x1[pic] d1,..., fn(xn), xn[pic] dn, де d1,…,dn – області визначення змінних. Потрібно знайти максимум (або мінімум) F(x1,…,xn)=f1(x1) + … + fn(xn) при деяких обмеженнях на змінні x1,…,xn. В найпростішому випадку обмеження одне ( не враховуючи природньої вимоги невід’ємності змінних): x1+x2+…+xn=A. Схема дій буде наступною: знаходимо F12(A)=max[f1(x)+f2(A-x)], далі
F123(A)=max[F12(x)+f3(A-x)] і т.ін., а в кінці кінців – max
F(x1,…,xn)=F12…n(A)=max[F12…n-1(x)+fn(A-x)]. o Приклад.

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

(Див. таблицю 1).

Таблиця 1:

Вихідні дані прикладу.
|Вкладення | 1 | 2 | 3 |
|0 |0 |0 |0 |
|1 |0,28 |0,25 |0,15 |
|2 |0,45 |0,41 |0,25 |
|3 |0,65 |0,55 |0,40 |
|4 |0,78 |0,65 |0,50 |
|5 |0,90 |0,75 |0,62 |
|6 |1,02 |0,80 |0,73 |
|7 |1,13 |0,85 |0,82 |
|8 |1,23 |0,88 |0,90 |
|9 |1,32 |0,90 |0,96 |
| | | | |

Як розпорядитися наявним капіталом так, щоб прибуток був максимальним ?

Звичайно, можна переглянути всі можливі комбінації розподілу капіталу, скажімо при чотирьох одиницях капіталу:
(4,0,0), (0,4,0), (0,0,4); (3,1,0), (3,0,1); (2,2,0), (2,0,2), (2,1,1) і т.ін.
Але якщо задана велика кількість змінних?... Для вирішення цієї задачі можна використовувати динамічне програмування. Введемо наступні позначення:

F1(x), f2(x), f3(x) – функції прибутку в залежності від капіталовкладень, тобто стовпці 2-4 (див. таб.1), F12(A) – оптимальний розподіл, коли А одиниць капіталу вкладується в першу і лругу точки разом,
F123(A) – оптимальний розподіл капіталу величини А, що вкладається у всі точки разом.

Наприклад,для визначення F12(2) треба знайти f1(0)+f2(2)=0,41, f1(1)+f2(1)=0,53, f1(2)+f2(0)=0,45 і обрати з них максимальну, тобто
F12(2)=0,53. Взагалі F12(2)=max[f1(x)+f2(A-x)]. Обчислюємо F12(0), F12(1),
F12(2),…F12(9), котрі заносимо в таблицю 2 (див. таб.2).

Для А=4 можливі комбінації (4, 0), (3, 1), (2, 2), (1, 3), (0, 4), котрі дають відповідно загальний прибуток: 0,78; 0,90; 0,86; 0,83; 0,65.
Більш детально отримання цих величин показано нижче.

Таблиця 2:

Розподіл капіталу між двома торговими точками.
|Вкладення |f1(x) |f2(x) |F12(A)|Оптимальний |
|(А) | | | |розподіл |
|0 |0 |0 |0 |0,0 |
|1 |0,28 |0,25 |0,28 |1,0 |
|2 |0,45 |0,41 |0,53 |1,1 |
|3 |0,65 |0,55 |0,70 |2,1 |
|4 |0,78 |0,65 |0,90 |3,1 |
|5 |0,90 |0,75 |1,06 |3,2 |
|6 |1,02 |0,80 |1,20 |3,3 |
|7 |1,13 |0,85 |1,33 |4,3 |
|8 |1,23 |0,88 |1,45 |5,3 |
|9 |1,32 |0,90 |1,57 |6,3 |
| | | | | |

F12(A)=max{f1(x)+f2(A-x)}

[pic]

[pic]
Тепер, коли фактично є залежність F12 від величини капіталу, що вкладується у перші дві точки, можна шукати F123(A)=max[F12(x)+f3(A-x)].
Результати наведемо в таблиці 3. Більш детально отримання цих величин при вкладенні капіталу в три точки показано в таблиці 4 для дев’яти одиниць капіталу.
Таблиця 3:
Розподіл капіталу поміж трьома торговими точками.
|Вкладення (А)|F12(x) |f3(x) |F123(A) |Оптимальний |
| | | | |розподіл |
| | | | | |
|0 |0 |0 |0 |(0, 0, 0) |
|1 |0,28 |0,15 |0,28 |(1, 0, 0) |
|2 |0,53 |0,25 |0,53 |(1, 1, 0) |
|3 |0,70 |0,40 |0,70 |(2, 1, 0) |
|4 |0,90 |0,50 |0,90 |(3, 1, 0) |
|5 |1,06 |0,62 |1,06 |(3, 2, 0) |
|6 |1,20 |0,73 |1,21 |(3, 2, 1) |
|7 |1,33 |0,82 |1,35 |(3, 3, 1) |
|8 |1,45 |0,90 |1,48 |(4, 3, 1) |
|9 |1,57 |0,96 |1,60 |(5, 3, 1) або (3,|
| | | | |3, 3) |

Таблиця 4:
Розподіл дев’яти одиниць капіталу поміж трьома точками.
|Капітал |x1+x2 |x3 |F123 |
| | | | |
| 9 |9 |0 |1,57 |
| |8 |1 |1,45+0,15=1,6 |
| |7 |2 |(5, 3, 1) |
| |6 |3 |1,33+0,25=1,58 |
| |5 |4 |1,2+0,4=1,6 |
| |4 |5 |(3, 3, 3) |
| |3 |6 |1,06+0,5=1,56 |
| |2 |7 |0,9=0,62=1,52 |
| |1 |8 |0,70+0,73=1,43 |
| |0 |9 |0,53+0,82=1,35 |
| | | |0,28+0,90=1,18 |
| | | |0,96 |

Важливо те, що отримані результати були д тими ж, якби ми користувались не F12 і F123, а, скажімо, F31 i F312. Зверніть увагу на те, що оптимальне рішення для А=9 – не єдине!

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

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

Приведемо приклад наступної математичної моделі – моделі управління запасами. Модель управління запасами використовується для визначення часу розміщення замовлень на ресурси та їх кількості, а також маси готової продукції. Будь-яка організація повинна підтримувати деякий рівень запасів для запобігання затримок на виробництві і в збуті [5, с. 231]. Ціль даної моделі – зведення до мінімуму негативних наслідків накопичення запасів, що виражається в певних витратах. Всупереч відомій приказці (“Запас кишеню не тягне”), підприємцю потрібно піклуватися про те, щоб витрати на зберігання продукції були в розумних межах.

Існують різні види запасів. Буферний запас, що створюється між постачальником та виробником, потрібен для компенсації затримок в поставках, для послаблення залежності споживача від постачальника, для виробництва продукції партіями оптимального розміру. Запас готової продукції потрібен для виробництва продукції партіями оптимального розміру, для задоволення очікуваного попиту, для компенсації відхилення фактичного попиту, від того, що прогнозується (гарантійний запас). Можливі різні постановки задачі управління запасами. Наприклад: визначити обсяг замовлень, вважаючи моменти виробництва замовлень фіксованими, або визначити і обсяг замовлень і моменти замовлень. Під оптимальним як правило розуміється рішення, що мінімізує суму всіх затрат, пов’язаних із створенням запасів. Затрати бувають трьох типів: затрати на оформлення і отримання замовлення, вартість зберігання продукції і штрафи при виснаженні запасів за недопоставлену продукцію. Приходиться також враховувати характеристики попиту (відомий – невідомий, постійний – залежить від часу, виникає в певні моменти – існує весь час) і замовлень (виконуються одразу ж
– через деякий час, приймаються в будь-який час – в певні моменти, замовлене надходить рівномірно – нерівномірно і т.ін.)[8, с.44].

Рекомендуем скачать другие рефераты по теме: предмет курсовой работы, бесплатные рефераты и курсовые.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата