Головна

Приклади.

  1. Антропогенне екосистема і умови її існування. Приклади.
  2. Вулканогенні родовища. Умови їх утворення і приклади.
  3. Генні хвороби, механізми їх виникнення. Приклади.
  4. Життєвий цикл плоских хробаків. Чергування господарів і феномен зміни господарів. Проміжні та основні господарі. Поняття про біогельмінтом, приклади.
  5. Лекція 3. Ранні підходи до організації БД. Системи, засновані на інвертованих списках, ієрархічні і мережні СУБД. Приклади. Сильні місця і недоліки ранніх систем
  6. Магматичні родовища, умови їх утворення і приклади.
  7. Метали необхідні і токсичні. Приклади.

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

У загальній постановці завдання лінійного програмування формулюється в такий спосіб.

Є якісь змінні  = (x1, x2, ..., xn) І лінійна функція цих змінних, яка носить назву цільової функції. Ставиться завдання: знайти екстремум (максимум чи мінімум) цільової функції за умови, що змінні  задовольняють системі лінійних рівностей і / або нерівностей.

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

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

Завдання щодо складання плану виробництва розглянемо більш докладно.

Нехай деяка виробнича одиниця (підприємство, цех, відділ і т.д.) може виробляти n видів товарів G1, G2, ..., Gn, Використовуючи при цьому m видів сировинних ресурсів R1, R2, ...,Rm, Запаси яких обмежені величинами b1, b2, ...,bm.

Tехнология виробництва товару Gj назвемо набір чисел aij, Який показує, яка кількість i-го ресурсу необхідно для виробництва одиниці товару Gj. Це можна записати у вигляді технологічної матриці, яка повністю описує технологічні потреби виробництва і елементами якої є числа aij.

  G1 G2  ... GТn
R1 a11 a12  ... a11
R2 a21 a22  ... a2n
 ...  ...  ...  ...  ...
Rm am1 am2  ... anm

Припустимо також, що відомі ціни реалізації одиниці кожного товару с1, с2, ..., сn.

позначимо через x1, x2, ..., xn плановане виробництво одиниць товарів G1, G2, ..., Gn. В силу наявної технологічної матриці для цього буде потрібно:

a11x1+a12x2+ ... +a1nxn - ресурсу R1,

a21x1+a22x2+ ... +a2nxn - ресурсу R2,

...

am1x1+am2x2+ ... +amnxn - ресурсу Rm.

З урахуванням обмежень на запаси ресурсів, а також очевидних умов невід'ємності змінних x1, x2, ..., xn отримаємо наступну систему лінійних нерівностей:

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

F=c1x1+c2x2+ ... +cnxn.

Таким чином, з урахуванням природного вимоги невід'ємності змінних отримуємо лінійну оптимізаційну задачу, яка може бути представлена ??в наступній формальної записи:

F=c1x1+c2x2+ ... +cnxn®max

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

B. Форми завдань лінійного програмування. Основні поняття і твердження.

Завдання лінійного програмування математично може бути представлена ??в різних формах.

Загальним завданням ЛП називається задача, яка полягає у визначенні максимального (мінімального) значення функції

 (1.1)

при умовах

 (1.2)

 (1.3)

де aij, bi, cj - задані постійні величини і k ? m.

Функція (1.1) називається цільовою функцією завдання (1.1) - (1.3), а умови (1.2) - (1.3) - обмеженнями даного завдання.

Таким чином, обмеження в загальному завданню ЛП задані у вигляді лінійних нерівностей і / або лінійних рівнянь. При цьому зауважимо, що в нерівностях, взагалі кажучи, можуть застосовуватися обидва знака, як "?", так і "?". Однак домноженіем при необхідності обох частин будь-якого нерівності на (-1) можна звести їх все до єдиного вигляду (1.2).

вектор = (X1 , x2, ..., Xn), компоненти якого задовольняють обмеженням (1.2) - (1.3), називається допустимим планом (або допустимим рішенням).

Сукупність усіх допустимих планів задачі лінійного програмування утворює допустиме безліч рішень цього завдання. Будемо позначати його через Х.

допустимий план  = (X1 *, X2 *, ... Xn *), при якому цільова функція задачі (1) приймає своє максимальне (мінімальне) значення, називається оптимальним.

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

Крім загальної форми розрізняють ще дві приватні задачі лінійного програмування - стандартну і основну.

особливістю стандартної задачі ЛП є те, що її обмеження представлені у вигляді лінійних нерівностей, а також умов невід'ємності на змінні, присутні в задачі:

 (1.4)

обмеження основного завдання ЛП являють собою лінійні обмеження-рівності, а також умови невід'ємності на змінні:

 (1.5)

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

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

 ®min,

то, ввівши в розгляд функцію  , Отримаємо:

 ®max.

Перехід від стандартної завдання до основної пов'язаний з введенням додаткових змінних xn + i , I =1,...,m. Покажемо це на прикладі.

Приклад 1.1. Вихідна задача ЛП має вигляд:

У першому з нерівностей ліва частина не більше правої частини. Тому додаванням в ліву частину деякого невід'ємного доданка x4 можна звести це нерівність до рівності. Аналогічно в другому нерівності ліва частина не менше правої. Отже, віднімаючи з лівої частини деякий невід'ємне число x5, Можна також звести таку нерівність до рівності. Отже, отримаємо нову форму записи завдання ЛП (основну):

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

Вступ | Лінійного програмування.


Глава 2. Елементи матричних ігор | C. Графоаналитический спосіб вирішення завдань лінійного програмування | D. Симплекс-метод | Алгоритм симплекс-методу | Метод штучного базису (М-метод) | Елементи теорії подвійності | Основна теорема подвійності | Третя теорема подвійності | Формальне представлення ігор. Поняття матричної гри | Принцип міінімакса рішення матричних ігор. |

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