Решение завдань лінійного программирования

ЛАБОРАТОРНА РОБОТА № 11.

РІШЕННЯ ЗАВДАНЬ ЛІНІЙНОГО ПРОГРАММИРОВАНИЯ.

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

ТЕОРЕТИЧНІ ОСНОВЫ Стандартная завдання лінійного програмування складається з трьох часток: цільової функції (на максимум чи мінімум) — формула (1.1), основних oграничений [pic] - формула (1.2), обмежень не заперечності змінних (є, немає) — формула (1.3).

(1.1).

[pic] і = 1,… m.

(1.2).

[pic].

(1.3).

Алгоритм вирішення завдань лінійного програмування вимагає приведення їх постановки в канонічний вид, коли цільова функція прагне максимуму (якщо поривалася мінімуму, то функцію треба помножити на -1, на стане йти до максимуму), основні обмеження мають вигляд рівності (для приведення до равенствам у разі знака [pic] треба праву частина каждогo такого k-го нерівності додати штучну зміну uk [pic], а разі знака [pic], uk [pic] треба відібрати їх із правій частині основних обмежень), присутні обмеження не заперечності змінних (якщо їх майже немає для певної перемінної хk, їх можна запровадити шляхом заміни всіх входжень цієї перемінної комбінацією x1k — х2k = хk, де х1k [pic] і х2k [pic]). При цьому виконання завдання лінійного програмування необхідно мати базис, тобто. набір змінних хi, у кількості, рівним числу основних обмежень, причому щоб кожна з цих змінних була лише щодо одного основному oграничении й мала свій множник аij = 1. Якщо таких змінних немає, то вони штучно додаються в основні обмеження й отримують індекси хm+1, xm+2 тощо. Вважається у своїй, що вони задовольняють умовам не заперечності змінних. Зауважимо, що й базисні перемінні (все) утворюються у результаті приведення завдання до канонічного виду, то цільова функція завдання залишається не змінювалась, і якщо перемінні додаються штучно до основним обмеженням, у яких вид рівностей, те з цільової функції віднімається їх сума, помножена на М, тобто. [pic] (так званий модифікований симплекс-метод). Ми не розглядати завдання, які стосуються модифікованого симплекс-методу. Для практичної рабо-ты по віднайденню виконання завдання лінійного програмування (за спрощеним варіантом простого симплекс-метода) використовуватимуться алгоритм итерационного (многошагового) процесу знаходження рішення і двоє типу оперативних оце-нок, дозволяють робити переходи від однієї кроку до іншого, і навіть показивающих, коли итерационный процес зупиниться і результати буде знайдено. Перша оцінка — це дельта-оценка, для перемінної хj вона не має вид:

[pic].

(1.4) Тут вираз і [pic] B означає, що на посаді коефіцієнтів цільової функ-ции, які у сумі висловлювання (1.4), використовуються коефіцієнти змінних, які входять у базис цьому кроці итерационного процесу. Переменными аij є множники матриці коефіцієнтів При основних ограничениях, розраховані даному кроці итерационного процесу. Дельтаоцінки розраховуються за всі змінним хi, наявних у завданню. Слід відзначити; що дельта-оценки базисних змінних рівні нулю. Після нахождения дельта-оценок їх вибирається найбільша по модулю негативна оцінка, змінна хk, їй відповідна, вводитимуть у базис. Інший важливою оцінкою є тетта-оценка, має вид:

[pic].

(1.5).

Т.е. за двозначним номером k, знайденому по дельта-оценке, ми маємо вихід на переменную хk і елементи шпальти ХB ділимо на відповідні (лише поклади тільні) елементи шпальти матриці А, відповідного зміною xk. З отриманих результатів вибираємо мінімальний, він буде тетта-оценкой, аi-й елемент шпальти B, лежить у однієї рядку з тетта-оценкой, буде выводиться з базису, замінюючись елементом xk, отриманим по дельта-оценке. Для здійснення такого заміни у i-ой рядку k — гo шпальти матриці А сделать одиницю, а інших елементах k-го шпальти зробити нулі. Таке преоб-разование і буде одним кроком итерационного процесу. Для здійснення такого перетворення використовується метод Гаусса. У відповідність до ним i-я рядок всієї матриці А, і навіть i-я координата ХB діляться на aik (отримуємо одиницю в i-ой рядку який вводимо в базис елемента). Потім вся i-я рядок (якщо і не одиниця), і навіть i-я координата ХB множаться на елемент (-а1k). Після цього виробляється поэлементное підсумовування чисел у шпальтах 1-ой і i-ой рядків, сумуються також ХB1, і (-а1k)*ХBi;. Аналогічні дії виробляються для решти рядків крім i-ой (базисної) рядки. У результаті виходить, що у i-ой рядку k-го елемента коштує, тоді як у всіх ос-тальных його рядках перебуває 0. Отже здійснюється крок итерационального алгоритму, Кроки алгоритму симплекс-метода тривають до того часу, поки що не отримано одне із наступних результатов.

• Усі небазисные дельта-оценки більше нуля — знайдено вирішення завдання чинейного програмування, він з себе вектор компонент x;, значення яких рівні нулю, або рівні елементам шпальти Х, та-в киє компоненти стоять на базисних місцях (скажімо, якщо базис утворюють перемінні х2, x4, х5, то ненульові компоненти перебувають у векторі рішення задучи лінійного програмування на 2-му, 4-му і 5-му місцях). • Є небазисные дельта-оценки, рівні нулю, тоді роблять висновок у тому, що завдання лінійного програмування має незліченну кількість рішень (уявлюване променем чи відрізком). Докладно розглядати випадки подібного типу, і навіть розбіжності між рішеннями як променя і відрізка не будемо. • Можливий варіант отримання шпальти негативних елементів на отрицательной розрахованої дельта-оценке, такій ситуації не можна обчислити тетта-оценки. І тут роблять висновок, що систему обмежень завдання лінійного програмування несовместна; отже, завдання лінійного програмування немає рішення. Рішення завдання лінійного програмування, коли вона єдине, слід нотувати у вигляді Х* = (…, …, …) — вектора рішення і значення цільової функ-ции у точці рішення L*(Х*). За інших випадках (рішень багато або їх отсут-ствуют) слід словесно описати отриману ситуацію. Якщо рішення завдання лінійного програмування нічого очікувати отримано протягом 10−12 ітерацій симплекс-метода, слід написати, що ухвалено рішення немає у в зв’язку зі неог-рачниченностью функції цели.

Для практичного розв’язання завдання лінійного програмування симплексметодом зручно користуватися таблицею виду (табл. 11.1):

Таблиця 1.1.

|B |CB |XB |A1 |… |An |? | |Базисні |Цільові |Праві | | | | | |компоненти |Коэффиц. |Частини | | | | | | |Базису |обмежений | | | | | |? | | |?1 | |?n | |.

Задание Необходимо вирішити завдання лінійного программирования.

L (x) = x1 — 2×2 + 3×3 [pic] x1 — 3×2 [pic] 3 2×1 — x2 + x3 [pic] 3 -x1 + 2×2 — 5×3 [pic] 3 Усі xi [pic] 0 і = 1, …3.

1. Спочатку наведемо завдання до канонічного виду:

L (x) = x1 — 2×2 + 3×3 [pic] x1 — 3×2 + x4 = 3 2×1 — x2 + x3 + x5 = 3 -x1 + 2×2 — 5×3 + x6 = 3 Усі xi [pic] 0 і = 1, …6.

2. Складаємо таблицю симплекс-метода (табл. 1.2). Очевидно, що базис утворюють компаненты x4, x5, x6:

|B |CB |XB |A1 |A2 |A3 |A4 |A5 |A6 |? | |A4 |0 |3 |1 |-3 |0 |1 |0 |0 |- | |A5 |0 |3 |2 |-1 |1 |0 |1 |0 |3 | |A6 |0 |3 |-1 |2 |-5 |0 |0 |1 |- | |? | | |-1 |2 |-3 |0 |0 |0 | | |A4 |0 |3 |1 |-3 |0 |1 |0 |0 | | |A3 |3 |3 |2 |-1 |1 |0 |1 |0 | | |A6 |0 |3 |-1 |2 |0 |0 |0 |1 | | |? | |9 |5 |2 |0 |0 |3 |0 | |.

Таким чином, на другому кроці розрахунків (обчислень дельта-оценок) отримано, що це небазисные дельта оцінки позитивні, що СРСР розвалився, що це завдання має єдине решение:

3. Рішення завдання запишемо в виде:

X* = (0, 0, 3, 3, 0, 3), L*(X*) = 9.

———————————- [pic].

[pic].

Міністерство загального характеру і професійного образования.

Російської Федерации.

Воронезький Державний Архітектурно — Строительный.

Университет.

Кафедра Економіки та управління строительством.

ЛАБОРАТОРНА РАБОТА.

На тему: «Рішення завдань лінійного программирования».

| |Виконав: | | |Студент 4 курсу | | |ФЗО ЭУС | | |Сидоров В.В. | | | | | |Керівник: | | |Богданов Д. А. |.

Воронеж — 2002 г.