Симплексний метод вирішення задач лінійного програмування
Назва роботи: Симплексний метод вирішення задач лінійного програмування
Предметна область: Математика та математичний аналіз
Опис: Запишемо систему рівнянь 5 у векторній формі: 6 де Aj B вектор a елемент матриці 1. Таким чином, нульові значення змінних задовольняють6 Вектори Аjj=n1nmможе служити базисом в mмерном просторі. Будь-який небазовий вектор можна розкласти за векторами базису. Розкладемо якийсь небазисний вектор Ak по векторах базису: Помножимо 8 на позитивну константу і віднімемо 8 з 7 довільна величина її можна вибрати настільки малою що незалежно від значення вираз у дужках буде завжди більше нуля так як 0.
Дата завантаження: 2013-07-31
Розмір файлу: 102.5 KB
Роботу завантажили: 7 чол.
Симплексний метод розв'язання задач лінійного програмування.
Симплексний метод або метод послідовного покращення плану дозволяє відомому базисному рішенню побудувати інше базисне рішення, для якого значення лінійної формули R & gt; ніж для вихідного. Запишемо систему рівнянь 5 у векторній формі:
де Aj, B вектор
a - елемент матриці
1. Припустимо, що відомо якесь базисне рішення, в якому m - змінних відмінних від 0. . Отже нульові значення змінних задовольняють(6) Вектори А j ( j = n +1,…, n + m )може бути базисом в m -мірному просторі. Будь-який небазовий вектор можна розкласти за векторами базису.
2. Розкладемо якийсь небазовий вектор A k за векторами базису:
Помножимо (8) на позитивну константу і віднімемо (8) з (7)
- довільна величина її можна вибрати настільки малою, що незалежно від значення вираз у дужках буде завжди більший за нуль так як >0 (за визначенням) позначимо: Для вектора A k : y k=. При =0 матимемо вихідне базисне рішення. Для отримання іншого базового рішення необхідно взяти. якщо коефіцієнти вектора Ак - негативні, то отримати нове базисне рішення неможливо. І тут потрібно взяти інший небазисний вектор і розкласти його за векторами базису. Якщо і його коефіцієнти будуть меншими за нуль, то слід розкладати наступний небазисний вектор до тих пір, поки не отримаємо розкладання, в якому хоча б одна змінна буде позитивною.
3. Нехай не всі коефіцієнти вектора А до негативні отже при безперервному зростанні, починаючи від 0, першою звернутися до 0 та змінна (), для n-ої
Ставлення буде мінімальним і це ставлення потрібно приймати за:
4. Припустимо, що мінімальне значення виходить при l = 1 тобто для першого з послідовності змінних: n +1, …. n + m , тобто = отже при даному значення (з (10)) дорівнюватиме 0 Інші ж значення будуть 0 для всіх j = n +2, ..., n + m . y n =. Замість вихідного базисного рішення отримаємо нове рішення:
За підсумками нового базисного рішення рівняння(9) запишеться як. Порівнюючи (11) з (7) приходимо до висновку що у вихідному базисі векторів A j (j = n +1. n + m). один з них А n +1 замінимо на вектор А k і нове базисне рішення задовольняє рівняння (11) Однак, досі не ясно, як змінюється значення критерію при переході до базисного рішення. Підставимо у вираз критерію вихідне базисне рішення отже При новому базисному рішенні: збільшення
Якщо >0 при переході до нового базисного рішення, цей перехід доцільний. У результаті в базисі вводитися небазисний вектор і утворюється новий базис, яким можна розкласти наступний небазисний вектор і якщо знову отримаємо >0, то будуємо новий базис і по ньомурозкладаємо наступний небазовий вектор і т.д. доки заміна базисних векторів небазесними призводить до підвищення критерію. З (12) випливає, що 0 завжди коли і тому рішення про перехід до нового базису можна перевірити до визначення при відомих коефіцієнтах розкладання вектора A k .