Динамическое і лінійне программирование

РефератДопомога в написанніДізнатися вартістьмоєї роботи

Завдамо середні очікувані доходи й ризики кожну операцію на площину (див. графік 2.). Тоді, ніж правіше точка на графіці, тим паче дохідна операція, ніж точка вище — тим паче вона ризикована. Для визначення операції оптимальної по Парето, необхідно на графіці знайти точку, що її домінує жодна інша точка. Оскільки точка домінує точку, якщо і, те з графіка 2. видно, що 3-ая операція домінує 2-ую… Читати ще >

Динамическое і лінійне программирование (реферат, курсова, диплом, контрольна)

Державний університет управления.

Інститут заочного обучения.

Спеціальність — менеджмент.

Кафедра прикладної математики.

КУРСОВОЙ ПРОЕКТ.

з дисципліни: «Прикладна математика».

Выполнил студент 1-го курсу Група № УП4−1-98/2 Студентський квиток №.

Москва, 1999 г.

1. Лінійна виробнича завдання 3.

2. Двоїста завдання 7.

3. Завдання про «Расшивке вузьких місць виробництва» 9.

4. Транспортна завдання 12.

5. Розподіл капітальних вкладень 17.

6. Динамічна завдання управління запасами 21.

7. Аналіз дохідності і ризику фінансових операцій 26.

8. Оптимальний портфель цінних паперів 28.

1. Лінійна виробнича задача.

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

Припустимо, підприємство чи цех може випускати [pic] видів продукції, використовуючи [pic] видів ресурсів. У цьому відомо кількість кожного виду ресурсу, витрата кожного виду ресурсу на випуск кожного виду продукції, прибуток, отримувана з одиниці випущеної продукції. Потрібна скласти такий план виробництва, у якому прибуток, отримувана підприємством, було б наибольшей.

Приймемо такі обозначения:

|[pic]|Номер ресурсу (i=1,2,…, m) | |[pic]|Номер продукції (j=1,2,…, n) | |[pic]|Расход i-го ресурсу на одиницю j-ой продукції | |[pic]|Имеющееся кількість i-го ресурсу | |[pic]|Прибыль на одиницю j-ой продукції | |[pic]|Планируемое кількість одиниць j-ой продукції | |[pic] |Зазначений план виробництва |.

Отже, математична модель завдання у тому, щоб знайти виробничу програму [pic] максимизирующую прибыль:

[pic].

У цьому, як і вона була виробничу програму [pic], її компоненти повинні задовольняти умові, що сумарна використання цього виду ресурсу, під час виробництва всіх видів продукції на повинен перевищувати те що кількість цього виду ресурсу, т. е.

[pic], де [pic].

Оскільки компоненти програми — кількість виробів, то не можуть виражені негативними числами, отже додається ще й одне условие:

[pic], де [pic].

Припустимо, що це підприємство може випускати чотири виду продукції ([pic]), використовуючи при цьому три виду ресурсів ([pic]). Відома технологічна матриця [pic] витрат будь-якого ресурсу на одиницю кожної продукції, вектор [pic] обсягів ресурсів немає і вектор [pic] удільної прибыли:

[pic] [pic] [pic].

Тоді математична модель завдання матиме вид: Знайти виробничу програму [pic] максимизирующую прибуток: |[pic] |(1.1) |.

при обмеженнях за ресурсами: |[pic] |(1.2) |.

де за змісту завдання: [pic], [pic], [pic], [pic] Отже, отримали завдання на перебування умовного экстремума. Для її рішення введемо додаткові неотрицательные неизвестные:

|[pic], |залишок ресурсу певного виду | |[pic], |(неиспользуемое кількість кожного | |[pic] |ресурсу) |.

Тоді замість системи нерівностей (1.2), одержимо систему лінійних алгебраїчних уравнений:

|[pic] |(1.3) |.

де серед усіх рішень, які відповідають умові неотрицательности:

[pic], [pic], [pic], [pic], [pic], [pic], [pic] треба знайти рішення, у якому функція (1.1) прийме найбільше значення. Це завдання будемо нічого вирішувати методом послідовного поліпшення плану — симплексным методом. Скористаємося тим, що праві частині від усіх рівнянь системи (1.3) неотрицательны, а саму систему має предпочитаемый вид — додаткові перемінні є засадничими. Прирівнявши нанівець вільні перемінні x1, x2, x3, x4, отримуємо базисне ненегативне решение:

[pic], [pic], [pic], [pic], [pic], [pic], [pic] перші чотири компоненти якого вони представляють виробничу програму [pic], через яку поки що немає. З висловлювання (1.1) видно, що нині найвигідніше починати виробляти продукцію третього виду, т.к. прибуток на одиницю випущеної продукції тут найбільша, у системі (1.3) приймаємо зміну x3 за розрізнювальну і перетворимо неї до іншого предпочитаемому виду. Навіщо складаємо відносини правих частин рівнянь до відповідним позитивним коефіцієнтам при обраної невідомою і знаходимо найбільше значення x3, яку вона може прийняти при нульових значеннях інших вільних невідомих, зберігши праві частини рівнянь неотрицательными, т. е.

[pic] Воно відповідає першому рівнянню у системі (1.3), і яке кількість виробів третього виду підприємство може виготовити з урахуванням обсягів сировини першого виду. Отже, в базис вводимо невідому x3, а виключаємо від туди невідому x5. Тоді приймаємо перше рівняння в системі (1.3) за що дозволяє, а що дозволяє елементом буде a13=6. Застосувавши формули винятку, переходимо до нового предпочитаемому виду системи з певним базисним допустимим рішенням. Повний процес розв’язування приведено у таблиці 1, де у останньої рядку третьої таблиці немає жодної негативного відносного оцінкової коэффициента.

[pic], де [pic], де [pic], тобто. виконується критерій оптимальності для максимизируемой функції (1.1).

|Таблица 1 | |З |Бази|H |30 |11 |45 |6 |0 |0 |0 |Пояснення | | |з | | | | | | | | | | | | | |[pic| |[pic|[pic|[pic|[pic|[pic| | | | | |] | |] |] |] |] |] | | |0 |[pic|15|3 |2 |6 |0 |1 |0 |0 |[pic] | | |] |0 | | | | | | | |x3 — що дозволяє| | | | | | | | | | | |змінна | | | | | | | | | | | |x3 (в базис. | | | | | | | | | | | |[pic] | | | | | | | | | | | |перший рядок — | | | | | | | | | | | |що дозволяє | | | | | | | | | | | |x5 (з базису. | | | | | | | | | | | |що дозволяє | | | | | | | | | | | |елемент = 6 | |0 |[pic|13|4 |2 |3 |5 |0 |1 |0 | | | |] |0 | | | | | | | | | |0 |[pic|12|4 |3 |2 |4 |0 |0 |1 | | | |] |4 | | | | | | | | | | |0 | |-30 |-11 |-45 |-6 |0 |0 |0 | | |45|[pic|25|[pic|[pic|1 |0 |[pic|0 |0 |[pic] | | |] | |] |] | | |] | | |x1 — що дозволяє| | | | | | | | | | | |змінна | | | | | | | | | | | |[pic] | | | | | | | | | | | |друга рядок — | | | | | | | | | | | |що дозволяє | | | | | | | | | | | |що дозволяє | | | | | | | | | | | |елемент = [pic] | |0 |[pic|55|[pic|1 |0 |5 |[pic|1 |0 | | | |] | |] | | | |] | | | | |0 |[pic|74|3 |[pic|0 |4 |[pic|0 |1 | | | |] | | |] | | |] | | | | | |1125| |[pic|4 |0 |-6 |[pic|0 |0 | | | | | |] | | | |] | | | | |45|[pic|14|0 |[pic|1 |-1 |[pic|[pic|0 |Усі [pic] | | |] | | |] | | |] |] | | | |30|[pic|22|1 |[pic|0 |2 |[pic|[pic|0 | | | |] | | |] | | |] |] | | | |0 |[pic|8 |0 |[pic|0 |-2 |[pic|[pic|1 | | | |] | | |] | | |] |] | | | | |1290| |0 |7 |0 |9 |6 |3 |0 | |.

У цьому кожен елемент симплексной таблиці існує певна економічний сенс. Наприклад, на другий симплексной таблице:

Т.к. у вищій рядку третьої таблиці 1 немає жодної негативного відносного оцінкової коефіцієнта, то виробничу програму, при якої отримувана підприємством прибуток має найбільше значення, знайдено, т.к., наприклад, коефіцієнт [pic] при перемінної [pic] показує, що й зробити одну одиницю продукції другого виду, то прибуток зменшиться на 7 грошових одиниць. Отже, отримали виробничу программу:

[pic], [pic], [pic], [pic] що є оптимальної і відданість забезпечує підприємству найбільшу можливу прибыль:

[pic] У цьому перший і другий ресурси буде використано повністю, тобто. перший і другий ресурси утворюють «вузькі місця производства»:

[pic], [pic] а третій ресурс матиме остаток:

[pic] До того ж у третій симплексной таблиці отримано звернений базис, відповідальний оптимальної виробничої программе:

[pic] можна буде перевірити виконання співвідношення [pic]: [pic] а т.к. з третьої симплексной таблиці: [pic], отже, співвідношення [pic] выполняется.

2. Двоїста задача.

Завдання, двоїста лінійної виробничої завданню, наприклад, може полягати у оцінці вигоди від продажу сировини, що у виробництві, набік. Наприклад, у минулому п. 1. розглянута лінійна виробнича завдання з випуску чотирьох видів продукції з допомогою трьох видів ресурсів по заданим технологіям. Припустимо, якийсь підприємець, займається виробництвом інших напрямів продукції з допомогою трьох так само видів ресурсів, пропонує «поступитися» їй усе наявні ресурси, і обіцяє платити y1 грошових одиниць кожну одиницю першого ресурсу, y2 грошових одиниць за кожну одиницю другого ресурсу і y3 грошових одиниць кожну одиницю третього ресурсу. Постає питання: за яких значеннях y1, y2, y3 можна прийняти пропозицію цього предпринимателя.

Т.к. попередній завданню технологічна матриця [pic] витрат будь-якого ресурсу на одиницю кожної продукції, вектор [pic] обсягів ресурсів немає і вектор [pic] удільної прибутку мали вид:

[pic] [pic] [pic] отже, для, наприклад, першого виду продукції, підприємство має затратити 3 одиниці ресурсу першого виду, 4 одиниці ресурсу другого виду та 4 одиниці ресурсу третього виду, внаслідок чого воно матиме прибуток 30 грошових одиниць. Отже, прийняти пропозицію підприємця можна, коли він заплатить незгірш від, тобто. у цінах y1, y2, y3 ця умова матиме вид:

[pic] Те саме і з продукцією другого, третього і четвертого виду, у своїй, на наявні ресурси, підприємець має сплатити незгірш від: [pic] грошових одиниць. Отже, підприємець шукатиме такі значення y1, y2, y3, у яких ця суму якомога менше. І йдеться про цінах, які залежать немає від цін якими ці ресурси були колись придбано, йдеться про цінах залежать від що застосовуються у виробництві технологій, обсягів ресурсів немає і прибутку, яку можна отримати за вироблену продукцію. Отже, завдання визначення розрахункових оцінок ресурсів призводить до завданню лінійного програмування: знайти вектор двоїстих оценок.

[pic] здатний мінімізувати загальну оцінку всіх ресурсов.

[pic] за умови, що у кожному виду продукції сумарна оцінка всіх ресурсів, витрачених виробництва одиниці виробленої продукції, незгірш від прибутку, одержуваної від одиниці цієї категорії продукції, т. е.:

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

[pic] [pic] У п. 1. знайшли, що [pic], [pic], а [pic] і [pic], тогда:

[pic] Але т.к. третій ресурс був надлишковим (див. п. 1.), то другий теоремі двоїстості, його двоїста оцінка дорівнює нулю, тобто. [pic]. Тоді переходимо до нову систему уравнений:

[pic] від куди отримуємо: [pic], [pic] Отже, отримали двоїсті оцінки ресурсов:

[pic], [pic], [pic] тоді загальна оцінка всіх ресурсів равна:

[pic] Це ж рішення значень двоїстих оцінок міститься у останньої рядку симплексной таблиці 1 і існує певна економічний сенс: |[pic] |Показує, що додавання однієї одиниці першого ресурсу | | |забезпечить приріст прибутку на 6 грошових одиниць. | |[pic] |Показує, що додавання однієї одиниці другого ресурсу | | |забезпечить приріст прибутку на 3 грошові одиниці. |.

3. Завдання про «Расшивке вузьких місць производства».

Завдання про «расшивке вузьких місць виробництва» у тому, що, наприклад, коли у процесі виробництва відбувається зміна обсягу якогоабо ресурсу, що у виробництві, то, відповідно змінюється план виробництва та прибуток підприємства, отримувана від готової продукції. Це може статися з різних причин, наприклад: зламався верстат, постачальник пропонує сировину у більшій кількості тощо. Тому, коли деяке ресурс повністю, то зменшення обсягу цього ресурсу, може спричинити всю структуру плану виробництва та прибуток підприємства. Отже, такий ресурс, утворюючий «вузькі місця виробництва», бажано мати з певним запасом, тобто. замовляти додатково, щоб зберегти структуру плану виробництва та отримати можливість збільшити прибуток підприємства. Наприклад візьмемо дані й одержують результати обчислень з п. 1. і п. 2., де визначено, що і другий ресурс використовуються повністю, і, відповідно, саме їхній потрібно замовляти додатково. Однак у таких обсягах, щоб зберегти структуру раніше знайденою програми виробництва, і з вимогою, що з постачальника можна було одержати додатково трохи більше однієї третини спочатку виділеного обсягу ресурсу будь-якого виду. Отже, завдання зводитися до пошуку обсягів придбання додаткових ресурсів, які відповідають зазначеним умовам, і вирахування додаткової можливої прибыли.

Тоді, нехай [pic] - вектор додаткових обсягів ресурсов:

[pic] у своїй, задля збереження структури виробничої програми, має виконуватися умова стійкості двоїстих оценок:

[pic].

Т.к. [pic], то завдання у цьому, щоб знайти вектор:

[pic] максимізує сумарний приріст прибутку: |[pic] |(3.1) |.

за умови збереження структури виробничої програми: |[pic] |(3.2) | припускаючи, що можна сподіватися отримати додатково трохи більше однієї третини обсягу ресурсу кожного виду, тобто.: |[pic] |(3.3) |.

причому додаткові обсяги ресурсів, за змістом завдання, неможливо знайти негативними, тобто.: |[pic], [pic] |(3.4) |.

Т.к. нерівності (3.2) і (3.3) їх необхідно виконувати одночасно, їх можна переписати у вигляді одного системи неравенств:

|(|[pic] |(3.5) | |(| | | |(| | | |(| | | |(| | |.

Отже, отримана завдання лінійного програмування: максимізувати функцію (3.1) за умов (3.4) і (3.5). Це завдання з цими двома перемінними можна вирішити графически:

Графік 1. На графіці видно, що систему лінійних нерівностей (3.4), (3.5), утворює область допустимих рішень, обмежену прямыми:

[pic], [pic], [pic], [pic].

при цьому лінії рівня функції (3.1) перпендикулярні вектору-градиенту [pic] й утворять сімейство паралельних прямих (градієнт вказує можливий напрямок зростання функції). Найбільшого значення функція (3.1) сягає у точці [pic]пересечения прямых:

[pic] і [pic] Координати цієї крапки й визначають шукані обсяги додаткових ресурсів. Отже, програма «розшивки вузьких місць виробництва має вид:

[pic], [pic], [pic] і приріст прибутку составит:

[pic].

Зведення результатів за пунктами 1−3 приведено в таблиці 2.

|Таблиця 2. | |[pic|30 |11 |45 |6 |B |[pic|[pic|[pic]| |] | | | | | |] |] | | |[pic|3 |2 |6 |0 |150 |0 |6 |50 | |] | | | | | | | | | | |4 |2 |3 |5 |130 |0 |3 |[pic]| | |4 |3 |2 |4 |124 |8 |0 |0 | |[pic|22 |0 |14 |0 |1290 | | |[pic]| |] | | | | | | | | | |[pic|0 |7 |0 |9 | | | | | |] | | | | | | | | |.

4. Транспортна задача.

Транспортна завдання — це завдання про мінімізації транспортних витрат, що стосуються забезпечення пунктів споживання певною кількістю однорідної продукції, виробленої (береженої) у кількох пунктах виробництва (зберігання). Загалом вигляді це може бути сформульована так: Однорідний продукт, зосереджений в [pic] пунктах виробництва (зберігання), необхідно розподілити між [pic] пунктами споживання. Вартість перевезення одиниці виробленої продукції відома всім маршрутів. Необхідно скласти такий план перевезень, у якому запити всіх пунктів споживання було б задоволені з допомогою наявних продуктів в пунктах виробництва та загальні транспортні витрати з доставки продуктів було б мінімальними. Приймемо такі обозначения:

|[pic]|Номер пункту виробництва (зберігання) (i=1,2,…, m) | |[pic]|Номер пункту споживання (j=1,2,…, n) | |[pic]|Количество продукту, що у i пункті | | |виробництва | |[pic]|Количество продукту, необхідне j-го пункту | | |споживання | |[pic]|Стоимость перевезення одиниці продукту з i-го пункту | | |відправлення в j-ый пункт призначення | |[pic]|Количество вантажу, планованого до перевезення від i-го | | |пункту відправлення в j-ый пункт призначення |.

Тоді, за наявності балансу виробництва та потребления:

[pic] математична модель транспортної завдання виглядатиме наступним чином: знайти план перевозок.

[pic], де [pic]; [pic] здатний мінімізувати загальну вартість всіх перевозок.

[pic] за умови, що із будь-якої пункту виробництва вивозитися весь продукт |[pic], де [pic] |(4.1) |.

будь-якому споживачеві доставляється необхідне кількості вантажу |[pic], де [pic] |(4.2) |.

причому, за змістом задачи.

[pic], …, [pic] Аби вирішити транспортної завдання найчастіше застосовується метод потенціалів, у якому вводять позначення вектора симплексных множників чи потенциалов:

[pic] Тогда:

[pic], де [pic]; [pic] Звідки следует:

[pic], де [pic]; [pic] У цьому одне із потенціалів можна вибирати довільно, т.к. у системі (4.1) і (4.2) одне рівняння лінійно залежить від інших, інші ж потенціали перебувають, що з базисних значень [pic].

Припустимо, що однорідний продукт, що у трьох пунктах виробництва (m=3), необхідно доставити вчетверо пункту споживання (n=4). У цьому матриця [pic] транспортних витрат за перевезення одиниці продукту із будь-якої пункту відправлення у будь-якій пункт призначення, вектор [pic] обсягів запасів продукту пунктах виробництва та вектор [pic] обсягів продукту, необхідних пунктах споживання, мають вигляд: |[pic] |[pic] | |[pic] | |.

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

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

[pic] одиниць, у своїй тарифи на перевезення продукту цей пункт споживання дорівнюватимуть нулю, т.к. фактичного переміщення продукту немає. Тоді, перше базисне дозволене рішення легко побудувати за правилом «північно-західного кута». А т.к. оцінки базисних клітин транспортної таблиці рівні нулю, то, прийнявши, що [pic], перша транспортна таблиця і потенціали мають вид:

|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] | |p|p| | | | | | |[pic] |[pic] | |i|i| | | | | | |[pic] |[pic] | |c|c| | | | | | |[pic] |[pic] | |]|]| | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | |50 |30 |11 |9 |* | |[pic]| | | |70 | | |36 |34 | |[pic]| | | |30 | | | |2 |28 |[pic]| | | | |[pic|[pic|[pic|[pic|[pic| | | | | |] |] |] |] |] | | | |.

Т.к. найбільша позитивна оцінка всіх вільних клітин транспортної таблиці, відповідає клітині 14, то будуємо цикл перерахунку: 14−13−23−24 і виробляємо перерозподіл поставок вздовж циклу пресчета: |[pic] |[pic] | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | | |9 |* |(|[pic]|[pic]|(|0 |9 | | |36 |34 | |[pic]|[pic]| |45 |25 | | | |[pic] | |.

Те отримуємо друге базисне дозволене рішення і знаходимо нові потенціали, вважаючи [pic]:

|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] | |p|p| | | | | | |[pic] |[pic] | |i|i| | | | | | |[pic] |[pic] | |c|c| | | | | | |[pic] |[pic] | |]|]| | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | |50 |30 |11 | |9 | |[pic]| | | |70 | |* |45 |25 | |[pic]| | | |30 | | | |2 |28 |[pic]| | | | |[pic|[pic|[pic|[pic|[pic| | | | | |] |] |] |] |] | | | |.

Т.к. тепер найбільша позитивна оцінка всіх вільних клітин транспортної таблиці, відповідає клітині 22, то будуємо цикл перерахунку: 22- 12−14−24 і виробляємо перерозподіл поставок вздовж циклу пресчета:

|[pic] |[pic] | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | | |11 |9 |(|[pic]|[pic]|(|0 |20 | | |* |25 | |[pic]|[pic]| |11 |14 | | | |[pic] | |.

Звідси отримуємо третє базисне дозволене рішення і знаходимо нові потенціали, приймаючи [pic]:

|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] | |p|p| | | | | | |[pic] |[pic] | |i|i| | | | | | |[pic] |[pic] | |c|c| | | | | | |[pic] |[pic] | |]|]| | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | |50 |30 | | |20 | |[pic]| | | |70 |* |11 |45 |14 | |[pic]| | | |30 | | | |2 |28 |[pic]| | | | |[pic|[pic|[pic|[pic|[pic| | | | | |] |] |] |] |] | | | |.

Т.к. найбільша позитивна оцінка всіх вільних клітин транспортної таблиці, тепер відповідає клітині 21, то будуємо цикл перерахунку: 21−11−14- 24 і виробляємо перерозподіл поставок вздовж циклу пресчета: |[pic] |[pic] | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | | |30 |20 |(|[pic]|[pic]|(|16 |34 | | |* |14 | |[pic]|[pic]| |14 |0 | | | |[pic] | |.

Отримуємо четверте базисне дозволене рішення і знаходимо нові потенціали, приймаючи [pic]:

|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] | |p|p| | | | | | |[pic] |[pic] | |i|i| | | | | | |[pic] |[pic] | |c|c| | | | | | |[pic] |[pic] | |]|]| | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | |50 |16 | | |34 | |[pic]| | | |70 |14 |11 |45 | | |[pic]| | | |30 | | |* |2 |28 |[pic]| | | | |[pic|[pic|[pic|[pic|[pic| | | | | |] |] |] |] |] | | | |.

Т.к. найбільша позитивна оцінка всіх вільних клітин транспортної таблиці, відповідає клітині 33, то будуємо цикл перерахунку: 33−23−21−11−14- 34 і виробляємо перерозподіл поставок вздовж циклу пресчета:

|[pic] |[pic] | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | | |16| |34|(|[pi| |[pi|(|14| |36| | | | | | |з] | |з] | | | | | | |14|45| | |[pi|[pi| | |16|43| | | | | | | |з] |з] | | | | | | | | |* |2 | | |[pi|[pi| | |2 |0 | | | | | | | |з] |з] | | | | | | | |[pic] | |.

Отримуємо п’яте базисне дозволене рішення і знаходимо нові потенціали, знову приймаючи [pic]:

|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] | |p|p| | | | | | |[pic] |[pic] | |i|i| | | | | | |[pic] |[pic] | |c|c| | | | | | |[pic] |[pic] | |]|]| | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | |50 |14 | | |36 | |[pic]| | | |70 |16 |11 |43 | |* |[pic]| | | |30 | | |2 | |28 |[pic]| | | | |[pic|[pic|[pic|[pic|[pic| | | | | |] |] |] |] |] | | | |.

Тепер найбільша позитивна оцінка всіх вільних клітин транспортної таблиці, відповідає клітині 25, звідси будуємо цикл перерахунку: 25−23−33- і виробляємо перерозподіл поставок вздовж цього циклу пресчета: |[pic] |[pic] | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | | |43 |* |(|[pic]|[pic]|(|15 |28 | | |2 |28 | |[pic]|[pic]| |30 |0 | | | |[pic] | |.

Отримуємо п’яте базисне дозволене рішення і знову знаходимо нові потенціали, приймаючи [pic]:

|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] | |p|p| | | | | | |[pic] |[pic] | |i|i| | | | | | |[pic] |[pic] | |c|c| | | | | | |[pic] |[pic] | |]|]| | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | | | | | | | | | |[pic] |[pic] | |50 |14 | | |36 | |[pic]| | | |70 |16 |11 |15 | |28 |[pic]| | | |30 | | |30 | | |[pic]| | | | |[pic|[pic|[pic|[pic|[pic| | | | | |] |] |] |] |] | | | |.

Знаходимо оцінки всіх вільних клітин таблицы:

|[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | |[pic] | | | |Усі [pic], де [pic]; [pic] |.

Т.к. отримали таблицю на яку немає жодної позитивної оцінки, отже, знайдено оптимальне базисне дозволене решение:

[pic].

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

5. Розподіл капітальних вложений.

Завдання розподілу капітальних вкладень — це нелінійна завдання розподілу ресурсів між підприємствами одного виробничого об'єднання чи галузі. Припустимо, що [pic] пунктів, де потрібно побудувати чи реконструювати підприємства галузі, навіщо виділено певна сума. У цьому відомий приріст потужності чи прибутку кожному за підприємства, залежно від суми капітальних капіталовкладень у це підприємство. Потрібна знайти такий розподіл капітальних вкладень між підприємствами, яке максимизирует сумарний приріст потужності чи прибутку усієї галузі. Приймемо такі обозначения:

|[pic] |Номер підприємства (j=1,2,…, n) | |[pic] |Загальна сума капітальних вкладень | |[pic] |Сума капітальних капіталовкладень у j-ое підприємство | |[pic] |Приріст потужності чи прибутку j-го підприємства, якщо | | |воно отримає xj грошових одиниць капітальних вкладень |.

Тоді, завдання у цьому, щоб знайти такі значення [pic], [pic], …, [pic], у яких значення сумарного приросту прибутку чи потужності всієї отрасли:

[pic] було найбільшим, при обмеження загального обсягу: [pic], причому будемо вважати, що це перемінні [pic] приймають аж цілі неотрицательные значення, т. е.:

Тоді, коли з [pic] грошових одиниць k-ое підприємство отримає [pic] грошових одиниць, то залишок [pic] коштів необхідно розподілити між підприємствами від першого до [pic] те щоб було отримано максимальний приріст прибутку чи потужності [pic]. Отже, приріст прибутку чи потужності k підприємств дорівнюватиме [pic] і треба вибрати таке значення [pic] між 0 і [pic], щоб зростання прибутку чи потужності k підприємств було б максимальним, т. е.:

[pic], де [pic]. Якщо ж k=1, то:

[pic] Припустимо, що виробниче об'єднання складається з чотирьох підприємств (n=4). Загальна сума капітальних вкладень дорівнює 700 грошових одиниць (b=700), у своїй суми виділені підприємствам кратні 100 грошовим одиницям. Значення функцій [pic] наведені у таблиці 3:

|Таблица 3. | |[pic] |0 |100 |200 |300 |400 |500 |600 |700 | |[pic] |0 |42 |58 |71 |80 |89 |95 |100 | |[pic] |0 |30 |49 |63 |68 |69 |65 |60 | |[pic] |0 |22 |37 |49 |59 |68 |76 |82 | |[pic] |0 |50 |68 |82 |92 |100 |107 |112 |.

Для заповнення таблиці 5 необхідна за таблиці 4 скласти значення функції [pic] зі значеннями [pic] і кожної північно-східній діагоналі вибрати найбільше (зазначено зірочкою), вказавши відповідні значення [pic]:

|Таблица 4. | | |[pic] |0 |100 |200 |300 |400 |500 |600 |700 | |[pic|[pic] |0 |42 |58 |71 |80 |89 |95 |100 | |] | | | | | | | | | | | |[pic] | | | | | | | | | |0 |0 |0 |42* |58 |71 |80 |89 |95 |100 | |100 |30 |30 |72* |88 |101 |110 |119 |125 | | |200 |49 |49 |91* |107* |120 |129 |138 | | | |300 |63 |63 |105 |121* |134* |143* | | | | |400 |68 |68 |110 |126 |139 | | | | | |500 |69 |69 |111 |127 | | | | | | |600 |65 |65 |107 | | | | | | | |700 |60 |60 | | | | | | | |.

|Таблиця 5. | |[pic] |0 |100 |200 |300 |400 |500 |600 |700 | |[pic] |0 |42 |72 |91 |107 |121 |134 |143 | |[pic] |0 |0 |100 |200 |200 |300 |300 |300 |.

Для заповнення таблиці 7 необхідна за таблиці 6 скласти значення функції [pic] зі значеннями [pic] і кожної північно-східній діагоналі вибрати найбільше (зазначено зірочкою), вказавши відповідні значення [pic]:

| | |Таблиця 6. | | |[pic] |0 |100 |200 |300 |400 |500 |600 |700 | |[pic|[pic] |0 |42 |72 |91 |107 |121 |134 |143 | |] | | | | | | | | | | | |[pic] | | | | | | | | | |0 |0 |0 |42* |72* |91 |107 |121 |134 |143 | |100 |22 |22 |64 |94* |113* |129* |143 |156 | | |200 |37 |37 |79 |109 |128 |144* |158* | | | |300 |49 |49 |91 |121 |140 |156 | | | | |400 |59 |59 |101 |131 |150 | | | | | |500 |68 |68 |110 |140 | | | | | | |600 |76 |76 |118 | | | | | | | |700 |82 |82 | | | | | | | |.

|Таблица 7. | |[pic] |0 |100 |200 |300 |400 |500 |600 |700 | |[pic] |0 |42 |72 |94 |113 |129 |144 |158 | |[pic] |0 |0 |0 |100 |100 |100 |200 |200 |.

Тепер, в таблиці 8, необхідно скласти значення функції [pic] зі значеннями [pic], але для значення [pic], тобто. заповнити тільки один диагональ:

|Таблица 8. | | |[pic] |0 |100 |200 |300 |400 |500 |600 |700 | |[pic|[pic] |0 |42 |72 |94 |113 |129 |144 |158 | |] | | | | | | | | | | | |[pic] | | | | | | | | | |0 |0 | | | | | | | |158 | |100 |50 | | | | | | |194 | | |200 |68 | | | | | |197* | | | |300 |82 | | | | |195 | | | | |400 |92 | | | |186 | | | | | |500 |100 | | |172 | | | | | | |600 |107 | |149 | | | | | | | |700 |112 |112 | | | | | | | |.

Найбільше цієї діагоналі показує максимально можливий сумарний приріст прибутку всіх чотирьох підприємств даного виробничого об'єднання, за загального сумі капітальних капіталовкладень у 700 грошових одиниць, тобто.: [pic] грошових одиниць причому четвертому підприємству має бути виділено: [pic] грошових одиниць Тоді третьому підприємству має бути виділено (див. табл. 7.): [pic] грошових одиниць другому підприємству має бути виділено (див. табл. 5.): [pic] грошових одиниць частку першого підприємства залишається: [pic] грошових одиниць Отже, найкращим є що розподіл капітальних вкладень на підприємствах: [pic][pic][pic][pic] що забезпечує виробничому об'єднанню найбільший можливий приріст прибыли:

[pic] грошових единиц.

6. Динамічна завдання управління запасами.

Завдання управління запасами — це завдання про підтримку балансу виробництва та збуту підприємства, минимизирующего витрати підприємства виробництво та зберігання продукції. Припустимо, що це підприємство, яке виробляє партіями деяку продукцію, одержало замовлення n місяців. Розміри замовлень значно змінюються від місяці місяцю, тому іноді краще виконувати замовлення відразу кількох місяців, та був зберігати готової продукції, поки не знадобиться, ніж виконувати замовлення саме той місяць, коли це замовлення має бути відправлений. Тому необхідно скласти план виробництва для цієї n місяців від урахуванням витрат за виробництво і збереження виробів. Приймемо такі позначення: |[pic] |Номер місяці (j=1,2,…, n) | |[pic] |Кількість виробів, які вироблялися j-ом місяці | |[pic] |Величина запасу до початку j-го місяці | |[pic] |Кількість виробів, що їх отгружены в j-ом | | |місяці | |[pic] |Витрати для зберігання і виробництво виробів на j-ом | | |місяці |.

Тоді, завдання у цьому, щоб знайти план виробництва [pic] компоненти якого задовольняють умовам матеріального баланса:

[pic], де [pic] і мінімізують сумарні витрати за весь запланований период:

[pic] причому за змістом завдання [pic], [pic], при [pic] Т.к. обсяг вироблену продукцію [pic] на етапі j може бути настільки великий, що запас [pic] може задовольнити попит усіх наступних етапів і у своїй втрачає сенс мати величину запасу [pic] більше сумарного попиту усіх наступних етапах, то змінна [pic] має відповідати ограничениям:

[pic].

Полученную завдання можна вирішити методом динамічного програмування, для чого слід визначити параметр стану [pic] і функцію стану [pic]: |[pic]|Наличный запас продукції кінці k-го місяці ([pic]) | |[pic]|Минимальные витрати за перші [pic] місяців: [pic] |.

Тоді, мінімальних витрат за місяць ([pic]):

[pic] Отже, мінімальних витрат при [pic]:

[pic], де [pic].

Якщо за цьому функція витрат за збереження і виробництво виробів на j-ом місяці має вид:

то мінімальних витрат за місяць ([pic]):

[pic] якщо запровадити обозначение:

[pic] то отже, мінімальних витрат при [pic]:

[pic], де [pic] Припустимо, що це підприємство уклало договори про поставки своєї продукції три місяці. Вихідні дані наведені у таблиці 9. У цьому вихідний запас товару складі становить дві одиниці, тобто [pic].

|Таблица 9. | |Період k |1 |2 |3 | |Попит ([pic]) |3 |2 |3 | |Витрати оформлення замовлення |4 |2 |3 | |([pic]) | | | | |Витрати за зберігання одиниці запасу |1 |1 |1 | |([pic]) | | | |.

Передбачається, що видатки придбання продукції становлять 5 крб. кожну одиницю для перших трьох одиниць і аналогічних сім крб. кожну додаткову одиницю, т. е.

[pic] Поклавши [pic], тогда:

[pic] Тоді, т.к. параметр стану [pic] може приймати значення на отрезке:

[pic] тобто. [pic], у своїй кожному значенням параметра стану відповідає певна область зміни перемінної [pic]:

[pic] Проте за першому етапі обсяги виробництва може бути менше однієї одиниці, т.к. попит [pic], а вихідний запас [pic], у своїй з балансового рівняння слід, що міра виробництва пов’язані з параметром стану [pic] соотношением:

[pic] тобто. кожному значенням [pic] відповідає єдине значення [pic], поэтому:

[pic], тогда:

|[pic] |[pic] |[pic] | |[pic] |[pic] |[pic] | |[pic] |[pic] |[pic] | |[pic] |[pic] |[pic] | |[pic] |[pic] |[pic] | |[pic] |[pic] |[pic] |.

Значення функції стану [pic] наведені у таблиці 10.: |Таблиця 10. | |[pic] |0 |1 |2 |3 |4 |5 | |[pic] |9 |15 |21 |29 |37 |45 | |[pic] |1 |2 |3 |4 |5 |6 |.

Поклавши [pic], тогда:

[pic], где:

[pic] Тут мінімум з перемінної [pic], яка може змінюватися в пределах:

[pic] де верхня межа залежить від параметра стану [pic], котра приймає значення на отрезке:

[pic] тобто. [pic], у своїй з балансового рівняння слід, що залишок товару початку другого місяці [pic] пов’язані з обсягом виробництва [pic] і з параметром стану [pic] соотношением:

[pic].

Тогда:

|[pic] |[pic] |[pic] |[pic]* | |([pic]) |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic]* |.

Найменші з отриманих значень [pic], є [pic], т. е.:

[pic] причому мінімум характеризується [pic] і [pic], т. е.:

[pic] і [pic] цих значень указуємо в результуючої таблиці 11. Аналогично:

|[pic] |[pic] |[pic] |[pic] | |([pic]) |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic]* | |[pic] |[pic] |[pic] |[pic] | |([pic]) |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic]* | | |[pic] |[pic] |[pic] | |[pic] |[pic] |[pic] |[pic] | |([pic]) |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic]* | | |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic] |.

Отже: |Таблиця 11. | |[pic] |0 |1 |2 |3 | |[pic] |21 |27 |34 |41 | |[pic] |0 |2 |3 |3 |3 |.

Тепер між іншим, що [pic], тогда:

[pic], где:

[pic].

Якщо залишати продукцію до кінця третього періоду непотрібно, тоді параметр стану приймає єдине значення [pic], отже, змінна [pic] може змінюватися в пределах:

[pic].

а з балансового рівняння слід, що залишок товару початку третього місяці [pic] пов’язані з обсягом виробництва соотношением:

[pic].

Тогда:

|[pic] |[pic] |[pic] |[pic] | |([pic]) |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic] | | |[pic] |[pic] |[pic]* |.

Отже, получаем:

[pic] причому мінімум характеризується [pic], т. е.:

[pic].

Отже, отримали мінімальні загальні видатки виробництво і зберігання продукції і на останню компоненту оптимального решения:

[pic].

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

Тоді т.к. [pic], то [pic], звідки [pic], отже, з таблиці 11.:

[pic] чи [pic].

Аналогічно т.к. [pic], то [pic] чи [pic], звідки [pic] чи [pic], отже, з таблиці 10.:

[pic] чи [pic].

Отже, отримано оптимальний план виробництва, який має дві варианта:

|[pic] |[pic] | |[pic] |[pic] | |[pic] |[pic] |.

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

7. Аналіз дохідності і ризику фінансових операций.

Фінансовій називається операція, початкова й кінцеве стан якої мають грошову оцінку і чітку мету проведення якої в максимізації доходу на вигляді різниці між кінцевої і початковій оцінками. У цьому майже всі фінансові операції відбуваються у умовах невизначеності та, отже, їх результат передбачити неможливо заздалегідь. Тому, за проведенні фінансової операції можливо отримання як прибутку, і збитку. Тому завдання аналізу дохідності і ризику фінансової операцій полягає щодо оцінки фінансової операції з погляду її дохідності і ризику. Найбільш поширеним способом оцінки фінансової операцій є уявлення доходу операції як випадкової розміру й оцінка ризику операції як середнього квадратического відхилення цього випадкового доходу. Наприклад, якщо прибуток від проведення деякою фінансової операції є випадкова величина [pic], то середній очікуваний прибуток [pic]- це математичне очікування випадкової величини [pic]:

[pic], де [pic] є можливість отримати дохід [pic] Т.к. среднеквадратическое отклонение:

[pic], де [pic] це міра незібраності можливих значень доходу навколо середнього очікуваного доходу, його вважатимуться кількісної мірою ризику операції означити як [pic]:

[pic].

Припустимо, що у чотирьом фінансовим операціям [pic], [pic], [pic], [pic] ряди розподілу доходів населення і ймовірностей отримання цих доходів мають вид:

|[pic]|2 |6 |8 |4 | |[pic]|2 |3 |4 |10 | | |[pic]|[pic]|[pic]|[pic]| | |[pic]|[pic]|[pic]|[pic]| | | | | | | | | | | | | |[pic]|0 |1 |2 |8 | |[pic]|0 |4 |6 |10 | | |[pic]|[pic]|[pic]|[pic]| | |[pic]|[pic]|[pic]|[pic]|.

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

|[pic] |[pic] | |[pic] | | |[pic] |[pic] | |[pic] | | |[pic] |[pic] | |[pic] | | |[pic] |[pic] | |[pic] | |.

Завдамо середні очікувані доходи [pic] й ризики [pic] кожну операцію на площину (див. графік 2.). Тоді, ніж правіше точка на графіці, тим паче дохідна операція, ніж точка вище — тим паче вона ризикована. Для визначення операції оптимальної по Парето, необхідно на графіці знайти точку, що її домінує жодна інша точка. Оскільки точка [pic] домінує точку [pic], якщо [pic] і [pic], те з графіка 2. видно, що 3-ая операція домінує 2-ую операцію, а 1-ая операція домінує 3-ую і 2-ую операції. Але 1-ая і 4-ая операції непорівнянні, т.к. дохідність 4-ой операції більше, а й ризик її теж більше, ніж дохідність і соціальний ризик 1-ой операції, отже, 1-ша операція є оптимальної по Парето. Для перебування кращої операції можна застосувати взвешивающую формулу, яка для пар [pic] дає одне число, яким можна визначити кращу операцію. Припустимо, що взвешивающей формулою буде [pic], тогда:

|[pic] |[pic] | |[pic] |[pic] |.

Звідси видно, що 1-ая фінансова операція — найкраща, а 2-ая — худшая.

8. Оптимальний портфель цінних бумаг.

Завдання формування оптимального портфеля цінних паперів — це завдання про розподілі капіталу, який учасник ринку хоче витратити для придбання набору цінних паперів, з різного виду цінних паперів, які відповідають можливість отримання деякого доходу. З характеристик цінних паперів найбільш значимі дві: ефективність яких і ризикованість. Т.к. ефективність [pic] - це певний узагальнений показник доходу чи прибутку, що його вважають випадкової величиною, та її математичне очікування позначають його як [pic]. Ризикованість цінних паперів ототожнюють із середнім квадратическим відхиленням, у своїй дисперсию зазвичай називають варіацією і позначається як [pic], т. е.:

[pic], де [pic].

Приймемо такі обозначения:

|[pic|Номер виду цінних паперів | |] | | |[pic|Доля капіталу, витрачена на закупівлю цінних паперів | |] |i-го виду (сума всіх часткою дорівнює одиниці) | |[pic|Эффективность цінних паперів i-го виду, що стоять одну | |] |грошову одиницю | |[pic|Математическое очікування ефективності [pic] | |] | | |[pic|Ковариация цінних паперів i-го і j-го видів | |] | | |[pic|Вариация (дисперсія) ефективності [pic] | |] | | |[pic|Рискованность цінних паперів i-го виду | |] | | |[pic|Эффективность портфеля (набору) цінних паперів | |] | |.

Тоді, математичне очікування ефективності портфеля цінних бумаг:

[pic] варіація портфеля цінних бумаг:

[pic] ризик портфеля цінних бумаг:

[pic] Отже, математична формалізація завдання формування оптимального портфеля цінних паперів: Знайти такий розподіл часткою капіталу, яке мінімізує варіацію ефективності портфеля, при заданої очікуваної ефективності портфеля [pic]. Тоді, якщо оптимальне рішення позначити як *, то:

Если ринку є безрисковые цінних паперів, те решіння завдання про формуванні портфеля цінних паперів набирає нового якість. Нехай: |[pi|Эффективность безризикових цінних паперів | |з] | | |[pi|Доля капіталу, вкладеного в безрисковые цінних паперів| |з] | | |[pi|Средняя очікувана ефективність ризиковій частини | |з] |портфеля | |[pi|Вариация ризиковій частини портфеля | |з] | | |[pi|Среднее квадратическое відхилення ефективності | |з] |ризиковій частини портфеля |.

Тоді, у рисковую частина портфеля вкладена [pic] частина всього капіталу, а т.к. вважається, що безрисковые цінних паперів некоррелированы з іншими, то очікувана ефективність всього портфеля цінних бумаг:

[pic] варіація портфеля цінних бумаг:

[pic] ризик портфеля цінних бумаг:

[pic] Припустимо, що завдання відшукати розподілу капіталу, при формуванні оптимального портфеля цінних паперів заданої ефективності, що складається з трьох видів цінних паперів: безризикових ефективності 3 і некоррелированных ризикових, з очікуваної ефективністю 5 і 9-те, ризики яких рівні 4 і шість, т. е.:

[pic], [pic], [pic], [pic], [pic] Тоді, варіації некоррелированных ризикових цінних паперів першого і другого виду: |[pic] |[pic] |.

Отже, матриця [pic] ковариаций ризикових видів цінних паперів і вектор-столбец [pic]ожидаемой ефективності ризикових видів цінних паперів мають вигляд: |[pic] |[pic] |.

Нехай [pic] - двомірний вектор-столбец, компоненти якого рівні 1, т. е.:

[pic] Тоді значення вектора-столбца [pic] оптимальних значень часткою, вкладених у рисковую частина портфеля цінних бумаг:

[pic] Где:

[pic].

[pic] Тобто.: [pic].

Отже, частки ризикових цінних паперів в оптимальному портфеле:

[pic], [pic] Отже, частка безризикових цінних паперів в оптимальному портфеле:

[pic] Т.к. необхідність виконання операції «short sale» виникає, коли [pic], то тому випадку, необхідність виконання операції «short sale» виникає, коли [pic]:

[pic], тобто. коли [pic].

———————————;

[pic].

Графік 2.

Показати весь текст

Заповнити форму поточною роботою