74559

СИМПЛЕКСНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Лекция

Информатика, кибернетика и программирование

Розв’язування задачі лінійного програмування симплексним методом. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків.

Украинкский

2015-01-04

278 KB

5 чел.

  1.  СИМПЛЕКСНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ ЗАДАЧ лінійного програмування

Анотація

Початковий опорний план. Перехід від одного опорного плану до іншого. Оптимальний розв’язок. Критерій оптимальності плану. Розв’язування задачі лінійного програмування симплексним методом. Метод штучного базису.

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів . Отже, загальна кількість опорних планів визначається кількістю комбінацій . Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом так званий симплексний метод, або симплекс-метод. 

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

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

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

4.1 Початковий опорний план

Розглянемо задачу лінійного програмування, записану в канонічній формі:

.

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

 (4.1)

 (4.2)

 (4.3)

Система обмежень (4.2) у векторній формі матиме вигляд:

, (4.4)

де

, ,..., ,

, …, , ,

  лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (4.4) базисними змінними будуть , а інші змінні вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори   одиничні, то отримаємо один із розв’язків системи обмежень (4.2):

 (4.5)

тобто допустимий план.

Такому плану відповідає розклад

 (4.6)

де  — лінійно незалежні вектори і за властивістю 3 розв’язків задачі лінійного програмування (п.3.4) план  є кутовою точкою багатогранника розв’язків, а отже, може бути початковим опорним планом.

4.2 Перехід від одного опорного плану до іншого

Розглянемо, як, виходячи з початкового опорного плану (4.6), перейти до наступного опорного плану, що відповідає цілеспрямованому процесу перебору кутових точок багатогранника розв’язків.

Оскільки  є базисом m-вимірного простору, то кожен з векторів співвідношення (4.5) може бути розкладений за цими векторами базису, причому у єдиний спосіб:

Розглянемо такий розклад для довільного небазисного вектора, наприклад, для :

 (4.7)

Припустимо, що у виразі (4.7) існує хоча б один додатний коефіцієнт .

Введемо деяку поки що невідому величину , помножимо на неї обидві частини рівності (4.7) і віднімемо результат з рівності (4.6). Отримаємо:

 (4.8)

Отже, вектор

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

 (4.9)

З (4.9) отримуємо, що для шуканого  має виконуватися умова . Отже, вектор  буде планом задачі для будь-якого , що задовольняє умову:

,

де мінімум знаходимо для тих i, для яких .

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

.

Підставимо значення  у вираз (4.8):

,

якщо позначити  , , то рівняння можна подати у вигляді:

,

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

.

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

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

Необхідно зазначити, що для випадку, коли вектор  підлягає включенню в базис, а в його розкладі (4.7) всі , то, очевидно, не існує такого значення , яке виключало б один з векторів. У такому разі план  містить m+1 додатних компонент, отже, система векторів  буде лінійно залежною і визначає не кутову точку багатогранника розв’язків. Функціонал не може в ній набирати максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв’язків.

4.3 Оптимальний розв’язок. Критерій оптимальності плану

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

Розглянемо задачу лінійного програмування (4.1)-(4.3).

Допустимо, що вона має опорні плани і вони є невиродженими. Розглянемо початковий опорний план виду (4.5):

Такому плану відповідає розклад за базисними векторами

 (4.10)

та значення функціонала:

 (4.11)

Кожен з векторів  можна розкласти за векторами базису, причому у єдиний спосіб:

, (4.12)

тому такому розкладу відповідатиме і єдине значення функціонала:

. (4.13)

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

, (4.14)

то план  є оптимальним розв’язком задачі лінійного програмування (4.1)-(4.3).

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

, (4.15)

то план Х0 є оптимальним розв’язком задачі лінійного програмування.

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

4.4 Розв’язування задачі лінійного програмування симплексним методом

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

Продовжимо розгляд задачі (4.1)-(4.3), опорний план якої . Для дослідження даного плану на оптимальність (за умовою оптимальності плану задачі лінійного програмування) необхідно вектори  системи обмежень (4.2) розкласти за базисними векторами  і розрахувати значення оцінок .

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

У стовпці «Базис» записані змінні, що відповідають базисним векторам, а в стовпці «Сбаз» – коефіцієнти функціонала відповідних базисних векторів. У стовпці «План» початковий опорний план , в цьому ж стовпці в результаті обчислень отримують оптимальний план. У стовпцях  записані коефіцієнти розкладу кожного j-го вектора за базисом, які відповідають у першій симплексній таблиці коефіцієнтам при змінних у системі (4.2). У (m+1)-му рядку в стовпці «План» записують значення функціонала для початкового опорного плану , а в інших стовпцях   значення оцінок . Цей рядок симплексної таблиці називають оцінковим.

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

,

де сі – коефіцієнти функціонала, що відповідають векторам базису.


Таблиця 4.1 – Перша симплексна таблиця для розв’язку задач лінійного програмування


Після заповнення табл.4.1 розраховують значення оцінок плану (останній рядок):  . Потім згідно з умовою оптимальності плану задачі лінійного програмування, якщо всі  (для задачі на максимум), то план є оптимальним. Допустимо, що одна з оцінок , тоді план  не є оптимальним і необхідно здійснити перехід до наступного опорного плану, якому буде відповідати більше значення функціонала. Якщо від’ємних оцінок кілька, то включенню до базису підлягає вектор, який вибирається як . Мінімум знаходять для тих індексів j, де . Якщо існує кілька однакових значень оцінок, що відповідають , то з відповідних їм векторів до базису включають той, якому відповідає максимальне значення функціонала.

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

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

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

.

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

Допустимо, що  відповідає вектору, що знаходиться в l-му рядку табл.4.1. Відповідний рядок симплексної таблиці називають напрямним.

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

Для визначення нового опорного плану необхідно всі вектори розкласти за векторами нового базису. Вектор Аk, який необхідно вводити до базису, в розкладі за початковим базисом має вигляд:

 (4.16)

Вектор Аl виходить з базису, і його розклад за новим базисом отримаємо з виразу (4.16):

 . (4.17)

Розклад вектора А0 за початковим базисом має вигляд:

. (4.18)

Для запису розкладу вектора в новому базисі підставимо вираз (4.17) у рівняння (4.18), маємо:

.

Отже, значення компонент наступного опорного плану розраховуються за формулами:

 (4.19)

Розклад за початковим базисом будь-якого з векторів має вигляд:

. (4.20)

Розклад за новим базисом отримаємо підстановкою (4.17)
у (4.20):

.

Новий план: , де

 (4.21)

Формули (4.19) та (4.21) є формулами повних виключень Жордана-Гаусса.

Отже, щоб отримати коефіцієнти розкладу векторів  за векторами нового базису (перехід до наступного опорного плану та створення нової симплексної табл.4.2), необхідно:

  1.  розділити всі елементи напрямного рядка на розв’язувальний елемент;
  2.  розрахувати всі інші елементи за формулами повних виключень Жордана—Гаусса (правило прямокутника).

Потім необхідно здійснити перевірку нових значень оцінкового рядка. Якщо всі Fj  сj  0, то план Х1 — оптимальний, інакше переходять до відшукання наступного опорного плану. Процес продовжують до отримання оптимального плану, чи встановлення факту відсутності розв’язку задачі.

Якщо в оцінковому рядку останньої симплексної таблиці оцінка Fj – сj 0 відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибираючи розв’язувальний елемент у зазначеному стовпчику таблиці та здійснивши один крок (одну ітерацію) симплекс-методом. У результаті отримаємо новий опорний план, якому відповідає те саме значення функціонала, що і для попереднього плану, тобто функціонал досягає максимального значення в двох точках багатогранника розв’язків, а отже, за властивістю 2 (п.3.2) розв’язків задачі лінійного програмування така задача має нескінченну множину оптимальних планів.

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


Таблиця 4.2 – Друга симплексна таблиця для відшукання опорного (оптимального) плану


4.5 Метод штучного базису (самостійна робота)

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

Розглянемо задачу лінійного програмування:

 (4.22)

 (4.23)

 (4.24)

Задача подана в канонічному вигляді і система обмежень (4.23) не містить одиничної матриці. Отримати одиничну матрицю можна, якщо до кожного рівняння в системі обмежень задачі додати одну змінну . Такі змінні називають штучними. (Не обов’язково кількість введених штучних змінних має дорівнювати m. Їх необхідно вводити лише в ті рівняння системи обмежень, які не розв’язані відносно базисних змінних.) Допустимо, що система рівнянь (4.23) не містить жодного одиничного вектора, тоді штучну змінну вводять у кожне рівняння:

 (4.25)

У результаті додавання змінних у рівняння системи (4.23) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (4.25) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві. Тоді система обмежень (4.25) набуде вигляду (4.23) (не міститиме штучних змінних), а розв’язок розширеної задачі буде розв’язком і задачі (4.22)-(4.24).

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

(У разі розв’язання задачі на відшукання мінімального значення цільової функції вводять коефіцієнти, які є досить великими числами. Цільова функція тоді має вигляд:

.

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

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

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.

Теорема 4.1. Якщо в оптимальному плані  розширеної задачі штучні змінні , то план  є оптимальним планом початкової задачі.

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

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

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

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

27068. Виды и формы бюджетной отчетности 16.13 KB
  Бюджетная отчетность предоставляется на бумажных носителях и или в виде электронного документа с представлением на электронных носителях или путем передачи по телекоммуникационным каналам связи в порядке установленном главным распорядителем бюджетных средств главным администратором доходов бюджета главным администратором источников финансирования дефицита бюджета финансовым органом органом казначейства и органом осуществляющим кассовое обслуживание с обязательным обеспечением защиты информации в соответствии с законодательством...
27069. Синтетический учет материальных запасов 16.14 KB
  Приобретение материальных запасов по фактической сформированной стоимости отражается по дебету соответствующих счетов аналитического учета счета 010500000 Материальные запасы 010531340 010536340 и кредиту счетов 030234730 Уменьшение кредиторской задолженности по приобретению материальных запасов 020834660 Уменьшение дебиторской задолженности подотчетных лиц по приобретению материальных запасов . Безвозмездное получение материальных запасов в том числе по централизованному снабжению распоряжению извещению отражается по дебету...
27070. Документальное оформление, порядок ведения и отражения в учете кассовых операций 16.09 KB
  Для учета кассовых операций применяются приходный кассовый ордер – форма № КО1 расходный кассовый ордер – форма КО2 журнал регистрации приходных и расходных кассовых документов форма КО3 кассовая книга форма КО4 книга учета принятых и выданных кассиром денежных средств форма КО5. Все операции по поступлению и расходованию денежных средств кассир записывает в кассовую книгу которая должна быть пронумерована прошнурована и опечатана сургучной печатью. В дебет его записывают поступление денежных средств в кассу а в кредит выбытие...
27071. Инвентаризация материальных запасов 15.97 KB
  Инвентаризация материальных запасов Методические указания по инвентаризации имущества и финансовых обязательств от 13 июня 1995 г . Инвентаризационной комиссией в описях заполняются данные о фактическом наличии товарноматериальных ценностей. Результаты проведенной инвентаризации материальных запасов отражают в инвентаризационной описи сличительной ведомости по объектам нефинансовых активов ф. При хранении материальных запасов в разных изолированных помещениях у одного материально ответственного лица инвентаризация проводится...
27072. Учет прочих доходов и расходов. Назначение счета «Прочие доходы и расходы» и его структура. Организация аналитического учета для формирования отчета «О прибылях и убытках» 23.5 KB
  Назначение счета Прочие доходы и расходы и его структура. Доходы и расходы организации формирующие финансовый результат ее деятельности В соответствии с Положением по бухгалтерскому учету Доходы организации ПБУ 9 99 введено в действие с 1 января 2000 г. Прочие поступления зачисляются на счет 91 Прочие доходы и расходы Прочими доходами признаются в учете: штрафы пени неустойки за нарушения условий договоров возмещения причиненных организации убытков – в отчетном периоде в котором судом вынесено решение об их взыскании или они...
27073. Архитектура SCM-систем 174.21 KB
  Объяснить что такое ERP Что такое архитектура Как архитектура относится к классу данной системы ИСТОРИЯ В начале 60х в США начались работы по автоматизации управления запасами. В результате активного роста крупносерийного и массового производства товаров народного потребления и торговли после Второй мировой войны стало очевидно что использование математических моделей планирования спроса и управления запасами ведет к существенной экономии средств замороженных в виде запасов и незавершенного производства. Управление складами в современных...
27074. Информация в бизнесе. Инф поддержка в бизнесе. Класс-ция корпоративных информационных систем 711.94 KB
  Что такое бизнес Бизнес – это экономическая деятельность направленная на систематическое получение прибыли от производства и или продажи товаров оказания услуг. Тк бизнесэто коммерческиориентировнная деятельность в конкурентной среде. Деятельность предприятия происходит в реальном физическом мире в котором протекают преимущественно энергетические процессы. Деятельность связанная с управлением предприятием анализ ситуаций выбор вариантов и иная интеллектуальная деятельность продуктом которой являются оценки и принятие решений...
27075. Системы электронного документооборота 139.67 KB
  Системы электронного документооборота 1. Что такое документооборот Документооборо́т это частный способ информационной системы обеспечивающее взаимодействие. Системы электронного документооборота обладают рядом преимуществ к числу которых можно отнести возможность однократной регистрации электронного документа параллельное выполнение необходимых операций с отслеживанием ответственного за их исполнение а также наличие эффективно организованной системы поиска документа и развитой системы отчетности. Электронный документооборот является...
27076. Стр-ра КИС. Основные функциональные задачи 921.26 KB
  Главной задачей такой системы является информационная поддержка производственных административных и управленческих процессов бизнеспроцессов формирующих продукцию или услуги предприятия то есть необходимо рассмотрение всех бизнеспроцессов и как следствие поддержка основных бизнеспроцессов. Технологическая стрра инф системы. 3уровневая архитектура: 1 подсистемы сбора хр накопления данных В каком виде может существовать Распределенные системы данных; БДболее жестко поддерживают структуру; КорпХДболее абстрагированная...