11. Постановка та матем. Модель закритої тз

ТЗ називається закритою, якщо сумарний попит дорівнює сумарній пропозиції: ∑ⁿ_j=1b_j = ∑_i=1^ma_i

Щоб скласти математичну модель, уведемо матрицю змінних Х = ||х_ij||, де х_ij - запланований обсяг перевезень від A_i до B_j. Очевидно, що розмірність цієї матриці m ´ n і матриця визначає шуканий план перевезень.

Знайдемо вираз кількості товарів, щo вивозиться від A_i. Першому споживачеві заплановано поставку х_і1, другому – х_і2 і т.д., п-му – х_1п. Сума цих величин х_і1 + х_і2 + ... + х_1п, або в скороченому запису∑ⁿ_j=1x_ij визначає запланований вивіз товару від A_i. За умовою задачі весь товар треба вивезти, отже, має виконуватися умова ∑ⁿ_j=1x_ij=a_i (i=1,m)

Аналогічно запланована кількість товару, що надходить до B_j, складається з поставок від А₁ – х_1j, від А₂ – х_2j, від А_m – х_mj. Сума х_1j + х_2j + ...+ х_mj = ∑^m_j=1x_ij – це кількість товару, що направляється до B_j. Оскільки всіх споживачів треба задовольнити, отримуємо таку систему обмежень: ∑^m_j=1x_ij =b_j (j=1,n). При цьому x_ij ³ 0 (i=1,m; j=1,n ).

Тариф перевезень, тобто вартість перевезення одиниці товару за маршрутом А_іB_j становить с_ij. Якщо за цим маршрутом перевозиться x_ij одиниць товару, то затрати становитимуть с_ijx_ij. Вираз ∑^m_j=1 c_ij x_ij відображує вартість перевезень від А_і до всіх B_j. Підсумовуючи його за j, дістаємо вартість перевезень∑ⁿ_j=1∑^m_i=1 c_ij x_ij Згідно з умовою задачі треба знайти план, який забезпечує мінімум транспортних витрат, отже, цільова функція задачі має вигляд Z=∑ⁿ_j=1∑^m_i=1 c_ij x_ij (min). Б-я ТЗ має розвязок.

16. Макроекон. Вф. Функція Кобба-Дугласа

Найбільш часто в економічній практиці зустрічається виробнича функція Кобба-Дугласа: ,

де A,α,β - деякі параметри. Ця функція буде виробничою,якщо буде задовольняти такі неокласичні умови:

1) якщо K>0, L>0, то f(K,L)>0, тобто A*K^α*L^β>0, тому A>0 – взаємодія трудових і виробничих ресурсів призводить до виробництва продукту.

2) Для виробництва необхідно наявність обох ресурсів

K*L=0→f(K,L)=0.

3)при збільшенні використання одного з ресурсів – зростає обсяг виробництва

З умови випливає α>0 і β>0.

4)для частинних похідних 2го порядку мають виконуватись такі вимоги у зв’язку з законом спадної прибутковості

Тому α-1 ≤ 0 та β-1 ≤ 0. 0≤α≤1 0≤β≤1

5)Виробнича функція має бути однорідною, тобто при збільшенні використання всіх ре сурсів у λ раз, обсяг продукції зростає у λ^N раз

Підставимо замість K L відпов λK λL

Функція Кобба – Дугласа – однорідна функція степеня α +β, тобто якщо збільшити використання обох ресурсів у λ раз, то обсяг продукції зросте в

λ^α+β раз, оскільки α+β>0.

Метод потенціалів

У методі потенціалів кожному рядку i і кожному стовпцю j транспортної таблиці ставляться у відповідність числа (потенціали) ui і vj. Для кожної базисної змінної xij, потенціали ui і vj задовольняють рівнянню:

Щоб знайти значення потенціалів з цієї системи рівнянь, потрібно присвоїти одному з них довільне значення (зазвичай вважають u1 = 0) і потім послідовно обчислювати значення інших потенціалів.

Далі, використовуючи знайдені значення потенціалів, для кожної небазисной змінної обчислюються величини ui + vj = cij.

Якщо всі ці числа є недодатними то опорний план є оптимальним і розв'язування на цьому завершується. В іншому випадку знаходиться нйбільше додатне значення і відповідна йому змінна вводиться в базис. Для визначення змінної, що виводиться з базису будується послідовність:

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

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

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

Теорема (умова оптимальності опорного плану транспортної задачі). Якщо для деякого опорного плану Х* = (xij*) існують числа ui та vj, для яких виконуються умови:

1) ui + vj = cij, xij > 0,

2) ui + vj ≤ cij, xij = 0

для всіх та , то він є оптимальним планом транспортної задачі.

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

Алгоритм методу потенціалів складається з таких етапів:

Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.

Побудова першого опорного плану транспортної задачі одним з відомих методів.

Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання.

Перевірка плану транспортної задачі на оптимальність.

4.1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь ui + vj = cij, які записують для всіх заповнених клітинок транспортної таблиці, кількість яких дорівнює , а кількість невідомих — . Кількість рівнянь на одне менша, ніж невідомих, тому система є невизначеною, і одному з потенціалів надають нульове значення. Після цього всі інші потенціали розраховують однозначно.

4.2. Перевірка виконання умови оптимальності для пустих клітин. За допомогою розрахованих потенціалів перевіряють умову оптимальності ui + vj ≤ cij для незаповнених клітинок таблиці. Якщо хоча б для однієї клітини ця умова не виконується, тобто ui + vj > cij, то поточний план є неоптимальним, і від нього необхідно перейти до нового опорного плану.

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

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

4.4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов’язково утвориться цикл (теореми та наслідок § 5.2). У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим — за черговістю знаки «–» та «+». У клітинках зі знаком «–» вибирають значення q і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «–». Якщо значенню q відповідає кілька однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.

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