Модель розподілу ресурсів

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

скачати

Зміст

Введення

1. Основні поняття

1.1. Модель динамічного програмування

1.2. Принцип оптимальності. Рівняння Беллмана

2. Оптимальний розподіл ресурсів

2.1 Постановка завдання

2.2 Двовимірна модель розподілу ресурсів

2.3 Дискретна динамічна модель оптимального розподілу ресурсів

2.4 Облік післядії в задачах оптимального розподілу ресурсів

Висновок

Список використаних джерел

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

Введення

Протягом всієї своєї історії люди при необхідності приймати рішення вдавалися до складних ритуалів. Вони влаштовували урочисті церемонії, приносили в жертву тварин, ворожили за зірками і стежили за польотом птахів. Вони покладалися на народні прикмети і намагалися дотримуватися примітивним правилами, що полегшує їм важке завдання прийняття рішень. В даний час для прийняття рішення використовують новий і, мабуть, більш науковий «ритуал», заснований на застосуванні електронно-обчислювальної машини. Без сучасних технічних засобів людський розум, ймовірно, не може врахувати численні і різноманітні фактори, з якими стикаються при управлінні підприємством, конструюванні ракети чи регулюванні руху транспорту. Існуючі в даний час численні математичні методи оптимізації вже досить розвинені, що дозволяє ефективно використовувати можливості цифрових і гібридних обчислювальних машин. Одним з цих методів є математичне програмування, що включає в себе як окремий випадок динамічне програмування.

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

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

Як розділ математичного програмування, динамічне програмування (ДП) почало розвиватися в 50-х роках XX ст. завдяки роботам Р. Беллмана і його співробітників. Вперше цим методом вирішувалися задачі оптимального управління запасами, потім клас завдань значно розширився. Як практичний метод оптимізації, метод динамічного програмування став можливий лише при використанні сучасної обчислювальної техніки.

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

1. Основні поняття

1.1 Модель динамічного програмування

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

Розглядається керована система, яка під впливом управління переходить з початкового стану в кінцевий стан . Припустимо, що процес управління системою можна розбити на п кроків. Нехай , , ..., - Стану системи після першого, другого, ..., п-го кроку. Схематично це показано на рис. 1.

Малюнок 3

Стан системи після k-го кроку (k = 1,2 ..., n) характеризується параметрами , , ..., які називаються фазовими координатами. Стан можна зобразити точкою s-мірного простору званого фазовим простором. Послідовне перетворення системи (по кроках) досягається за допомогою деяких заходів , , ..., , Які складають управління системою , Де - Управління на k-му кроці, що переводить систему зі стану в стан (Рис. 1). Управління на k-му кроці полягає у виборі значень певних керуючих змінних * .

Припускаємо надалі, що стан системи в кінці k-го кроку залежить тільки від попереднього стану системи та управління на даному кроці (рис. 1). Така властивість отримало назву відсутності післядії. Позначимо цю залежність у вигляді

, (1.1)

Рівності (1.1) отримали назву рівнянь станів. Опції вважаємо заданими.

Варіюючи управління U, отримаємо різну «ефективність» процесу * *, яку будемо оцінювати кількісно цільової функцією Z, яка залежить від початкового стану системи і від вибраного управління U:

. (1.2)

Показник ефективності k-го кроку процесу управління, який залежить від стану на початку цього кроку та управління , Обраного на цьому кроці, позначимо через розглянутій задачі покрокової оптимізації цільова функція (1.2) повинна бути адитивною, тобто

. (1.3)

Якщо властивість адитивності цільової функції Z не виконується, то цього іноді можна домогтися деякими перетвореннями функції. Наприклад, якщо Z-мультиплікативна функція, задана у вигляді , То можна розглянути функцію , Яка є адитивною.

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

Задачу покрокової оптимізації можна сформулювати так: визначити сукупність допустимих управлінні , , ..., , Переводять систему з початкового стану в кінцевий стан і максимізує чи мінімізують показник ефективності (1.3).

Для однаковості формулювань (але не обчислювальних процедур!) Надалі ми будемо говорити тільки про завдання максимізації, маючи на увазі, що якщо необхідно мінімізувати Z, то, замінивши Z на Z '= - Z перейдемо до максимізації Z'.

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

Якщо змінні управління приймають дискретні значення, то модель ДП називається дискретною. Якщо ж зазначені змінні змінюються безперервно, то модель ДП називається неперервною. Залежно від числа параметрів станів (s) і числа керуючих змінних на кожному кроці (r) розрізняють одновимірні і багатовимірні моделі ДП. Число кроків в задачі може бути або кінцевим, або нескінченним .

Динамічне програмування застосовується при оптимізації як детермінованих, так і стохастичних процесів.

У деяких завданнях, розв'язуваних методом ДП, процес управління природно розбивається на кроки. Наприклад, при розподілі на кілька років ресурсів діяльності підприємства кроком природно вважати часовий період; при розподілі коштів між n підприємствами номером кроку природно вважати номер чергового підприємства. В інших завданнях розбиття на кроки вводиться штучно. Наприклад, безперервний керований процес можна розглядати як дискретний, умовно розбивши його на деякі часові відрізки - кроки. Виходячи з умов кожної конкретної задачі, довжину кроку вибирають таким чином, щоб на кожному кроці отримати просту задачу оптимізації та забезпечити необхідну точність обчислень.

1.2 Принцип оптимальності. Рівняння Беллмана

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

Ілюстрацією до сказаного вище може служити задача про вибір найкоротшого шляху для переходу з точки A в точку B, якщо маршрут повинен пройти через деякі пункти. На рис. 2 ці пункти позначені кружками, а що з'єднують їх дороги - відрізками, поруч з якими проставлені відповідні відстані.

Малюнок 3

З точки зору інтересів оптимізації тільки кожного найближчого кроку - вибору найкоротшого шляху з даної точки в сусідню - слід рухатися по маршруту, що проходить через точки . Довжина цього маршруту дорівнює 34. Такий шлях з A в B не є найкоротшим. Наприклад, маршрут, що проходить через точки , Має меншу довжину, яка дорівнює 25. Вирішивши це завдання, можна переконатися, що другий шлях також не є оптимальним.

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

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

Використання цього принципу гарантує, що управління, вибраного на будь-якому кроці, є не локально кращим, а кращим з точки зору процесу в цілому.

Так, якщо система на початку k-го кроку знаходиться в стані , І ми вибираємо довільне керування , То система прийде в новий стан , І подальші управління повинні вибиратися оптимальними щодо стану . Останнє означає, що при цих управліннях максимізується показник ефективності на наступних до кінця процесу кроках k +1, ..., n, тобто величина . Показник, що характеризує сумарну ефективність від даного k-го до останнього п-го кроку, будемо позначати через , Тобто . Завдання оптимізації процесу, починаючи з k-го до останнього n-го кроку (рис. 3), схожа на вихідну при початковому стані системи , Управлінні і показнику ефективності [Аналогічно (1.2)]. Вибравши оптимальне управління на що залишилися п - k + l кроки, отримаємо величину , Яка залежить тільки від , Т. е.

. (1.4)

Назвемо величину умовним максимумом. Якщо тепер ми виберемо на k-му кроці деякий довільне керування , То система прийде в стан . Згідно з принципом оптимальності, яке б ми не вибрали, на подальших кроках управління повинен вибиратися так, щоб показник ефективності досягав максимального значення, рівного . Залишається вибрати управління . Його не можна вибирати з умови локальної максимізації показника ефективності на даному k-му кроці, аби отримати . Такий підхід був би недалекоглядним, оскільки від вибору залежить новий стан , А від останнього - максимально можлива ефективність, яка може бути досягнута в подальшому, тобто величина . Тому необхідно вибирати управління так, щоб воно в сукупності з оптимальним керуванням на наступних кроках (починаючи з (k +1) - го) призводило би до спільного максимуму показника ефективності на п-k + l кроках, починаючи з k-го до кінця. Це положення в аналітичній формі можна записати у вигляді наступного співвідношення:

, (1.5)

що отримав назву основного функціонального рівняння ДП, або рівняння Белмана. Схематично співвідношення (1.5) ілюструється на рис. 3.

Малюнок 3

З рівняння (1.5) може бути отримана функція , Якщо відома функція ; Аналогічно можна отримати , Якщо знайдена і т. д., поки не буде визначена величина , Що представляє за визначенням максимальне значення показника ефективності процесу в цілому: .

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

Вирішуючи рівняння (1.5) для визначення умовного максимуму показника ефективності за n-k + l кроків, починаючи з k-го, ми визначаємо відповідне оптимальне управління , При якому цей максимум досягається. Це управління також залежить від . Будемо позначати таке управління через і називати умовним оптимальним керуванням на k-му кроці.

Основне значення рівняння (1.5), в якому реалізована ідея динамічного програмування, полягає в тому, що рішення вихідної задачі визначення - максимуму функції (1.2) n змінних , , ..., зводиться до вирішення послідовності n завдань, що задаються співвідношеннями (1.5), кожне з яких є завданням максимізації функції однієї змінної . Ці завдання виявляються взаємопов'язаними, так як в співвідношенні (1.5) при визначенні враховується знайдена при вирішенні попереднього завдання функція .

2. Оптимальний розподіл ресурсів

2.1 Постановка завдання

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

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

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

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

Завдання 1. Є початкова кількість коштів , Яке необхідно розподілити протягом n років між s підприємствами. Засоби , Виділені у k-му році i-му підприємству, приносять дохід у розмірі і до кінця року мають бути повернені у кількості . У подальшому розподілі дохід може або брати участь (частково або повністю), або не брати участь.

Потрібно визначити такий спосіб розподілу ресурсів (кількість коштів, що виділяються кожному підприємству в кожному плановому році), щоб сумарний дохід від s підприємств за n років був максимальним.

Отже, в якості показника ефективності процесу розподілу ресурсів за n років приймається сумарний дохід, отриманий від s підприємств:

. (2.1)

Кількість ресурсів на початку k-го року будемо характеризувати величиною (Параметр стану). Управління на k-му кроці полягає у виборі змінних , Що позначають ресурси, що виділяються в k-му році i-му підприємству.

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

(2.2)

Якщо ж деяка частина доходу бере участь в подальшому розподілі в якому-небудь році, то до правої частини рівності (2.2) додається відповідна величина.

Потрібно визначити ns невід'ємних змінних , Які відповідають умовам (2.2) і максимізує функцію (2.1).

Обчислювальна процедура ДП починається з введення функції , Що означає дохід, отриманий за п-k +1 років, починаючи з k-го року до кінця аналізованого періоду, при оптимальному розподілі коштів між s підприємствами, якщо у k-му році розподілялося коштів. Функції для задовольняють функціональним рівнянням (1.5), які запишуться у вигляді

(2.3)

При згідно (1.5) отримуємо

. (2.4)

Далі необхідно послідовно вирішити рівняння (2.4) та (2.3) для всіх можливих . Кожне з цих рівнянь являє собою завдання на оптимізацію функції, що залежить від s змінних. Таким чином, завдання з ns змінними зведена до послідовності n завдань, кожна з яких містить s змінних. У цій загальній постановці завдання, як і раніше складна (через багатовимірності) і спростити її, розглядаючи як ns-крокову завдання, в даному випадку не можна. Справді, спробуємо це зробити. Пронумеруємо кроки за номерами підприємств спочатку в 1-му році, потім в 2-м і т. д.:

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

Протягом k-го року стан до початку будь-якого кроку (I = l, 2, .... s) визначиться за попереднім станом за допомогою простого рівняння . Однак після закінчення року, тобто до початку наступного року, до готівкових коштів необхідно буде додати коштів і, отже, стан на початку -Го кроку буде залежати не тільки від попереднього ks-го стану, але і від усіх s станів і управлінь за минулий рік. У результаті ми отримаємо процес з післядією. Щоб виключити післядія, доводиться вводити декілька параметрів стані; завдання на кожному кроці залишається як і раніше складною через багатомірності.

2.2 Двовимірна модель розподілу ресурсів

Завдання 2. Планується діяльність двох підприємств (s = 2) протягом n років. Початкові кошти складають . Засоби x, вкладені в підприємство I, приносять до кінця року дохід і повертаються в розмірі ; Аналогічно, кошти x, вкладені в підприємство II, дають дохід і повертаються в розмірі . Після закінчення року всі кошти, що залишилися заново перерозподіляються між підприємствами I і II, нових засобів не надходить і дохід у виробництво не вкладається.

Потрібно знайти оптимальний спосіб розподілу наявних коштів.

Будемо розглядати процес розподілу коштів як n-кроковий, в якому номер кроку відповідає номеру року. Керована система - два підприємства з вкладеними в них засобами. Система характеризується одним параметром стану - Кількістю коштів, які слід перерозподілити на початку k-го року. Змінних управління на кожному кроці дві: і - Кількість коштів, виділених відповідно підприємству I і II. Оскільки кошти щорічно перерозподіляються повністю, то . Для кожного кроку завдання стає одновимірної. Позначимо через , Тоді .

Показник ефективності k-го кроку дорівнює . Це - дохід, отриманий від двох підприємств протягом k-го року.

Показник ефективності завдання - дохід, отриманий від двох підприємств протягом n років - становить

. (2.5)

Рівняння стану висловлює залишок коштів після k-го кроку і має вигляд

. (2.6)

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

; (2.7)

,

де - Визначається з рівняння стану (2.6).

Завдання 3. Вирішити завдання 2 при наступних умовах: ; ; ; ; ; .

Якщо і - Кошти, виділені відповідно підприємствам I і II в k-му році, то сумарний дохід, отриманий від обох підприємств, дорівнює

,

а рівняння стану (2.6) приймає вигляд

.

Основні функціональні рівняння (2.7) запишуться так:

;

.

Проведемо етап умовної оптимізації.

4-й крок. Умовний оптимальний дохід дорівнює

,

так як лінійна відносно функція досягає максимуму в кінці інтервалу, тобто при .

3-й крок:

.

Коефіцієнт при негативний, тому максимум в цій лінійної щодо функції досягається на початку інтервалу, тобто

; .

2-й крок:

, Звідки ; .

1-й крок:

при .

Результат умовної оптимізації:

; ; ; ;

; ; ;

Перейдемо до безумовної оптимізації. Вважаємо ; Тоді , . Знаючи , Знаходимо ; Використовуючи , Отримуємо і . Аналогічно , . Нарешті, . Отже, кошти по роках потрібно розподілити так:



Рік

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

1

2

3

4

I

0

0

0

5120

II

10000

8000

6400

0

При такому розподілі коштів (10000 крб.) За чотири роки буде отриманий дохід, рівний .

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

2.3 Дискретна динамічна модель оптимального розподілу ресурсів

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

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

Завдання 3. Скласти оптимальний план щорічного розподілу коштів між двома підприємствами протягом трирічного планового періоду при наступних умовах: 1) початкова сума становить 400, 2) вкладені кошти в розмірі x приносять на підприємстві I дохід і повертаються у розмірі 60% від x, а на підприємстві II-відповідно і 20%; 3) щорічно розподіляються всі готівкові кошти, одержувані з повернутих коштів: 4) функції і задано в табл. 1:

Таблиця 9

x


50

100

150

200

250

300

350

400

6

10

15

26

28

38

45

49

8

12

20

28

35

40

46

48

Модель динамічного програмування даної задачі аналогічна моделі, складеній в задачі 1.

Процес управління є трехшаговим. Параметр - Засоби, що підлягають розподілу в k-му році (k = 1, 2, 3). Змінна управління - Кошти, вкладені в підприємство I в k-му році. Кошти, вкладені в підприємство II в k-му році, становлять . Отже, процес управління на k-му кроці залежить від одного параметра (Модель одновимірна). Рівняння стану запишеться у вигляді

, (2.8)

а функціональні рівняння - у вигляді

, (2.9)

. (2.10)

Спробуємо визначити максимально можливі значення, для яких необхідно проводити табулювання на k-му кроці (k = 1, 2, 3). При з рівняння (2.8) визначаємо максимально можливе значення ; Маємо = 0,6-400 = 2400 (всі кошти вкладаються у підприємство I). Аналогічно, для отримуємо граничне значення . Нехай інтервал зміни збігається з табличним, т. е. = 50. Складемо таблицю сумарного прибутку на даному кроці: (Див. табл. 2). Це полегшить подальші розрахунки. Так як , То клітини, розташовані по діагоналі таблиці, відповідають одному й тому ж значенню , Зазначеному в 1-му рядку (у 1-му стовпці) табл. 2. У 2-му рядку таблиці записані значення , А в 2-му стовпці - значення , Взяті з табл. 1. Значення в інших клітинах таблиці отримані складанням чисел і . що стоять на 2-му рядку і в 2-му стовпці та відповідних колонку і рядку, на перетині яких знаходиться дана клітина. Наприклад, для = 150 отримуємо ряд чисел: 20 - для x = 0, у = 150; 18 - для x = 50, y == 100; 18 - для x = 100, y = 50; 15 - для x = 150, y = 0 .

Таблиця 9

x

y

0

50

100

150

200

250

300

350

400

0

0

6

10

15

26

28

38

45

49

50

8

14

18

23

34

36

46

53



100

12

18

22

27

38

40

50



150

20

26

30

35

46

48



200

28

34

38

43

54


250

35

41

45

50



300

40

46

50



350

46

52


400

48



Аналогічну таблицю корисно підготувати і для розрахунків за формулою (2.8). Розрахунок наведено в табл. 3.

Таблиця 9

x

y

0

50

100

150

200

250

300

350

400

0

0

30

60

90

120

150

180

210

240

50

10

40

70

100

130

160

190

220



100

20

50

80

110

140

170

200


150

30

60

90

120

150

180



200

40

70

100

130

160




250

50

80

110

140



300

60

90

120



350

70

100


400

80



Проведемо умовну оптимізацію за звичайною схемою.

3-й крок. Основне рівняння (2.9)

вирішимо за допомогою табл. 2. Як вказувалося вище, . Переглянемо числа на діагоналях, відповідних , 50, 100, 150 і на кожній діагоналі виберемо найбільше. Це і є . У 1-му рядку знаходимо відповідне умовне оптимальне керування. Дані оптимізації на 3-му кроці помістимо в основну таблицю (табл. 4). У ній введений стовпець , Який у подальшому використовується при інтерполяції.

Оптимізація 2-го кроку проведена в табл. 5 згідно рівнянню виду (2.10):

.

Таблиця 9 (основна)

3-й крок

2-й крок




8



10,8


50

8



50

10,8



50





6





9,6



100

14



50

20,4



50





6





8,0



150

20



0

28,4



100











14



200







42,4



200











9,2



250







51,6



200

Таблиця 9

50

100

150

0

50

0

50

100

0

50

100

150

50

0

100

50

0

150

100

50

0

10

30

20

40

60

30

50

70

90

8

6

12

14

10

20

18

18

15

1,6

4,8

3,2

6,4

9,2

4,8

8

10,4

12,8

9,6

10,8

15,2

20,4

19,2

24,8

26

28,4

27,8

Продовження

200

250

0

50

100

150

200

0

50

100

150

200

250

200

150

100

50

0

250

200

150

100

50

0

40

60

80

100

120

50

70

90

110

130

150

28

26

22

23

26

35

34

30

27

31

28

6,4

9,2

11,6

14

16,4

8

10,4

12,8

16,2

17,6

20

34,4

35,2

33,6

37

42,4

43

44,4

42.8

42,2

51,6

48

Результати оптимізації занесені до табл. 4. Для значень , Некратний 50, наведена лінійна інтерполяція функції в табл. 4.

Умовна оптимізація 1-го кроку згідно з рівнянням

для = 400 наведена в допоміжній табл. 6. Для значень, некратний 50, відповідні значення функції отримані інтерполяцією в основний табл. 4.

Таблиця 9

0

50

100

150

200

250

300

350

400

400

350

300

250

200

150

100

50

0

80

100

120

140

160

180

200

220

240

48

52

50

50

54

48

50

53

49

16,6

20,4

23,6

27,8

31,2

36,8

42,4

46,1

49,8

64,6

72,4

73,6

77,8

85,2

84,8

92,4

99,1

98,8

Перейдемо до безумовної оптимізації. З табл. 6 отримуємо Z max = 99, l, = 350, = 50. За і в табл. 3 знаходимо = 220; для цього значення з табл. 4 одержуємо = 200. Отже, = 20. Цьому управлінню в табл. 3 відповідає = 124; для отриманого значення з табл. 4 після інтерполювання знаходимо = 24 і = 100.

Отже, ми отримали такий оптимальний план розподілу коштів між двома підприємствами по роках:

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

1-й рік

2-й рік

3-й рік

I

350

200

24

II

50

20

100

При цьому може бути отриманий максимальний дохід, рівний Z max = 99, l. Прямий підрахунок доходу за табл. 2 для знайденого оптимального управління дає 97,2. Розбіжність у результатах на 1,9 (близько 2%) пояснюється помилкою лінійної інтерполяції.

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

2.4 Облік післядії в задачах оптимального розподілу ресурсів

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

Таким чином, порушується одна з умов, що пред'являються до задач оптимізації, для того щоб їх можна було описати моделлю ДП. Щоб врахувати передісторію процесу розподілу ресурсів, можна збільшити число параметрів стану на кожному кроці, штучно включивши в число фазових координат всі керуючі параметри: попередніх кроків, які визначають післядія. Якщо число таких параметрів велике, то схема ДП ускладнюється настільки, що стає практично непридатною. У разі якщо розмірність штучного фазового простору не перевищує 3-4, то завдання можна вирішити вручну або (для великого числа кроків n) на машині.

Розглянемо модель задачі оптимального розподілу ресурсів з післядією, аналогічну завданню 2.

Завдання 5. Початкові кошти розподіляються між двома підприємствами протягом n років. Дохід, отриманий в кінці k-го року від підприємств I і II, залежить від засобів і , Виділених відповідно в підприємства I і II в k-му році, і від суми всіх вкладених у підприємства I і II коштів відповідно за попередні k - 1 років. Від цих же факторів залежить і величина коштів, які повертаються в кінці кожного року і перерозподіляються в черговому плановому періоді. Нові кошти не надходять, дохід у виробництво не вкладається.

Потрібно знайти оптимальний спосіб розподілу ресурсів між підприємствами I і II на n років.

Позначимо через , функції прибутку, а через і - Функції повернення коштів на підприємстві I і II відповідно.

Стан системи в кінці k-го кроку задовольняє рівнянню

, (2.11)

а дохід, отриманий на k-му кроці від двох підприємств, дорівнює

. (2.12)

Величини (2.11) і (2.12) залежать не тільки від управління на k-му кроці, а й від усіх управлінні на попередніх кроках (процес розподілу ресурсів має последействием).

Введемо в розгляд дві нові фазові координати:

, , (2.13)

вважаючи . Стан системи до початку k-го кроку характеризується трьома параметрами: , , . Так як всі готівкові кошти в k-му році повністю розподіляються між підприємствами I і II, то .

Рівняння стану має вигляд

(2.14)

а дохід на k-му кроці дорівнює

. (2.15)

Сумарний дохід за n років складає

. (2.16)

Потрібно знайти невід'ємні змінні , Обертаються в максимум функцію (2.16) і задовольняють рівнянням (2.14) при початкових умовах , , .

Позначимо через умовний максимальний дохід, отриманий за n - k +1 кроків, починаючи з k-го до n-го включно, при оптимальному розподілі коштів на цих кроках.

Функціональні рівняння (1.5) для мають вигляд

;

. (2.17)

Вирішуючи послідовно рівняння (2.17) для , Отримаємо, як і вище, дві послідовності значень і . Далі при початкових умовах , , , Враховуючи рівняння стану (2.14), по ланцюжку отримаємо оптимальне управління і :



.

Оптимальне управління виходить за формулами , А відповідний максимальний дохід дорівнює .

Розглянемо, як реалізується схема ДП, що враховує передісторію процесу, на наступному дискретної моделі оптимального розподілу ресурсів.

Завдання 6. Засоби = 6 розподіляються між трьома підприємствами, які належать одному об'єднанню і пов'язаними одним технологічним циклом так, що продукція підприємства I служить напівфабрикатом для підприємства II, і продукція перших двох підприємств служить напівфабрикатом для підприємства III. У табл. 7 задані функції , , , Що характеризують випуск продукції в одних і тих же одиницях залежно від вкладених коштів в підприємства I, II, III відповідно. Кожному підприємству можна виділити не більше 5 од. коштів, кратних .

Потрібно розподілити початкові кошти між трьома підприємствами так, щоб максимізувати випуск продукції.

Запишемо модель ДП завдання.

Початковий стан = 6; номер кроку k-номер підприємства (k = l, 2, 3); змінні - Кошти, виділені підприємствам I, II, III відповідно, - задовольняють умовам

. (2.18)

Таблиця 9

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

Продукція

1

2

3

4

5

I


2,1

3,2

4,3

5,1

5,1


II

x 1 x 2

1

2

3

4

5



0

2,2

2,8

3.1

4,3

6



1

3,1

4.2

5,3

7,1

8



2

3,3

4,5

6,1

7,3

-



3

3,5

4,8

6,7

-


-




4

5,4

5,9

-


-

-

III


x 3

x 1 + x 2

1

2

3

4

5



0

3,4

3,8

4,2

5,0

5,0



1

3,7

4,1

4,5

5,3

5,3



2

3,7

4,1

4,5

5,4

-



3

4,0

4,5

4,8

-

-



4

4,2

4,8

-

-

-



5

4,6

-

-

-

-



6

-


-

-

-

-

Показник ефективності - сумарна продукція - дорівнює

. (2.19)

Знайти змінні , Що задовольняють умовам (2.18) і обертаються в максимум функцію (2.19).

Будемо характеризувати стан процесу розподілу коштів на початку k-го кроку двома параметрами: - Залишком коштів після виділення попереднім k -1 підприємствам; - Кількістю коштів, вкладених в попереднє підприємство ( ). Рівняння станів мають вигляд

(2.20)

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

,

, (2.21)

,

Позначимо висловлювання, які стоять у фігурних дужках другого і третього рівнянь (2.21), відповідно через і .

Умовна оптимізація третього кроку зводиться до вирішення першого рівняння з (2.21). Результат її збігається з розділом III табл. 7 (тут ).

Умовна оптимізація 2-го кроку проведена в табл. 8, при цьому в другому з рівнянь (2.21) стану і виражені через і зі співвідношень (2.20). Умовні максимуми для всіх , у таблиці підкреслені. При заповненні табл. 8 використовувалися розділи II і III табл. 7.

Умовна оптимізація 1-го кроку проведена в табл. 9 тільки для = 6. При використанні третього з рівнянь (2.21) і виражені через і зі співвідношень (2.20). При розрахунках в табл. 9 використовувалися розділ I табл. 7 і підкреслені значення табл. 8.

Використовуючи результат умовної оптимізації (табл. 9, 8 і розділ III табл. 7), отримаємо оптимальне рішення.

З таблиці. 9 отримуємо Z max = 15, l; це значення досягається при . Звідси . З таблиці. 8 знаходимо ; Отже, . З розділу III табл.7 визначаємо .

Таким чином, при розподілі = (4, 1, 1) коштів між трьома підприємствами може бути досягнутий максимальний випуск продукції, величина якого дорівнює 15,1 од.

Таблиця 9




0

0

1

0

3,4

3,4

0

3,7

3,7

0

3,7

3,7

0

3,5

3,5

0

4,6

4,6



1

0

2,2

0

2,2

3,1

0

3,1

3,3

0

5,3

4,0

0

4,0

5,4

0

5,4





















0

2

0

3,8

3,8

0

3,8

3,8

0

4,1

4,1

0

4,5

4,5

0

4,8

4,8

2

1

1

2,2

3,7

5,9

3,1

3,7

6,8

3,3

4,0

7,3

3,5

4,2

7,7

5,4

4,6

10,0



2

0

2,8

0

2,8

4,2

0

4,2

4,5

0

4,5

4,8

0

4,8

5,9

0

5,9



















0

3

0

4,0

4,2

0

4,5

4,5

0

4,5

4,5

0

4,8

4,8





1

2

2,2

38

6,0

3,1

4,1

7,2

3,3

4,5

7,8

3,5

4,8

8,3



3

2

1

2,8

3,7

6,5

4,2

4,0

8,2

4,5

4,2

8,7

4,8

4,6

9,4





3

0

3,1

0

3,1

5,3

0

5,3

6,1

0

0

6,7

0

6,7







0

4

0

5

5

0

5,3

5,3

0

5,4

5,4



1

3

2,2

4,5

6,7

3,1

4,5

7,6

3,3

4,8

8,1


4

2

2

2,8

4,1

6,9

4,2

4,5

8,7

4,5

4,8

8,4



3

1

3,1

4

7,1

5,3

4,2

9,5

6,1

4,6

10,7



4

0

4,3

0

4,3

7,1

0

7,1

7,3

0

7,3













0

5

0

5

5

0

5,3

5,3



1

4

2,2

5,3

7,5

3,1

5,4

8,5


5

2

3

2,8

4,5

7,3

4,2

4,8

9



3

2

3,1

4,5

7,6

5,3

4,8

10,1



4

1

4,3

4,2

8,5

7,1

4,6

11,7



5

0

6

0

6

8

0

8










0

6

0

5

5



1

5

2,2

5,3

7,5



2

4

2,8

5,4

8,2


6

3

3

3,1

4,8

7,9



4

2

4,3

4,8

9,1



5

1

6

4,6

10,6



6

0

6

0

6


Таблиця 9

0

6

0

0

10,6

10,6

1

5

1

2,1

11,7

13,8

2

4

2

3,2

10,7

13,9

3

3

3

4,3

9,4

13,7

4

2

4

5,1

10

15,1

5

1

5

5,1

5,4

10,5

Висновок

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

Список використаних джерел

  1. Беллмана Р. Динамічне програмування. М.: ІЛ, 1960. 430 з.

  2. Бронштейн І.М., Семендяев К.А. Довідник з математики для інженерів і учнів Втузов. М.: Наука, 1986. 534 с.

  3. Калліхман І.Л., Войтенко М.А. Динамічне програмування в прикладах і задачах. М.: Вища школа, 1979. 124 с.

  4. Гіммельблау Д.М. Прикладне нелінійне програмування. М.: Світ, 1975. 534с.

Додаток 1

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

# Include <iostream.h>

# Include <conio.h>

# Include <values. H>

//-------------- Визначаємо початкові ресурси --------------------

const ksi _0 = 6;

//-------------- Клас таблиці для виведення ------------------------

class Table

{

int tx, ty, c_x, new_y;

public:

Table ();

void NewString (double a1, double a2, double a3,

double a4, double a5, double a6, double a7);

void EndOfTable ();

};

//------------- Конструктор класу -------------------------------

Table:: Table ()

{

tx = 1, ty = 1;

c_x = 77;

clrscr ();

gotoxy (tx, ty);

cout <<"┌";

for (int i = 0; i <c_x; i + +)

cout <<"─";

cout <<"┐";

gotoxy (tx +7, ty); cout <<"┬";

gotoxy (tx +14, ty); cout <<"┬";

gotoxy (tx +19, ty); cout <<"┬";

gotoxy (tx +26, ty); cout <<"┬";

gotoxy (tx +26, ty); cout <<"┬";

gotoxy (tx +40, ty); cout <<"┬";

gotoxy (tx +63, ty); cout <<"┬";

gotoxy (tx, ty +1); cout <<"│";

gotoxy (tx +2, ty +1); cout <<"ksi1";

gotoxy (tx +7, ty +1); cout <<"│";

gotoxy (tx +9, ty +1); cout <<"eta1";

gotoxy (tx +14, ty +1); cout <<"│";

gotoxy (tx +16, ty +1); cout <<"x1";

gotoxy (tx +19, ty +1); cout <<"│";

gotoxy (tx +21, ty +1); cout <<"ksi2";

gotoxy (tx +26, ty +1); cout <<"│";

gotoxy (tx +28, ty +1); cout <<"f2 (x2, eta1)";

gotoxy (tx +40, ty +1); cout <<"│";

gotoxy (tx +42, ty +1); cout <<"Z3_max (ksi2, eta1 + x1)";

gotoxy (tx +63, ty +1); cout <<"│";

gotoxy (tx +65, ty +1); cout <<"Z2 (ksi1, eta1)";

gotoxy (tx +78, ty +1); cout <<"│";

gotoxy (tx, ty +2); cout <<"├";

for (i = 0; i <c_x; i + +)

cout <<"─";

cout <<"┤";

gotoxy (tx +7, ty +2); cout <<"┼";

gotoxy (tx +14, ty +2); cout <<"┼";

gotoxy (tx +19, ty +2); cout <<"┼";

gotoxy (tx +26, ty +2); cout <<"┼";

gotoxy (tx +26, ty +2); cout <<"┼";

gotoxy (tx +40, ty +2); cout <<"┼";

gotoxy (tx +63, ty +2); cout <<"┼";

new _ y = ty +3;

}

//------------- Визначення методів класу таблиці ---------------

void Table:: NewString (double a1, double a2, double a3,

double a4, double a5, double a6, double a7)

{

gotoxy (tx, new_y);

for (int i = 0; i <c_x; i + +)

cout <<"";

gotoxy (tx +7, ty +2); cout <<"┼";

gotoxy (tx +14, ty +2); cout <<"┼";

gotoxy (tx +19, ty +2); cout <<"┼";

gotoxy (tx +26, ty +2); cout <<"┼";

gotoxy (tx +26, ty +2); cout <<"┼";

gotoxy (tx +40, ty +2); cout <<"┼";

gotoxy (tx +63, ty +2); cout <<"┼";

gotoxy (tx, new_y); cout <<"│";

gotoxy (tx +2, new_y); cout <<a1;

gotoxy (tx +7, new_y); cout <<"│";

gotoxy (tx +9, new_y); cout <<a2;

gotoxy (tx +14, new_y); cout <<"│";

gotoxy (tx +16, new_y); cout <<a3;

gotoxy (tx +19, new_y); cout <<"│";

gotoxy (tx +21, new_y); cout <<a4;

gotoxy (tx +26, new_y); cout <<"│";

gotoxy (tx +28, new_y); cout <<a5;

gotoxy (tx +40, new_y); cout <<"│";

gotoxy (tx +42, new_y); cout <<a6;

gotoxy (tx +63, new_y); cout <<"│";

gotoxy (tx +65, new_y); cout <<a7;

gotoxy (tx +78, new_y); cout <<"│";

new_y + +;

if (new_y> 24)

{

gotoxy (tx, new_y); cout <<"└";

for (int i = 0; i <c_x; i + +)

cout <<"─";

cout <<"┘";

gotoxy (tx +7, ty +2); cout <<"┴";

gotoxy (tx +14, ty +2); cout <<"┴";

gotoxy (tx +19, ty +2); cout <<"┴";

gotoxy (tx +26, ty +2); cout <<"┴";

gotoxy (tx +26, ty +2); cout <<"┴";

gotoxy (tx +40, ty +2); cout <<"┴";

gotoxy (tx +63, ty +2); cout <<"┴";

new_y = ty +3;

}

}

void Table:: EndOfTable ()

{

int i, j;

gotoxy (tx, new_y); cout <<"└";

for (i = 0; i <c_x; i + +)

cout <<"─";

cout <<"┘";

gotoxy (tx +7, ty +2); cout <<"┴";

gotoxy (tx +14, ty +2); cout <<"┴";

gotoxy (tx +19, ty +2); cout <<"┴";

gotoxy (tx +26, ty +2); cout <<"┴";

gotoxy (tx +26, ty +2); cout <<"┴";

gotoxy (tx +40, ty +2); cout <<"┴";

gotoxy (tx +63, ty +2); cout <<"┴";

gotoxy (tx, new_y +1);

for (j = new_y +1; j <26; j + +)

{

for (i = tx; i <c_x +4; i + +)

{

gotoxy (i, j);

cout <<"";

}

}

gotoxy (1,24);

}

//------------ Повідомлення ----------------------------------- ------

void MessageSend (char * MessageForFunc)

{

cout <<MessageForFunc <<endl;

getch ();

}

//---- Визначення функцій, що характеризують випуск продукції -----

double f3 (int arg1, int arg2)

{

if ((arg1 <0 | | arg1> ksi_0) | | (arg2 <0 | | arg2> ksi_0))

return (double) MAXINT;

double Values ​​[ksi_0 +1] [ksi_0 +1] = {0, 3.4, 3.8, 4.2, 5.0, 5.0, 0,

0, 3.7, 4.1, 4.5, 5.3, 5.3, 0,

0, 3.7, 4.1, 4.5, 5.4, 0, 0,

0, 4.0, 4.5, 4.8, 0, 0, 0,

0, 4.2, 4.8, 0, 0, 0, 0,

0, 4.6, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0};

return Values ​​[arg2] [arg1];

}

double f2 (int arg1, int arg2)

{

if ((arg1 <0 | | arg1> ksi_0) | | (arg2 <0 | | arg2> ksi_0))

return (double) MAXINT;

double Values ​​[ksi_0 +1] [ksi_0 +1] = {0, 2.2, 2.8, 3.1, 4.3, 6, 0,

0, 3.1, 4.2, 5.3, 7.1, 8, 0,

0, 3.3, 4.5, 6.1, 7.3, 0, 0,

0, 3.5, 4.8, 6.7, 0, 0, 0,

0, 5.4, 5.9, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0};

return Values ​​[arg2] [arg1];

}

double f1 (int arg1)

{

if (arg1 <0 | | arg1> ksi_0)

return (double) MAXINT;

double Values ​​[ksi_0 +1] = {0, 2.1, 3.2, 4.3, 5.1, 5.1, 0};

return Values ​​[arg1];

}

int main (void)

{

clrscr ();

Table ob;

int ksi, eta, x, i, j, Indexes [6] [5], IndexOfMax = -1, X_opt [3];

double Z_2 [6] [5], Max = 0, MayBeMax = 0, Z_max;

for (i = 0; i <6; i + +)

for (j = 0; j <5; j + +)

{

Z_2 [i] [j] = 0;

Indexes [i] [j] =- 1;

}

for (ksi = 1; ksi <7; ksi + +)

{

for (eta = 0; eta <5; eta + +)

{

Max = MayBeMax = 0;

for (x = 0; x <ksi + 1; x + +)

{

if ((ksi + eta)> 6)

break;

MayBeMax = f2 (x, eta) + f3 (ksi - x, x + eta);

if (Max <MayBeMax)

{

Max = MayBeMax;

IndexOfMax = x;

}

ob.NewString (ksi, eta, x, ksi-x, f2 (x, eta), f3 (ksi - x, x + eta), MayBeMax);

getch ();

}

if (Max> 0)

{

Z_2 [ksi-1] [eta] = Max;

Indexes [ksi-1] [eta] = IndexOfMax;

}

}

}

ob.EndOfTable ();

getch ();

Max = MayBeMax = 0;

for (x = 0; x <ksi_0; x + +)

{

MayBeMax = f1 (x) + Z_2 [ksi_0 - 1 - x] [x];

if (Max <MayBeMax)

{

Max = MayBeMax;

X_opt [0] = x;

}

}

Z_max = Max;

X_opt [1] = Indexes [ksi_0 - 1 - X_opt [0]] [X_opt [0]];

Max = MayBeMax = 0;

for (i = 0; i <ksi_0 + 1; i + +)

{

MayBeMax = f3 (i, X_opt [0] +1);

if (Max <MayBeMax)

{

Max = MayBeMax;

X _ opt [2] = i;

}

}

cout <<"Максимальний випуск продукції:" <<Z_max <<endl;

cout <<"досягається при розподілі коштів:";

cout <<"x1 =" <<X_opt [0] <<", x2 =" <<X_opt [1] <<", x3 =" <<X_opt [2];

getch ();

getch ();

return 0;

}

Результати роботи програми

┌ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ┬ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ┬

│ ksi 1 │ eta 1 │ x 1 │ ksi 2 │ f 2 (x 2, eta 1) │ Z 3_ max (ksi 2, eta 1 + x 1) │ Z 2 (ksi 1, eta 1) │

├ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ┴ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ┴

│ 1 │ 0 │ 0 │ 1 │ 0 │ 3.4 │ 3.4 │

│ 1 │ 0 │ 1 │ 0 │ 2.2 │ 0 │ 2.2 │

│ 1 │ 1 │ 0 │ 1 │ 0 │ 3.7 │ 3.7 │

│ 1 │ 1 │ 1 │ 0 │ 3.1 │ 0 │ 3.1 │

│ 1 │ 2 │ 0 │ 1 │ 0 │ 3.7 │ 3.7 │

│ 1 │ 2 │ 1 │ 0 │ 3.3 │ 0 │ 3.3 │

│ 1 │ 3 │ 0 │ 1 │ 0 │ 4 │ 4 │

│ 1 │ 3 │ 1 │ 0 │ 3.5 │ 0 │ 3.5 │

│ 1 │ 4 │ 0 │ 1 │ 0 │ 4.2 │ 4.2 │

│ 1 │ 4 │ 1 │ 0 │ 5.4 │ 0 │ 5.4 │

│ 2 │ 0 │ 0 │ 2 │ 0 │ 3.8 │ 3.8 │

│ 2 │ 0 │ 1 │ 1 │ 2.2 │ 3.7 │ 5.9 │

│ 2 │ 0 │ 2 │ 0 │ 2.8 │ 0 │ 2.8 │

│ 2 │ 1 │ 0 │ 2 │ 0 │ 4.1 │ 4.1 │

│ 2 │ 1 │ 1 │ 1 │ 3.1 │ 3.7 │ 6.8 │

│ 2 │ 1 │ 2 │ 0 │ 4.2 │ 0 │ 4.2 │

│ 2 │ 2 │ 0 │ 2 │ 0 │ 4.1 │ 4.1 │

│ 2 │ 2 │ 1 │ 1 │ 3.3 │ 4 │ 7.3 │

│ 2 │ 2 │ 2 │ 0 │ 4.5 │ 0 │ 4.5 │

│ 2 │ 3 │ 0 │ 2 │ 0 │ 4.5 │ 4.5 │

│ 2 │ 3 │ 1 │ 1 │ 3.5 │ 4.2 │ 7.7 │

│ 2 │ 3 │ 2 │ 0 │ 4.8 │ 0 │ 4.8 │

│ 2 │ 4 │ 0 │ 2 │ 0 │ 4.8 │ 4.8 │

│ 2 │ 4 │ 1 │ 1 │ 5.4 │ 4.6 │ 10 │

│ 2 │ 4 │ 2 │ 0 │ 5.9 │ 0 │ 5.9 │

│ 3 │ 0 │ 0 │ 3 │ 0 │ 4.2 │ 4.2 │

│ 3 │ 0 │ 1 │ 2 │ 2.2 │ 4.1 │ 6.3 │

│ 3 │ 0 │ 2 │ 1 │ 2.8 │ 3.7 │ 6.5 │

│ 3 │ 0 │ 3 │ 0 │ 3.1 │ 0 │ 3.1 │

│ 3 │ 1 │ 0 │ 3 │ 0 │ 4.5 │ 4.5 │

│ 3 │ 1 │ 1 │ 2 │ 3.1 │ 4.1 │ 7.2 │

│ 3 │ 1 │ 2 │ 1 │ 4.2 │ 4 │ 8.2 │

│ 3 │ 1 │ 3 │ 0 │ 5.3 │ 0 │ 5.3 │

│ 3 │ 2 │ 0 │ 3 │ 0 │ 4.5 │ 4.5 │

│ 3 │ 2 │ 1 │ 2 │ 3.3 │ 4.5 │ 7.8 │

│ 3 │ 2 │ 2 │ 1 │ 4.5 │ 4.2 │ 8.7 │

│ 3 │ 2 │ 3 │ 0 │ 6.1 │ 0 │ 6.1 │

│ 3 │ 3 │ 0 │ 3 │ 0 │ 4.8 │ 4.8 │

│ 3 │ 3 │ 1 │ 2 │ 3.5 │ 4.8 │ 8.3 │

│ 3 │ 3 │ 2 │ 1 │ 4.8 │ 4.6 │ 9.4 │

│ 3 │ 3 │ 3 │ 0 │ 6.7 │ 0 │ 6.7 │

│ 4 │ 0 │ 0 │ 4 │ 0 │ 5 │ 5 │

│ 4 │ 0 │ 1 │ 3 │ 2.2 │ 4.5 │ 6.7 │

│ 4 │ 0 │ 2 │ 2 │ 2.8 │ 4.1 │ 6.9 │

│ 4 │ 0 │ 3 │ 1 │ 3.1 │ 4 │ 7.1 │

│ 4 │ 0 │ 4 │ 0 │ 4.3 │ 0 │ 4.3 │

│ 4 │ 1 │ 0 │ 4 │ 0 │ 5.3 │ 5.3 │

│ 4 │ 1 │ 1 │ 3 │ 3.1 │ 4.5 │ 7.6 │

│ 4 │ 1 │ 2 │ 2 │ 4.2 │ 4.5 │ 8.7 │

│ 4 │ 1 │ 3 │ 1 │ 5.3 │ 4.2 │ 9.5 │

│ 4 │ 1 │ 4 │ 0 │ 7.1 │ 0 │ 7.1 │

│ 4 │ 2 │ 0 │ 4 │ 0 │ 5.4 │ 5.4 │

│ 4 │ 2 │ 1 │ 3 │ 3.3 │ 4.8 │ 8.1 │

│ 4 │ 2 │ 2 │ 2 │ 4.5 │ 4.8 │ 9.3 │

│ 4 │ 2 │ 3 │ 1 │ 6.1 │ 4.6 │ 10.7 │

│ 4 │ 2 │ 4 │ 0 │ 7.3 │ 0 │ 7.3 │

│ 5 │ 0 │ 0 │ 5 │ 0 │ 5 │ 5 │

│ 5 │ 0 │ 1 │ 4 │ 2.2 │ 5.3 │ 7.5 │

│ 5 │ 0 │ 2 │ 3 │ 2.8 │ 4.5 │ 7.3 │

│ 5 │ 0 │ 3 │ 2 │ 3.1 │ 4.5 │ 7.6 │

│ 5 │ 0 │ 4 │ 1 │ 4.3 │ 4.2 │ 8.5 │

│ 5 │ 0 │ 5 │ 0 │ 6 │ 0 │ 6 │

│ 5 │ 1 │ 0 │ 5 │ 0 │ 5.3 │ 5.3 │

│ 5 │ 1 │ 1 │ 4 │ 3.1 │ 5.4 │ 8.5 │

│ 5 │ 1 │ 2 │ 3 │ 4.2 │ 4.8 │ 9 │

│ 5 │ 1 │ 3 │ 2 │ 5.3 │ 4.8 │ 10.1 │

│ 5 │ 1 │ 4 │ 1 │ 7.1 │ 4.6 │ 11.7 │

│ 5 │ 1 │ 5 │ 0 │ 8 │ 0 │ 8 │

│ 6 │ 0 │ 0 │ 6 │ 0 │ 0 │ 0 │

│ 6 │ 0 │ 1 │ 5 │ 2.2 │ 5.3 │ 7.5 │

│ 6 │ 0 │ 2 │ 4 │ 2.8 │ 5.4 │ 8.2 │

│ 6 │ 0 │ 3 │ 3 │ 3.1 │ 4.8 │ 7.9 │

│ 6 │ 0 │ 4 │ 2 │ 4.3 │ 4.8 │ 9.1 │

│ 6 │ 0 │ 5 │ 1 │ 6 │ 4.6 │ 10.6 │

│ 6 │ 0 │ 6 │ 0 │ 0 │ 0 │ 0 │

└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─

Максимальний випуск продукції: 15.1

досягається при розподілі коштів: x1 = 4, x2 = 1, x3 = 1

* Управління на k-му кроці може характеризуватися якісно

* * Термін «ефективність» розуміється як деяка оцінка результату процесу. Вона може висловлювати собою пoкaзaтeль, який бажано максимізувати (наприклад, прибуток, фондовіддача, продуктивність) або показник, який необхідно мінімізувати (наприклад, витрати, собівартість, втрати)


20


Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
307.8кб. | скачати

Схожі роботи:
Ефективність обміну і розподілу ресурсів
Поняття Загроза безпеки Модель порушника Загроза інформаційних ресурсів
Ряд розподілу функція розподілу
Рівновага на товарному ринку Проста кейнсіанська модель модель витрати доходи 2
Рівновага на товарному ринку Проста кейнсіанська модель модель витрати доходи
Маркетингова політика розподілу
Теорія розподілу інформації
Маркетингова політика розподілу 2
Канали розподілу товарів
© Усі права захищені
написати до нас