|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Симплексний метод рішення задач лінійного програмуванняІснує багато методів які дозволяють знайти оптимальне рішення в задачах лінійного програмування (ЗЛП). Одним з таких методів, який дозволяє ефективно вирішувати такі задачі є симплекс метод. Ідея цього методу складається з переходів від одного розв’язку xk до другого xk+1, для яких виконується умова f(xk) > f(xk+1). Для переходу від одного розв’язку до другого використовуються симлексні таблиці. Кожній симплексній таблиці відповідає один з розв’язків задачі. По змісту симплексної таблиці можна визначити, чі оптимальне рішення знайдено, або що задача рішень не має. Послідовність рішення задачі лінійного програмування за допомогою симплексного методу. Рішення задачі лінійного програмування виконується в наступній послідовності: Крок 1. Здійснюється перевірка економіко-математичної моделі на відповідність канонічному виду. Якщо модель не відповідає вимогам, то виконується приведення моделі до канонічного виду. Крок 2. Для таблиці обмежень будується матриця коефіцієнтів та визначається базіс. Якщо треба, то послідовно у кожній строці визначається базисна змінна і за методом Гауса проводяться необхідні перетворення. Кожна базисна зміна має бути присутньою тільки в одній строці обмежень. Нехай Xk , Xk+1, …, Xk+j - є базіс, тогда Xk= B1, Xk+1= B2, …, Xk+j= Bm – є базисний розв’язок. Подальша задача полягає в тому, щоб від початкового допустимого базисного розв’язку перейти до іншого базисного розв’язку, при якому значення лінійної форми зменшиться. Лінійна форма при початковому базисному розв’язку дорівнює нулю. Для поліпшення результатів розв’язку на кожному кроці треба перевести одну змінну з неосновних в основні і одну змінну з основних в неосновні, тобто дві змінні міняються місцями. Крок 3. Будуємо симлекс таблицю для лінійної моделі наступного виду: Таблиця 1.5.1
В таблиці k, k+1, k+j < n, (Xk , Xk+1, …, Xk+j ) – початковий базіс рішення. Крок 4. Серед коефіцієтів Ci (i = 1,n) обираємо Ci < 0 той, що має найменше значення (найбільше за абсолютним значенням). Стовпець з обраним Ci визначає змінну, яку треба перенести до базису. Щоб обрати змінну, яку треба виключити з бази розраховуємо оценку, яка визнається як Bi /aij. Виключати треба змінну, яка буде мати найменшу оцінку. Крок 5. Після визначення змінної - притендента на перенесення в базис, використовуючі метод Гауса треба провести відповідні розрахунки в обмеженнях. Для цього строку обмежень з визначеною зміною пділимо на коефіцієнт при цей зміной. Потім знаходимо чому дорівнює ця змінна через інші змінні і підставляємо її значення в інші строки обмеження і лінейну форму. Крок 6. За результатми проведених змін оновлюємо симплекс таблицю. Якщо серед коефіцієтів Ci (i = 1,n) є Ci < 0, то переходимо до кроку 4. Якщо всі Ci ³ 0, то знайдено оптимальне рішення. Приклад 1. В прикладі 1 розділа 1.1 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти максимальне значення цільової функції
F = 10x1 + 12 x2 ® max при обмеженнях на ресурси виробництва по металу, склу та трудовим ресурсам відповідно до технологічних норм, 4x1 + 5x2 £ 300 2x1 + x2 £ 100 2x1 + 3x2 £ 160 x1 ³ 0; x2 ³ 0 Приводимо модель до канонічного виду
F = - 10x1 - 12 x2 ® min при обмеженнях 4x1 + 5x2 + x3 = 300 2x1 + x2 + x4 = 100 2x1 + 3x2 + x5 = 160 x1 ³ 0; x2 ³ 0; x3 ³ 0; x4 ³ 0; x5 ³ 0 Будуємо сімплекс таблицю і визначаємо базіс. Так як додаткові змінні x3, x4, x5 мають кофецієнт одиницю та присутні тільке один раз в кожній строці обмежень, то ці змінні можуть створювати базіс. Таблиця 1.5.2
Аналізуємо остнню строку таблиці та визначаємо стовпець зі змінною, яку треба перенести до базису. В нашому випадку найменше значення “ -12 ”, що відповідає знмінній x2. Визначаємо змінну, яку треба вивести з базісу. Для цього вільні значення (стовпець В) ділимо на коефіцієнти у відповідних строках стовпця x2. За підсумками маємо значення 300 / 5; 100 / 1; 160 / 3 або 60; 100; 53,33333 Найменше значення знаходиться в строці зі змінною x5. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x2 замість x5. Обмеження, у якому визначено x2 і x5 поділимо на 3 і отримуємо (2/3)x1 + x2 + (1/3)x5 = 160/3. Вирішуємо рівняння відносно x2 x2 = 160/3 -(2/3)x1 - (1/3)x5
Отримане значення x2 підставляємо в інші обмеження і цільову функцію.
4x1 + 5(160/3 -(2/3)x1 - (1/3)x5) + x3 = 300 або (2/3)x1+ x3 - (5/3)x5 = 100/3, 2x1 + 160/3 -(2/3)x1 - (1/3)x5 + x4 = 100 або (4/3)x1+ x4 - (1/3)x5 = 140/3. Підставляємо значення x2 в цільову функцію
F = - 10x1 - 12 (160/3 -(2/3)x1 - (1/3)x5) або- 2x1 + 4x5 – 640 ® min,
і отримуємо нову систему цільової функції і обмежень
F = - 2x1 + 4x5 – 640 ® min, при обмеженнях (2/3)x1+ x3 - (5/3)x5 = 100/3 (4/3)x1+ x4 - (1/3)x5 = 140/3 (2/3)x1 + x2 + (1/3)x5 = 160/3
Будуємо нову сімлекс таблицю: Таблиця 1.5.3
Знову визначаємо змінну, яку треба перевести до базісу. За підсумками аналізу ніжньої строки це змінна x1 . Визначаємо змінну, яку треба вивести з базісу. Для цього вільні значення (стовпець В) ділимо на коефіцієнти у відповідних строках стовпця x1. За підсумками маємо значення
(100/3):(2/3) = 50; (140/3):(4/3) = 35; (160/3):(2/3) = 80 На цьому кроці найменше значення знаходиться в строці зі змінною x4. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x1 замість x4. Обмеження, у якому визначено x1 і x4 поділимо на 4/3 і отримуємо x1 + (3/4)x4 - (1/4)x5 = 35. Вирішуємо рівняння відносно x1 x1 = 35 - (3/4)x4 + (1/4)x5
Отримане значення x1 підставляємо в інші обмеження і цільову функцію.
2/3(35 - (3/4)x4 + (1/4)x5) + x3 + (5/3)x5 = 100/3 або x3 - (1/2)x4 - (3/2)x5 = 10, 2/3(35 - (3/4)x4 + (1/4)x5) + x2 + (1/3)x5 = 160/3 або x2 - (1/2)x4 + (1/2)x5 = 30, Підставляємо значення x2 в цільову функцію
F = - 2(35 - (3/4)x4 + (1/4)x5) + 4x5 – 640 ® min, або 1,5 x4 + 3,5x5 – 710 ® min,
і отримуємо нову систему цільової функції і обмежень
F = 1,5x4 + 3,5x5 – 710 ® min, при обмеженнях x3 - (1/2)x4 - (3/2)x5 = 10 x1 + (3/4)x4 - (1/4)x5 = 35 x2 - (1/2)x4 + (1/2)x5 = 30, Будуємо нову сімлекс таблицю: Таблиця 1.5.4
В нової таблиці немає відємних значень в останій строці. Тому ми маємо оптимальне розв’язування задачі. Змінні x4, x5 , які не входять до бази, дорівнюємо нулю і отримуваємо результат: (x1 = 35; x2 = 30; x3 = 10; x4 = 0; x5 = 0;), максимальне значення функції дорівнює 710. Подставляємо значення x1 = 35 і x2 = 30 до цільової функції і отримуваємо:
F = 10x1 + 12 x2 = 10*35 + 12*30 = 350 + 360 = 710 Це визначає, що рішення вірно. Приклад 2. На двох складах зберегається 12т. та 15т. товару який треба перевезти до трьох крамниць (до 1-й крамниці – 8т., до 2-й крамниці – 10т., до 3-й крамниці – 9 т.). Необхідно скласти оптимальний план перевезень якщо вартість перевезення в у.о. 1т. товару зі складів до крамниць наведено в таблиці: Таблиця 1.5.5
Ця задача наведена в прикладі 2 розділа 1.2 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти минимальне значення цільової функції:
F(x) = 30 x1 + 46 x2 +32 x3 + 20 x4 + 53 x5 + 40 x6 ® min З обмеженнями x1 + x2 + x3= 12 x4 + x5 + x6= 15 x1 + x4 = 8 x2 + x5 = 10 x3 + x6 = 9 xi³ 0i = 1,2,…,6
У даному випадку задача лінійного програмування вже має канонічний вид. Треба будувати симлекс таблицю, але спочатку необхідно визначити базіс. За методом Гауса виконуємо наступні перетворення, щоб визначити базові змінні. З першого рівняння x1= 12 - x3 - x2. Підставляємо значення x1 до третього рівняння, та виводимо x1 до бази. З четвертого рівняння x2= 10 - x5. Підставляємо значення x2 до першого і третього рівняння, та виводимо x2 до бази. З п’ятого рівняння x3= 9 - x6. Підставляємо значення x3 до першого і третього рівняння, та виводимо x3 до бази. Після ціх перетворень маємо наступні обмеження
x1 - x5 - x6= -7 x4 + x5 + x6= 15 x4 + x5 + x6= 15 x2 + x5 = 10 x3 + x6 = 9 xi³ 0i = 1,2,…,6 Друге рівняння тотожно третьому, тому його можна виключити. Для моделі будуємо симплексну таблицю Таблиця 1.5.6
В таблиці немає в останій строці коефіцієнтів, які мають відємне значення, тому подальша оптимізація за допомогою симплекс перетворень не можлива. Для пошуку остаточного рішення треба змінні, які не є базовими дорівняти 0. Якщо за першим рівнянням одночасно x5 та x6 дорівняти 0, то x1 буде мати відємне значення, а це суперечить умовам. Для подальшого пошуку рішення треба застосовувати інши логічно математичні перетворення, за результатами яких остаточне рішення (0;3; 9; 8; 7; 0), а значення цільової функції F(x) = 30*0 + 46*3 +32*9 + 20*8 + 53*7 + 40*0 = 957. Остаточне рішення має вигляд: Таблиця 1.5.7
У даному прикладі наведено рішення транспортної задачі симплекс методом. Використання цього методу для вирішення транспортних задач не є ефективним. Для розв’язування транспортних задач більш ефективними є спеціальні методи, які будуть наведени при розгляді транспортних задач.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.014 сек.) |