Xreferat.com » Рефераты по экономико-математическому моделированию » Стандартна задача лінійного програмування

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

src="http://xreferat.ru/image/114/1307194698_220.png" alt="Стандартна задача лінійного програмування" width="57" height="21" align="BOTTOM" border="0" />


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

Рис. 1.

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

Прямі лінії на площиніСтандартна задача лінійного програмування, які паралельні прямій, що визначається рівняннямСтандартна задача лінійного програмуванняназивають лініями рівнів лінійної функції Стандартна задача лінійного програмування. Користуючись поняттям напрямного вектора Стандартна задача лінійного програмування , можемо визначити розміщення півплощинСтандартна задача лінійного програмування і Стандартна задача лінійного програмування на координатній площині Стандартна задача лінійного програмування. Півплощина Стандартна задача лінійного програмування розміщена по той бік прямоїСтандартна задача лінійного програмування, куди показує напрямний вектор -Стандартна задача лінійного програмування. Аналогічно вектор Стандартна задача лінійного програмування показує, де розміщена півплощина Стандартна задача лінійного програмування відносно прямої Стандартна задача лінійного програмування побудуємо напрямний вектор N = (3,-2). Напрямний вектор міститься у шуканій півплощині, яка виділена штриховими лініями (рис 3.2).


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

Рис. 3.2


Якщо врахувати, що множина точок, що задовольняє рівняння


Стандартна задача лінійного програмування 29.)


при п = 3, є півплощина, а при п > 3 - гіперплощина в n-вимірному просторі, то лему 3 можна поширити на випадок трьох і більше змінних.

Теорема 2. Множиною всіх розв'язків лінійної нерівності з п змінними


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

є одним з півпросторів, на які весь простір розділяється площиною або гіперплощиною (29), включаючи й саму площину (гіперплощину).

Розглянемо множину розв'язків систем нерівностей.

Теорема 3. Множиною розв'язків сумісної системи т лінійних нерівностей з двома змінними


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


є опуклим многокутником.

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

Теорема 4. Множина розв'язків сумісної системи т лінійних нерівностей з п змінними є опуклим многогранником в n-вимірному просторі.

Теорема 5. Множиною всіх допустимих розв'язків сумісної системи т лінійних рівнянь з п змінними (Стандартна задача лінійного програмування) є опуклим многогранником в n-вимірному просторі.

Теорема 6. Оптимальне значення задачі лінійного програмування досягається у вершині многогранника розв'язків системи обмежень.

Результати цього підрозділу дають змогу так інтерпретувати задачі лінійного програмування:

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

Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Техніко-економічні показники вирощування цих культур маємо у табл. 2:


Таблиця 2 Показники вирощування сільськогосподарських культур

Показник (із розрахунку на 1 га) Озима пшениця Цукрові буряки Наявний ресурс
Затрати праці, людино-днів 5 25 270
Затрати праці механізаторів, людино-днів 2 8 80
Урожайність, тонн 3,5 40 —
Прибуток, тис. грн. 0,7 1 —

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

Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрових буряків, ввівши такі позначення:

x1 — шукана площа посіву озимої пшениці, га;

x2— шукана площа посіву цукрових буряків, га.

Задача лінійного програмування має такий вигляд:


Стандартна задача лінійного програмування (38)


за умов:


Стандартна задача лінійного програмування (39)

Стандартна задача лінійного програмування (40)

Стандартна задача лінійного програмування (41)

Стандартна задача лінійного програмування (42)

Стандартна задача лінійного програмування (43)


Геометричну інтерпретацію задачі зображено на рис. 2.2.

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

Рис. 2.2. Область допустимих розв'язків задачі


Область допустимих розв'язків цієї задачі дістаємо так. Кожне обмеження, наприклад Стандартна задача лінійного програмування задає півплощину з граничною прямою Стандартна задача лінійного програмування. Будуємо її і визначаємо півплощину, яка описується нерівністю Стандартна задача лінійного програмування.З цією метою в нерівність Стандартна задача лінійного програмування підставляємо координати характерної точки, скажімо,Стандартна задача лінійного програмуванняіСтандартна задача лінійного програмування. Переконуємося, що ця точка належить півплощині Стандартна задача лінійного програмування. Цей факт на рис. 2.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (39)—(43). У результаті перетину цих півплощин утворюється область допустимих розв'язків задачі (на рис. 2.2 — чотирикутник ABCD). Цільова функція Z = 0,7x1+х2 являє собою сім'ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z=0, то маємо Z = 0,7x1+х2=0. Ця пряма проходить через початок системи координат. Коли Z= 3,5, то маємо пряму 0,7x1+х2=3,5.


6. Розв’язання стандартної задачі симплекс-методу


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

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

Алгоритм розв'язування задачі лінійного програмування симплекс-методом складається з п'яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

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

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

5. Повторення дій починаючи з п. 3. Розглянемо докладніше кожний з етапів алгоритму.

1. Визначення першого опорного плану починають із запису задачі лінійного програмування в канонічній формі, тобто у вигляді обмежень-рівнянь з невід'ємними правими частинами. Якщо в умові задачі присутні обмеження-нерівності, то перетворення їх на рівняння виконується за допомогою додаткових змінних, які вводяться до лівої частини обмежень типу «<» зі знаком «+», а до обмежень типу «>» — зі знаком «-». У цільовій функції задачі додаткові змінні мають коефіцієнт нуль.

Після зведення задачі до канонічного вигляду її записують у векторній формі. За означенням опорного плану задачі лінійного програмування його утворюють т одиничних лінійно незалежних векторів, які становлять базис w-вимірного простору (де m — кількість обмежень у задачі лінійного програмування).

На цьому етапі розв'язування задачі можливі такі випадки:

після запису задачі у векторній формі в системі обмежень є необхідна кількість одиничних векторів. Тоді початковий опорний план визначається безпосередньо без додаткових дій;

у системі обмежень немає необхідної кількості одиничних незалежних векторів. Тоді для побудови першого опорного плану застосовують метод штучного базису. Ідея його полягає в тому, що відсутні одиничні вектори можна дістати, увівши до відповідних обмежень деякі змінні з коефіцієнтом +1, які називаються штучними. У цільовій функції задачі лінійного програмування штучні змінні мають коефіцієнт +М (для задачі на min) або —М (для задачі на max), де М— досить велике додатне число.

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

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

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

Наступний стовпчик симплексної таблиці — «Сбаз» — коефіцієнти при базисних змінних у цільовій функції задачі.

У третьому стовпчику — «План» — записують значення базисних змінних і відшукувані у процесі розв'язування задачі компоненти оптимального плану.

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

3. Перевіряють опорний план на оптимальність згідно з наведеною далі теоремою.

Теорема (ознака оптимальності опорного плану). Опорний план Стандартна задача лінійного програмування задачі лінійного програмування є оптимальним, якщо для всіх Стандартна задача лінійного програмування виконується умова Стандартна задача лінійного програмування (для задачі на max) або : Стандартна задача лінійного програмування (для задачі на min)

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

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


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


або безпосередньо із симплексної таблиці як скалярний добуток векторів-стовпчиків «Сбаз» та «xj» мінус відповідний коефіцієнт Стандартна задача лінійного програмування.Розраховані оцінки записують в окремий рядок симплексної таблиці, який називають оцінковим.

У процесі перевірки умови оптимальності можливі такі випадки:

а) усіСтандартна задача лінійного програмуваннязадовольняють умову оптимальності, і тоді визначений опорний план є оптимальним;

б) не всі Стандартна задача лінійного програмування задовольняють умову оптимальності, і тоді потрібно виконати перехід до наступного, нового опорного плану задачі.

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

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

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

Перетином напрямного стовпчика та напрямного рядка визначається число симплексної таблиці Стандартна задача лінійного програмування, яке називають розв'язувальним елементом. За допомогою елемента Стандартна задача лінійного програмування і методу Жордана—Гаусса розраховують нову симплексну таблицю.

Далі ітераційний процес повторюють доти, доки не буде визначено оптимальний план задачі.

У разі застосування симплекс-методу для розв'язування задач лінійного програмування можливі такі випадки.

1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка Стандартна задача лінійного програмування відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв'язувальний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.

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

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

Навчальні завдання розв'язування задач симплекс-методом

Розглянемо застосування симплекс-методу для розв'язування деяких задач лінійного програмування.

Задача 2.41.

Продукція чотирьох видів А, В, С і Д проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду задано таблицею.


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

А В С Д

1

2

2

3

3

2

4

1

2

2


Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-год становить 10 дол. для верстата 1 і 15 дол. — для верстата 2. Можливий час використання верстатів обмежений: для верстата 1 він становить 450 машино-год, а для верстата 2 — 380 машино-год.

Ціна одиниці продукції кожного виду дорівнює відповідно 73, 70, 55 та 45 дол.

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

Побудова математичної моделі. Нехай Стандартна задача лінійного програмування— план виробництва продукціїу-го виду, де у може набувати значень від 1 до 4.

Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:


для верстата 1 Стандартна задача лінійного програмування (машино-год);

для верстата 2 Стандартна задача лінійного програмування(машино-год).


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


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


Отже, математична модель поставленої задачі має такий вигляд:


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


Розв'язування. Розв'яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.

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


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


Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:


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


Канонічну систему обмежень задачі запишемо у векторній формі: >і


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


де


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


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


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


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


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


Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням


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


є опорним планом задачі і для цього початкового плану


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


2. Складемо симплексну таблицю для першого опорного плану задачі.


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


Елементи останнього рядка симплекс-таблиці є оцінками Δj, за допомогою яких опорний план перевіряють на оптимальність. їх визначають так:


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


У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану:Стандартна задача лінійного програмування=0-450 + 0-380 = 0.

3. Після обчислення всіх оцінок опорний план перевіряють на оптимальність. Для цього продивляються елементи оцінкового рядка. Якщо всі Стандартна задача лінійного програмування (для задачі на max) або Стандартна задача лінійного програмування (для задачі на min), визначений опорний план є оптимальним. Якщо ж в оцінковому рядку присутня хоча б одна оцінка, що не задовольняє умову оптималь-ності (від'ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.

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

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

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

Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення Стандартна задача лінійного програмування і вибираємо найменше значення. Згідно з даними симплексної таблиці бачимо, що minСтандартна задача лінійного програмування, і тому з базису виключаємо зміннуСтандартна задача лінійного програмування, а числоСтандартна задача лінійного програмування= 3 називатимемо розв'язувальним елементом. Подальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса.

Друга симплексна таблиця має такий вигляд:


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


У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «Стандартна задача лінійного програмування», а решту елементів нової таблиці розраховують за розглянутими далі правилами:

1. Розв'язувальний (напрямний) рядок необхідно поділити на розв'язувальний елемент і здобуті числа записати у відповідний рядок нової симплексної таблиці.

2. Розв'язувальний стовпчик у новій таблиці записують як одиничний

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: