Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Табличний запис ЗЛП. Алгоритм СМ для ЗЛП, представлених в симетричній формі.

Розглянемо ЗЛП, представлену в симетричній формі: знайти найбільше значення функції

(1.20)

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

(1.21)

(1.22)

Ввівши змінні з (1.21) отримаємо

(1.23)

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

(1.24)

Звідси випливає, що розв’язок

є опорним для даної задачі. Будемо покращувати його, користуючись методом повного виключення змінних (метод Жордана-Гаусса). Нагадаємо, що при цьому одночасно вирішується питання про сумісність системи обмежень та наявність у ній неістотних обмежень, тобто рівнянь, які є лінійними комбінаціями інших. Надалі систему обмежень задачі будемо вважати сумісною, а всі її рівняння – лінійно незалежними. Запишемо вихідні дані задачі в симплексну таблицю 1.2.

 

Таблиця 1.2

  x1 x2 xn
y1 a11 a12 a1n b1
y2 a21 a22 a2n b2
ym am1 am2 amn bm
f c1 c2 cn

 

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

Зауваження 1.3. Якщо в симплексній таблиці, яка містить деякий опорний план, всі елементи f–рядка (не рахуючи вільного члена) невід’ємні, то цей опорний план є оптимальним.

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

Зауваження 1.5. Якщо в f–рядку симплексної таблиці, яка містить деякий опорний план, є хоча б один від’ємний елемент, якому відповідає стовпчик недодатних елементів

то цільова функція необмежена на множині планів, тобто

Зауваження 1.6. Якщо в f–рядку симплексної таблиці, яка містить оптимальний план, є хоча б один нульовий елемент (не рахуючи вільного члена), то ЗЛП має нескінченну множину оптимальних планів.

Дамо коротку характеристику алгоритму знаходження оптимального плану.

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

Таким чином, вибираючи змінну, яка вводиться в базис, за від’ємним елементом f-рядка, ми забезпечуємо зростання функції f .

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

Визначення 1.16 Елемент, який знаходиться на перетині розв’язуючого рядка і розв’язуючого стовпця, називається розв’язуючим елементом.

Перехід до нового базису називається симплексним перетворенням. В результаті цієї операції відбувається перерозподіл ролей між двома змінними, які входять в деяку систему лінійних рівнянь: одна змінна із залежних переходить в незалежні, а друга навпаки. Відповідний коефіцієнт f–рядка стане невід’ємним. Така операція відома в алгебрі під назвою кроку перетворень Жордана-Гаусса. Досить часто її називають кроком модифікованого виключення Жордана-Гаусса.

Сформулюємо правило перерахунку елементів при переході до нового опорного плану, ближчого до оптимального:

1. Розв’язуючий елемент замінюємо на обернений до нього.

2. Елементи розв’язуючого рядка ділимо на розв’язуючий елемент.

3. Елементи розв’язуючого стовпчика діляться на розв’язуючий елемент, взятий з протилежним знаком.

4. Решта елементів знаходимо за правилом прямокутника:

,

де – розв’язуючий елемент.

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

Таблиця 1.3

  у1 у2 ym xm+1 xn
х1 b11 b12 b1m b1m+1 b1n a1
х2 b21 b22 b2m b2m+1 b2n a2
хm bm1 bm2 bmm bmm+1 bmn am
f q1 q2 qm qm+1 qn Q

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

Знову повертаємося до прикладу 1.1. Запишемо (1.11) та (1.14) у вигляді, зручному для запису у симплексну таблицю

(1.25)

(1.26)

 

 

і яка матиме вигляд:   x1 x2
y1
y2 1
y3
f –1 –2
  ­  

Візьмемо в (1.25) і (1.26) рівними нулю, одержимо . Даний розв’язок є опорним. Його можна покращити за рахунок збільшення змінної (їй відповідає найбільший за модулем від’ємний коефіцієнт в -рядку). Відповідний стовпчик буде розв’язуючим. Оскільки , то, розв’язуючим є другий рядок. Число 1, яке лежить на перетині другого рядка і другого стовпця, буде розв’язуючим елементом. Провівши для нього один крок перетворень Жордана–Гаусса, прийдемо до наступної таблиці:

  x1 у2
y1 1 –1
х2
y3 –1
f –1

 

Отриманий розв’язок: не є оптимальним, оскільки в -рядку є від’ємний елемент. Розв’язок можна покращити за рахунок збільшення змінної (їй відповідає від’ємний коефіцієнт в -рядку). Як і раніше, знаходимо Тому перший рядок розв’язуючий, а 1 – розв’язуючий елемент. Провівши один крок перетворень Жордана-Гаусса, одержимо:

 

  у1 у2
х1 –1
х2
y3 –2
f

Розв’язок є оптимальним, оскільки в -рядку відсутні від’ємні елементи.

 


Читайте також:

  1. Rete-алгоритм
  2. Алгоритм
  3. Алгоритм
  4. Алгоритм 1.
  5. Алгоритм 2
  6. Алгоритм RLE
  7. Алгоритм безпосередньої заміни
  8. Алгоритм Берлекемпа-Мессі
  9. Алгоритм відшукання оптимального плану.
  10. Алгоритм Гоморі
  11. Алгоритм Дейкстри.
  12. Алгоритм Деккера.




Переглядів: 705

<== попередня сторінка | наступна сторінка ==>
Алгоритм СМ у формі тотожних перетворень | Алгоритм СМ для ЗЛП, представлених в загальному виді

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.011 сек.