• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Приклад використання симплекс-методу.

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

; ; .

Згідно з заданою умовою цільова функція (1) має вигляд:

(1)

(1)

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

				…
…

В даному випадку n=5 (кількість змінних). Необхідно виразити базисні змінні через вільні. Для цього запишемо систему обмежень:

(2)

Отже, система обмежень набуває вигляду:

(2)

Де - базисні змінні. - вільні змінні.

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

Отримано всі дані для заповнення симплексної таблиці:

Таблиця1

		3	-5	6/3=2
	-6	-1	-3
				36/12=3

Базисний план не являється оптимальним. Значення функції .

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

1) якщо всі вільні члени (не враховуючи рядочка ) в симплексній таблиці невід’ємні, а в рядочку (не враховуючи вільного члена) немає жодного додатного елемента, то оптимальне рішення досягнуте;

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

3) якщо ж в стовпчику з додатнім коефіцієнтом цільової функції є додатні елементи, то потрібно зробити заміну однієї з вільних змінних на одну з базисних;

4) обирається вирішальний стовпчик , такий, що , якщо таких елементів декілька, обирається найбільший;

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

6) обчислюються відношення , ;

7) в якості вирішального елементу обирається коефіцієнт , для якого попередньо обчислене відношення мінімальне:

.

Таким чином вирішальний елемент . Вирішальним рядочком буде рядок з елементом . Тому необхідно зробити заміну базисних змінних , .

Формуємо другу симплексну таблицю за формулами:

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

Таблиця 2

	-8	-7/3	47/3
		1/3	-5/3
	-4	1/3	-14/3
		-4

Базисний план . Значення функції

Знайдене рішення не оптимальне, тому необхідно продовжувати обчислення.

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