Сформулюйте задачу динамічного програмування

В економічній практиці має місце проблема розподілу одного ресурсу (наприклад, капітальних вкладень, бюджетних коштів, тощо) між багатьма напрямками. Для розв’язування задач такого типу досить ефективним є метод динамічного програмування В основі методу лежить ідея застосування апарату рекурент-них співвідношень. Запропонований Р. Беллманом метод дозво-ляє звести процес оптимізації функції п змінних до и-крокового процесу оптимізації функції однієї змінної на кожному кроці. Задачі, для розв’язування яких можливе застосування методу динамічного програмування, повинні задовольняти такі власти-вості: • можливості фактичного або умовного розподілу початкової задачі на окремі підзадачі, кожна з яких містить меншу кількість змінних (навіть до однієї); • однотипності підзадач; • можливості вимірювання однаковими одиницями ефекту від прийнятого рішення в результаті розв’язування кожної підзадачі; • можливості обчислення загального ефекту як суми ефектів в окремих підзадачах. Продемонструємо змістовну та обчислювальну сторони мето.у якого ресурсу. Це може бути запас сировини, енергетичні ресур-си, фінансові, трудові тощо. Існують альтернативні варіанти ви-користання цього ресурсу. В результаті використання ресурсу за тим чи іншим варіантом отримується деякий прибуток, розмір якого залежить від кількос-ті ресурсу, а також від процесу, де конкретно використовується ресурс. Необхідно знайти такий розподіл ресурсу, щоб загальний прибуток був найбільшим.

 

39. Як визначити статус ресурсів прямої задачі та інтервали стійкості двоїстих оцінок відносно зміни запасів дефіцитних ресурсів?

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

40.суть методу Жордана-Гаусса

Суть метода Гаусса состоит в преобразовании (1) к системе с треугольной матрицей, из которой затем последовательно (обратным ходом) получаются значения всех неизвестных. Рассмотрим одну из вычислительных схем. Эта схема называется схемой единственного деления. Итак, рассмотрим эту схему. Пусть a₁₁≠0 (ведущий элемент) разделим на a₁₁ первое уравнение. Получим
(2)
Пользуясь уравнением (2), легко исключить неизвестные x₁ из остальных уравнений системы (для этого достаточно из каждого уравнения вычесть уравнение (2) предварительно умноженное на соответствующий коэффициент при x₁), то есть на первом шаге получим
.
Иными словами, на 1 шаге каждый элемент последующих строк, начиная со второй, равен разности между исходным элементом и произведением его «проекции» на первый столбец и первую (преобразованную) строку.
Вслед за этим оставив первое уравнение в покое, над остальными уравнениями системы, полученной на первом шаге, совершим аналогичное преобразование: выберем из их числа уравнение с ведущим элементом и исключим с его помощью из остальных уравнений x₂ (шаг 2).
После n шагов вместо (1) получим равносильную систему
(3)
Таким образом, на первом этапе мы получим треугольную систему (3). Этот этап называется прямым ходом.
На втором этапе (обратный ход) мы находим последовательно из (3) значения x_n, x_n-1, …, x₁.
Обозначим полученное решение за x₀. Тогда разность

называется невязкой.
Если ε=0, то найденное решение x₀ является верным.

Суть методу Жордана Гаусса

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

Метод Жордана-Гаусса полягає в послідовному виключенні невідомих за допомогою елементарних перетворень:
1) множення рівняння на деяке число;
2)заміна одного з рівнянь системи сумою з іншим рівнянням
тієї ж системи, помножимо на деяке число;
3) видалення з системи рівнянь тотожностей.
З допомогою перетворення 2) можна виключити деяке невідоме із усіх рівнянь системи, крім одного.           

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

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

 

 

41. Назвіть умови оптимальності транспортної задачі.

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

Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість: .

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

Друга умова: Сумарний обсяг продукції, який ввезений кожному j-му споживачу має дорівнювати його потребам.

Третя умова: Сумарна вартість перевезень повинна бути мінімальна.