На головну

Лінійне програмування. Загальні завдання оптимізації.

  1. a. одиничні і загальні імена
  2. I. Завдання семіотики і передумови, необхідні для її розробки
  3. I. До чого прагне педагогіка, якою вона має бути і в чому її завдання?
  4. I. Загальні положення
  5. I. Основні завдання
  6. I. Основні завдання ЗОВНІШНЬОЇ ПОЛІТИКИ
  7. I. Поняття, основні принципи, цілі, завдання та напрями забезпечення безпеки дорожнього руху.

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

f (x)  max (min), де x X

Визначена таким чином задача називається задачею оптимізації, де

Х - допустиме безліч даного завдання

f (x) - цільова функція

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

х  (х1, х2, ..., Хn), Тобто є точкою n-мірного арифметичного простору (Rn), Відповідно Х - це підмножина в Rn, Дуже багато залежить від того як задається безліч Х.

в більшості випадків Х виділяється з Rn за допомогою системи нерівностей.

(2)

q1, q2 , ..., Qm - Задані функції в Rn

Х - безліч точок х1, х2, ..., Хn, Які належать Rn і задовольняють системі нерівностей (2).

У цьому випадку завдання оптимізації набуває наступний вигляд: дана функція з n змінних f (x) і система нерівностей (2). Потрібно знайти максимум або мінімум f (x) при умовах (2). Треба знайти не тільки саме значення максимуму або мінімуму функції, але і точку або точки, якщо їх декілька, в яких це значення досягається, такі точки називаються оптимальними рішеннями. Безліч всіх оптимальних рішень називається оптимальним множиною і позначається Х * .

Дані завдання є завданнями математичного програмування. При цьому f (x) - цільова функція, а нерівності з системи (2) - обмеження. У більшості випадків в ці обмеження входять умови невід'ємності самих змінних (тривіальні обмеження). Залежно від виду функції f (x), а також функцій q1, q2 , ..., Qm розрізняють різні види математичного програмування.

Коли функції лінійні говорять про завдання лінійного програмування.

Завдання лінійного програмування

№1 Завдання про банк.

Власні кошти банку в сумі з депозитами становить 100 млн. $, Частина цих коштів, але не менше 35 млн. $ Повинна бути розміщена в кредитах.

кредити - Чи не ліквідні активи банку, тому існує правило, згідно з яким банки повинні купувати в певній пропорції ліквідні активи (цінні папери), щоб компенсувати НЕ ліквідність кредитів.

Ліквідне обмеження: цінні папери повинні становити не менше 30% коштів, розміщених в кредитах і цінних паперах в сумі.

c1 - Прибутковість кредиту

c2 - Прибутковість цінних паперів

Мета банку: максимізація прибутку.

х1 - Кошти, розміщені в кредитах

х2 - Кошти, розміщені в цінних паперах

f (x) = c1x1 + c2x2  max

№2 Завдання про дієту

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

  A B C  Ціна
 В 1 кг П1 a1 b1 c1 S1
 В 1 кг П2 a2 b2 c2 S2
 потреба a b c  

х1 - Оптимальна кількість продукту 1 (кг)

х2 - Оптимальна кількість продукту 2 (кг)

f (x) = s1x1 + s2x2  min

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

№3 Завдання про використання ресурсів

Підприємство має в своєму розпорядженні певну кількість ресурсів

 ТовариРесурси T1 T2  кількість ресурсу
R1 a11 a12 b1
R2 a21 a22 b2
R3 a31 a32 b3
 Дохід від 1 од. c1 c2  

х1 - Оптимальна кількість товару 1 (кг)

х2 - Оптимальна кількість товару 2 (кг)

f (x) = c1x1 + c2x2  max

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

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

 ПотребітеліПост-ки П1 П2 П3  кількість вугілля
М1 c11\ x1 c12\ x2 c13\ x3 a1
М2 c21 \ x4 c22\ x5 c23\ x6 a2
 потреби b1 b2 b3  

х1-6 - Оптимальна кількість перевезеного вугілля

Транспортна задача є відкритою, якщо a1 + a2 b1 + b2 + b3.

Транспортна задача закритого типу a1 + a2 = b1 + b2 + b3.

f (x) = c11 * x1 + c12 * x2 + c13 * x3 + c21 * x4 + c22 * x5 + c23 * x6  min

 




Лекція №1. 3 сторінка | Лекція №1. 4 сторінка | Лекція №1. 5 сторінка | Лекція №1. 6 сторінка | Лекція №1. 7 сторінка | Лекція №1. 8 сторінка | Лекція №1. 9 сторінка | Лекція №1. 10 сторінка | Лекція №1. 11 сторінка | Лекція №1. 12 сторінка |

© um.co.ua - учбові матеріали та реферати