Реферати українською » Экономико-математическое моделирование » Лінійне програмування як метод оптимізації


Реферат Лінійне програмування як метод оптимізації

Страница 1 из 3 | Следующая страница

Зміст

Запровадження

1. Загальна завдання лінійного програмування (ЛЗ)

2. Приведення завдання лінійного програмування до стандартної формі

3. Приклади економічних завдань, наведених до завдань ЛЗ

4.Геометрический метод вирішення завдань ЛЗ

5.Симплексний метод вирішення завдань ЛЗ

6.Теореми двоїстості і їх використання в завданнях ЛЗ

6. Транспортна завдання і її рішення методом потенціалів

Укладання

Література


Запровадження

Нині оптимізація застосовується у науці, техніки і будь-якій іншій області людської діяльності.

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

Пошуки оптимальних рішень увінчалися створенням спеціальних математичних методів і у 18 столітті було закладено математичні основи оптимізації (варіаційне літочислення, чисельні методи лікування й ін.). Проте до другої половини 20 століття методи оптимізації у багатьох областях науку й техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, яку без ЕОМ реалізувати було конче важко, а деяких випадках - неможливо.

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

· кількість продукції - витрата сировини

· кількість продукції - якість продукції

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

При постановці завдання оптимізації необхідно:

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

Типовий приклад неправильної постановки завдання оптимізації:

"Одержати максимальну продуктивність при мінімальної собівартості".

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

Правильна завдання можна було наступна:

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

б) отримати мінімальну собівартість при заданої продуктивності;

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

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

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

4. Облік обмежень.

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

Критерієм оптимальності називається кількісну оцінкуоптимизируемого якості об'єкта.

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

Отже, завдання оптимізації зводиться до пошукуекстремума цільової функції.

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

>Линейное програмування - з перших і найбільш докладно вивчених розділів математичного програмування. Саме лінійне програмування стало тим розділом, від якого почала розвиватися сама дисципліна "математичне програмування". Термін "програмування" в назві дисципліни нічого спільного з терміном "програмування (тобто. складання програм) для ЕОМ" немає, оскільки дисципліна "лінійне програмування" виникла доти, коли ЕОМ стали широко застосовуватися під час вирішення математичних, інженерних, економічних пріоритетів і ін. завдань. Термін "лінійне програмування" виникла у результаті неточного перекладу англійського ">linearprogramming". Один із значень слова ">programming" - складання планів, планування. Отже, правильним перекладом ">linearprogramming" було би "лінійне програмування", а "лінійне планування", що як точно відображає зміст дисципліни. Проте, термін лінійне програмування, нелінійне програмування тощо. з нашого літературі стали загальноприйнятими.

Отже, лінійне програмування виникла після Другий Світовий Війни і став швидко розвиватися, залучаючи увагу математиків, економістів і інженерів завдяки можливості широкого практичного застосування, а як і математичної "стрункості".

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

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

>Линейное програмування є найчастіше використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:

· раціонального використання сировини й матеріалів; завдання оптимізації розкроювання;

· оптимізації виробничої програми підприємств;

· оптимального розміщення й концентрації виробництва;

· складання оптимального плану перевезень, роботи транспорту;

· управління виробничими запасами;

· і ще, належать сфері оптимального планування.

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

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

Значне розвиток теорія і алгоритмічний апарат лінійного програмування отримали з винаходом і поширенням ЕОМ і формулюванням американським математиком Дж.Дансингомсимплекс-метода.

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

Завдання з нелінійної цільової функцією і лінійними обмеженнями називають завданнями нелінійного програмування з лінійними обмеженнями.Оптимизационние завдання що така можна класифікувати з урахуванням на структурні особливості нелінійних цільових функцій. Якщо цільова функція Є - квадратична функція, ми маємо працювати з завданнямквадратичного програмування; якщо Є - цей показник лінійних функцій, то відповідна завдання називається завданнядробно-линейного програмування, тощо. Розподіл оптимізаційних завдань для цієї класи представляє значний інтерес, оскільки специфічні особливості тих чи інших завдань відіграють істотне значення розробки методів розв'язання.


1. Загальна завдання лінійного програмування (ЛЗ)

 

Завдання лінійного програмування (ЛЗ) полягає у перебування мінімуму (чи максимуму) лінійної функції при лінійних обмеженнях.

Загальна форма завдання має вигляд: знайти за умов

Де

Тут і далі нам зручніше вважати сек. і ай вектор - рядками, а x і b= (b1,...,b>m) T - вектор стовпчиками.

Поруч із загальної формою широко використовуються також канонічна і стандартна форми. Як у канонічної, і у стандартної формі

тобто. все перемінні у кожному допустимому виконанні завдання враховувалинеотрицательние значення (такі перемінні прийнято називати >неотрицательние на відміну провільних змінних, галузь значень яких отаке обмеження не накладається). Відмінність ж між тими формами у тому, що у тому випадку I2 = 0, а іншому - I1 = 0.

Завдання ЛЗ в канонічної формі:


                        (2.1)

                                   (2.2)

                                     (2.3)

Завдання ЛЗ у кімнаті стандартного формі:

У обох випадках А матриця розмірностіm x n,i-я рядок якої збігаються з вектором аі.

Завдання ЛЗ у спільній формі зводиться (у сенсі) до завданню ЛЗ в канонічної (стандартної) формі. Під цим розуміється існування загального способу побудови по вихідної завданню (у спільній формі) нового завдання ЛЗ (у потрібній нам формі), будь-яке оптимальне яке "легко" перетворюється на оптимальне рішення вихідної завдання й навпаки. (Фактично, зв'язок між тими завданнями виявляється ще більше тісній). Тим самим було ми маємо можливість, не втрачаючи спільності, займатися вивченням завдань ЛЗ, представлених або у канонічної, або у стандартної формі. Через це наші подальші розгляду завдань ЛЗ буде присвячено, переважно, завданням в канонічної формі.

 

2. Приведення завдання лінійного програмування до стандартної формі

 

Будь-яка завдання лінійного програмування наводиться до стандартної (канонічної) формі основної мети лінійного програмування, яка формулюється так: знайтинеотрицательние значення зміннихX1,X2,Xn, які відповідають обмеженням як рівностей:

>A11X1 +A12X2 + … +A1nXn =B1;

>A21X1 +A22X2 + … +A2nXn =B2;

……………………………………

>Am1X1 +Am2X2 + … +AmnXn =Bm;

>Xj 0,j=1,…,n

і що звертають в максимум лінійну функцію цих змінних:

E =C1X1 +C2X2 + … +CnXnmax

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

>Bj 0,j=1,…,n

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

вийти з мінімізації цільової функції до її максимізації;

змінити знаки правих частин обмежень;

вийти зограничений-неравенств доравенствам;

позбутися змінних, які мають обмежень на знак.

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


3. Приклади економічних завдань, наведених до завдань ЛЗ

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

Розглянемо окремі.

Визначення оптимального асортименту. Єm видів ресурсів у кількостяхb1,b2,., bі, b>m і n видів виробів.Задана матрицяA=||a>ij||,i=1,.,m,j=1,.,n, де a>ij характеризує добові норми витратi-го ресурсу на одиницюj-го виду виробів. Ефективність виробництваj-го виду виробів характеризується показником Зj, що задовольняє умові лінійності. Потрібно визначити такий план випуску виробів (оптимальний асортимент), у якому сумарний показник ефективності буде найбільший.

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

                     (3.1)

при обмеженнях

                   (3.2)

Крім обмежень на ресурси (3.2) у цю модель можна запровадити додаткових обмежень на запланований рівень випуску продукції , xі: xj: x>k = bі: bj: b>k всім і, j,k тощо.

Оптимальний розподіл взаємозамінних ресурсів. Єm видів взаємозамінних ресурсів а1, а2,., а>m, використовуваних і під час n різних робіт (завдань). Обсяги робіт, що їх виконані, становлять b1, b2,., bі, bn одиниць.Задани числа , що вказують, скільки одиницьj-й роботи можна з одиниціі-го ресурсу, і навіть З>ij - видатки виробництвоj-й роботи з одиниціi-го ресурсу. Потрібна розподілити ресурси на роботах в такий спосіб, щоб сумарна ефективність виконаних робіт була максимальної (чи сумарні витрати - мінімальними).

Це завдання називається загальної розподільній завданням. Кількість одиницьi-го ресурсу, яке виділено виконання робітj-го виду, позначимо через x>ij.

Математична модель аналізованої завдання така:

                     (3.3)

при обмеженнях

                       (3.4)

                         (3.5)

Обмеження (3.4) означає, що план усіх фізичних робіт може бути виконано повністю, а (3.5) означає, що ресурси би мало бути витрачені повністю.

Прикладом це завдання то, можливо завдання розподілу літаків по авіалініям.

Завдання про сумішах. Є р компонентів, при поєднанні що у різних пропорціях отримують різні суміші. Кожен компонент, отже й суміш, міститьq речовин. Кількістьk-го речовиниk = 1, 2,.,q, що до складу одиниціі-го компонента і до складу одиниці суміші, позначимо через а>ik і а>k відповідно.

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

>Задано р величин Зі, характеризуючих вартість, масу чи калорійність одиниціi-го компонента, іq величин b>k, вказують мінімально необхідне відсотковий вмістk-го речовини в суміші. Означимо через x1, x2,.,xр значення компонентар-го виду, що до складу суміші.

Математична модель це завдання має тої вид:

                       (3.6)

при обмеження

                   (3.7)

Обмеження (3.7) означає, що відсотковий вмістk-го речовини в одиниці суміші має не менше b>k.

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

4.Геометрический метод вирішення завдань ЛЗ

Завдання 1. При відгодівлі кожну особину повинно отримати щонайменше 14ед.питательного речовини P.S1, щонайменше 15 од. речовини P.S2 і проінвестували щонайменше 10 речовини P.S3. Для складання раціону використовують два виду корми. Зміст кількості одиниць поживних речовин, у 1 кілограмі кожного виду корми й вартість одного кілограма корми дана в таблиці 1.

Таблиця 1

Живильні речовини Кількість одиниць поживних речовин, у 1 кг. корми
корм 1 корм 2

P.S1

1 2

P.S2

1 3

P.S3

2 1
Вартість 1 кг. корми 3 7

Скласти раціон мінімальної вартості.

Рішення:

>X1 +2X2 14

>X1 +3X2 15

>2X1 +X2 10

>X1,X2 0

>3X1 + 7X2 min

 >X1 +2X2 = 14

>X1 +3X2 =15

>2X1 +X2 = 10


 

5.Симплексний метод вирішення завдань ЛЗ

Завдання 2. Для виготовлення4-ех видів продукціїP1,P2,P3,P4 використовують два виду сировини: P.S1 і P.S2. Запаси сировини, кількість одиниць сировини, витрачених на виготовлення одиниці виробленої продукції, а як і величина прибутку, отримувана від одиниці виробленої продукції, наведені у таблиці 2.

Таблиця 2.

Вигляд сировини Запас сировини Кількість одиниць сировини, які йдуть на виготовлення одиниці виробленої продукції

>P1

>P2

>P3

>P4

P.S1

3 1 1 1 2

P.S2

7 1 2 3 1
Прибуток від одиниці виробленої продукції 9 14 15 10

Скласти план виробництва, який биполучений максимального прибутку.

Рішення:

1. Формальна завдання має такий вигляд:

>9X1 +14X2 + 15X3 +10X4 max

>X1 +X2 +X3 +2X4 3

>X1 +2X2 +3X3 +X4 7

>X1,X2,X3,X4 0

2. Наведемо до стандартної (канонічної) формі:

F =9X1 +14X2 +>15X3 +10X4 +0X5 +0X6

>X1 +X2 +X3 +2X4 + X5 = 3

>X1 +2X2 +>3X3

Страница 1 из 3 | Следующая страница

Схожі реферати:

Навігація