Київський національний економічний університет імені Вадима Гетьмана

Реферат з дисципліни «Прикладне моделювання» на тему:

«Симплекс-алгоритм для розв’язання задачі лінійного програмування»

Перевірив: Коляда Ю. В.

________________________________

Виконала:

Студентка 2 курсу

Очної форми навчання

Факультету економіки та управління

Спеціальності «Економіка підприємства»

Групи ЕП-203

Горбунова Юлія В’ячеславівна

Київ 2021

Зміст

1.Теоретична частина……………………………………………………………..2

1.1 Обґрунтування та опис обчислювальної процедури. Приведення задачі лінійного програмування до стандартної форми……………………………….2

1.2 Симплексний метод розв'язання задач………………………………………2

1.3 Алгоритм симплекс-метода……………………….………………………….4

2. Практична частина……………………………………………………………..6

2.1 Приклад 1………………………………………………………………………6

2.2 Приклад 2………………………………………………………………………8

1. Теоретична частина.

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

Будь-яка задача лінійного програмування наводиться до стандартної (канонічної) форми основної задачі лінійного програмування, яка формулюється наступним чином: знайти невід'ємні значення змінних X1, X2, Xn, що задовольняють обмежень у вигляді рівностей:

A11X1 + A12X2 +… + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

……………………………………

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ≥ 0, j =1,…, n

і звертають у максимум лінійну функцію цих змінних:

E = C1X1 + C2X2 + … + CnXn -> макс

У цьому потрібно, щоб праві частини рівностей були невід’ємні, тобто. повинні дотримуватися умов:

Bj ≥ 0, j=1,…,n

Приведення до стандартної форми необхідно, оскільки більшість методів розв'язання задач лінійного програмування розроблено саме для стандартної форми. Для приведення до стандартної форми завдання лінійного програмування може знадобитися виконати такі дії:

• перейти від мінімізації цільової функції до її максимізації;

• змінити знаки правих частин обмежень;

• перейти від обмежень-нерівностей до рівностей;

• Позбутися змінних, які мають обмежень на знак.

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

1.2 Симплексний метод розв'язання задач.

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

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

ѓ = C0 + C1x1 + C2x2 + ... + Cnxn

та система m лінійних рівнянь із n невідомими. Це називається системою обмежень:

a11x1 + a12x2 + ... + a1nxn = b1

a21x1 + a12x2 +...+ a2nxn = b2

...

am1x1 +am2x12 +...+ amnxn = bm

Цільову функцію представимо у вигляді:

ѓ - C1x1-C2x2 -...- Cnxn = C0

Складемо симплекс-таблицю. Надалі будемо вважати, що ранг матриці системи обмежень дорівнює r.

У цьому випадку система обмежень матиме вигляд:

x1 +...+ a1,r+1xr+1 +...+ a1nxn = b1

x2 + a2,r+1xr+1 +...+ a2nxn = b2

...

xr+ ar,r+1xr+1 +...+ arnxn = br

Тоді цільова функція має вигляд:

ѓ + Cr+1xr+1 + Cr+2xr+2 -...- Cnxn = C0

Знаходження оптимального плану симплексним методом включає такі етапи:

1. Знаходять опорний план.

2. Складають симплекс-таблицю. Загалом:

Таблиця 1

Базисні невідомі	Вільні члени	x1	x2	xr	xr+1	xj	xn
x1	b1	1	0	0	a1,r+1	a1j	a1n
x2	b2	0	1	0	a2,r+1	a2j	a2n
xi	bi	0	0	0	ai,r+1	aij	ain
xr	br	0	0	1	ar,r+1	arj	arn
ѓ	C0	0	0	0	Cr+2	Cj	Cn

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

4. Нехай елемент Сj<0, тоді в j-му стовпці необхідно знайти позитивний елемент. Якщо всі коефіцієнти цього шпальти негативні, то рішення немає.

5. Якщо позитивний коефіцієнт в j-му стовпці один, то вибраний рядок з номером i треба поділити всі коефіцієнти на число aij. Результат поділу записуємо в нову симплекс-таблицю. Якщо ж позитивних коефіцієнтів кілька, необхідно скласти відношення bi/aij і з отриманих значень вибрати найменше, що відповідає i-му рядку.

6. У новій симплекс-таблиці у стовпці базисних невідомих замість xi пишеться xj. Триває заповнення таблиці. У стовпці з номером j необхідно отримати нулі (включаючи рядок із цільовою функцією). Для цього треба помножити i-й записаний рядок на потрібне число і скласти з рештою рядків.

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