На головну

Визначення провідних шпальти і рядки

  1. B. Визначення прибутковості ОФЗ-ПК і ОГСЗ.
  2. II. Поняття частоти випадкової події. Статистичне визначення ймовірності.
  3. II. Сортування списку по стовпцях
  4. II.1.1. Визначення теоретичних і практичних завдань психології та педагогіки
  5. IV. ШВИДКА СИГНАЛИЗАЦИЯ І ТОЧНЕ ВИЗНАЧЕННЯ МІСЦЯ АВАРІЇ
  6. V. Визначення ймовірності і непевного простору.
  7. VI. Найпростіше «визначення», його призначення і структура

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

Потім елементи стовпця вільних членів симплексной таблиці ділимо на елементи того ж знака (+/+; -/ _) Ведучого шпальти.

Результати заносимо в окремий стовпець ?i, Які будуть завжди позитивні.

Рядок симплексной таблиці, що відповідає мінімальному значенню ?i є провідною.

Вона визначає змінну xi яка вийде з базису і стане вільною.

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

Побудова нового опорного плану.

Перехід до нового плану здійснюється в результаті перерахунку симплексной таблиці методом Жордана - Гаусса.

Спочатку замінимо змінні в базисі, тобто замість xi в базис увійде змінна хj відпо-ціалу ведучому стовпцю.

Розділимо всі елементи провідного рядка попередньої симплексной таблиці на розв'язний елемент і результати розподілу занесемо в рядок наступної симплексной таблиці, відповідну введеної в базис змінної xj.

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

Інші елементи нового плану знаходяться за правилом прямокутника:

А ? В

НЕ = СТЕ - ---

РЕ

де СТЕ - Елемент старого плану,

РЕ - Дозволяє елемент,

А,В -елементи старого плану, що утворюють прямокутник з елементами СТЕи РЕ

далі повертаємося до другого етапу - перевірці плану на оптимальність.

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

Якщо в провідному стовпці всі коефіцієнти aij ? 0, то функція мети F ( ) не обмежена на безлічі допустимих планів, тобто F ( ) > ? і завдання не має рішення.

Якщо в стовпці ?i симплексной таблиці містяться два або кілька однакових найменших значення, то новий опорний план будевиродженим (Одна або кілька базисних змінних стануть рівними нулю).

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

Елементи рядків, які мають однакові найменші значення ?i діляться на передбачувані дозволяють елементи, а результати заносяться в додаткові рядки.

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

Наприклад, таблиця, яка містить три рівних значення

?i = 2, має вигляд:

 план  базисні змінні  Значення базисних змінних xl x2 x3 x4 x5 х6 x7  ?i
 II х4  4/2 = 2
х5  8/4 = 2
х6  -1  10/5 = 2

Припустимо, що дозволяє стовпцем є x1, який вводиться в новий план, тоді дозволяє елементом може бути: 2,4 або 5. За вказаною правилу, вийде таблиця:

 Значення базисних змінних х1 x2 x3 х4 х5 x6 x7
 1,5  0,5
 0,25  0,25
 2,4  -0,2  0,2  0,2

Порівнюємо послідовно зліва направо отримані приватні за стовпцями.

У першому і другому стовпцях всі приватні однакові, а в третьому стовпці найменше приватне 1,5 в першому рядку.

Отже, цей рядок і буде роздільної з дозволяє елементом 2.

Якщо в оптимальний план увійшла додаткова змін-ва xn +1, То при реалізації такого плану є недовикористані ресурси i-го виду в кількості, отриманому в стовпці вільних членів симплексной таблиці.

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

Вільну змінну, відповідну зазначеному стовпчику, можна внести в базис, виконавши відповід-повідні етапи алгоритму.

В результаті буде отримано другий оптимальний план з іншим набором базисних змінних.

Приклад 1. Комерційне підприємство, реалізує три групи товарів А, В и С.

Нормативи витрат ресурсів на 1 тис. руб. товарообігу, дохід від продажу товарів на 1 тис. руб. товарообігу, а також обсяг ресурсів задані в табл. 4.1.

 Види матеріально-грошових ресурсів  Норма витрат матеріально-грошових ресурсів на 1 тис.руб. товарообігу  Об'емресурсовbi
 група А  група В  група С
 Робочий час продавців, люд.-год  0,1  0,2  0,4
 Площа торгових залів, м2  0,05  0,02  0,02
 Площа складських приміщень, м2
 Дохід, тис. Руб.  max

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

Рішення. Запишемо математичну модель задачі.

визначимо вектор  = (x1, x2, x3), Який задовольняє умовам

 0,1x1 + 0,2x2 + 0,4x3 ? 1100

0,05x1 + 0,02x2 + 0,02x3 ? 120

3x1 + x2 + 2x3 ? 8000

x1? 0, x2 ? 0, x3 ?0

і забезпечує максимальне значення цільової функції

F (X) = Зx1 + 5х2 + 4х3 -> Max.

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

 0,1x1 + 0,2x2 + 0,4x3 + x4 = 1100

0,05x1 + 0,02x2 + 0,02x3 + x5= 120

3x1 + x2 + 2x3 + x6= 8000

 матриця коефіцієнтів А = (aij) цієї системи рівнянь має наступний вигляд:

 0,1 0,2 0,4 1 0 0

A = 0,05 0,02 0,02 0 1 0

3 1 2 0 0 1

вектори , , - лінійно незалежні, так як визначник, складений з компонент цих векторів, відмінний від нуля.

Отже, відповідні цим векторах змінні x4, x5, x6 є базисними і в цьому завданні визначають обсяги невикористаних ресурсів.

Вирішимо систему рівнянь щодо базисних змінних.

x4 = 1100 - (0,1x1+ 0,2x2+ 0,4x3 + x4)

x5 = 120 - (0,05x1+ 0,02x2+ 0,02x3 + x5)

x6 = 8000 - (3x1+ x2+ 2x3 + x6)

Функцію мети запишемо у вигляді рівняння:

F (X) = 0 - (Зx1 - 5х2 - 4х3).


Вважаючи, що вільні змінні x1 = 0, х2 = 0, х3 = 0, отримаємо перший опорний план 1= (0,0,0.1100,120,8000), F ( ) = О, в якому базисні змінніx4 = 1100, x5 = 120, x6 = 8000.

Отже, товари не продаються, дохід дорівнює нулю, а ресурси не використовуються.

Отриманий перший опорний план запишемо в симплексну таблиці 4.2.

 план  базисні змінні  Значення базисних змінних  Значення коефіцієнтів при змінних  ?i  
x1 x2 x3 x4 x5 x6  
 
I x4 x5 x6  0,10,05  0,20,02  0,40,02  
 індексна рядок F ( )  -3  -5  -4    
 II x2 x5 x6  0,50,042,5  -0,02  -0,1-5  
 індексна рядок F ( )  -0,5    
 III x2 x1 x6  2,25-0.51,25  6,25-2,51,25  12,5-62,5    
 індексна рядок F ( )  5,75  23,75  12,5    

Перший опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти: - 3, - 5, - 4.

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

| -5 | > {| -3 |, | -4 |}.

обчислимо значення ?i по рядках як частка від ділення bi/ai2 і вибираємо найменше:

min?i= Min (bi/ai2) = min [-1100 / 0.2; 120 / 0.02; 8000/1] = 5500

Отже, перший рядок є провідною.

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

Формуємо наступну частину симплексного таблиці.

замість змінної x4 в план II увійде змінна x2.

Рядок, відповідна змінної х2 в плані II, Отримана в результаті поділу всіх елементів рядка х2 плану I на дозволяючий елемент РЕ = 0,2.

На місці дозволяє елемента в плані II отримуємо 1.

В інших клітинах стовпця x2 плану II записуємо нулі.

Таким чином, в новому плані II заповнені рядки x2 і стовпець x2.

Всі інші елементи нового плану II, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозволяє елемент РЕ = 0,2.

У другій вершині по діагоналі знаходиться старе значення елемента, наприклад, значення цільової функції F (K1) = 0 = СЕ, Яке вказує на місце розташування нового НЕ в новому плані II.

третій елемент А = 1100 і четвертий елемент В = -5 завершують побудову прямокутника в яких бракує двох вершинах і розташовані по інший діагоналі.

Значення нового елемента в плані II знаходиться з виразу:

Елементи рядка визначаються аналогічно:

1100 · 0,02 0,1 · 0,02

120 - ----------- = 10 0,05 - ---------- = 0,04

0,2 0,2

0,4 · 0,02 0,02 · 1

0,02 - ---------- = - 0,02 0 - ---------- = - 0,1

0,2 0,2

Всі елементи, розташовані на перетині рядків і стовпців, відповідних однойменною базисним елементам, рівні 1.

Інші елементи стовпця в базисах векторів, включаючи індексний рядок, рівні 0.

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

Виконуючи послідовно всі етапи алгоритму, формулюємо план II.

На третій ітерації табл.4.2 отримуємо план III, Який є оптимальним, так як всі коефіцієнти в індексному рядку ? O.

Оптимальний план можна записати так:

 * = (250,5375,0,0,0,1875), F ( ) = 27 625 тис.руб.

Отже, необхідно продавати товарів першої групи А 250 од., А другої групи В - 5375 од.

При цьому торговельне підприємство отримує максимальний дохід в розмірі 27 625 тис.руб.

Товари групи С не реалізуються,

В оптимальному плані серед базисних змінних знаходиться додаткова змінна x6.

Це вказує на те, що ресурси третього виду (площа складських приміщень) недовикористаної на 1875 м2, Так як змінна х6 була введена в третє обмеження завдання, що характеризує собою використання складських приміщень цього ресурсу.

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

Приклад 3. Розглянемо рішення задачі ЛП з урахуванням додаткових обмежень іншого виду ?:

 0,5xн+ xв ? 3 0,5xн + xв + x1 = 3

xн+0,5xв ? 4 xн + 0,5xв + x2 = 4

-xн+ xв ? 1,5 -xн + xв + x3 = 1,5

xв ? 2 xв + x4 = 2

xв ? 0,25 xв + x5 = 0,25

xн ? 0,5 xн + x6 = 0,5

F (X) = 2xн+3xв > max F (X) = 0 - (- 2xн-3xв) > max

Заповнимо симплексну таблицю 4.4 і проведемо відповідні операції, враховуючи, що при обчисленні приватних ?i, Необхідно поділ проводити тільки з числами однакового знака.

 план  базисні змінні  Значення базисних змінних xн xв x1 x2 x3 x4 x5 x6  ?i
I х1  0,5
x2  0,5
х3  1,5  -1  1,5
x4
x5  -1/4  -1  1/4
x6  -0,5  -1 -
 F (X)  -2  -3  
 VI х3  3,5  -2  
x4 2/3 -4/ з 2/ з  
x5 11/12 4/ з -2/ з  
xн З1/ з -2/ з 4/ з  
xв l1/ з 4/ з -2/ з  
x6 25/6 -2/ з 4/ з  
 F (X)  102/ з 22/ з 2/ з  

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

 * = (31/3; 11/3; 0; 0; 3,5; 2/3; 11/12; 25/6)

Рішення завдання закінчено F (X6) = 10 2/3 тис. руб.




Побудова економіко-математичної моделі задачі | Побудова економіко-математичної моделі задачі | Побудова економіко-математичної моделі задачі | Побудова економіко-математичної моделі задачі | Вибір портфеля цінних паперів. | Побудова економіко-математичної моделі задачі | Управління портфелем активів. | Завдання про закріплення літаків за повітряними лініями. | Основні форми ЗАПИСИ ЗАВДАННЯ лінійного програмування. | ГЕОМЕТРИЧНИЙ МЕТОД |

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