Алгоритм симплексного методу.

1. Вибираємо базисні перемінні: ,…, . Нульове базисне рішення має вид: ; базисні вектори: ,…, .

2. Знайдемо розкладання векторів обраному по базисі й обчислимо значення оцінок .

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

, де , .

Нехай , тоді вектор вводиться в базис. Виводиться буде вектор , для який справедливо:

Елемент називається розв'язний, а рядок та стовпець - напрямними.

Новий базис: .

Відповідні базисні перемінні:

.

4. Знайдемо координати розкладання векторів по новому базисі і нове базисне рішення.

Нове базисне рішення визначається по формулах:

Розкладання векторів обчислюється в такий спосіб:

Щоб знайти розкладання векторів по новому базисі треба розділити направляючий рядок на розв'язний елемент і зробити повне виключення по методу Жордана-Гауса в направляючому стовпці.

 

 

cn	An	x1, n x2, n x r, n x m, n	zn – cn
…	…
ck	Ak	x1, k x2, k x r, k xm, k	zk – ck
…	…
cm+1	Am+1	x1,m+1 x2,m+1 xr,m+1 xm,m+1	zm+1– cm+1
cm	Am
…	…
cr	Ar
…	…
c2	A2
c1	A1
	X^Б	x1 x2 xr xm	z0
	C^Б	c1 c2 c r cm
	A^Б	A1 A2 A r Am
i		r m	m+1

 

 

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

Зауваження: Якщо зважується задача максимізації цільової функції, то функція мети записується у виді:

.

Для неї зважується задача мінімізації. Хай – оптимально (точка мінімуму цільової функції ), тоді для вихідної задачі - точка максимуму цільової функції .

Приклад 7.2.

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

Потрібно максимізувати цільову функцію.

при обмеженнях:

 

Тому що симплексний метод вирішує задачу мінімізації, то функцію мети розглянемо у виді:

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

 

, , , .

 

Базисні перемінні: _, ;

Вільні перемінні: _, ;

 

Базисні вектори: , ;

Нульове базисне рішення: ;

Функція мети:

Складемо вихідну симплекс - таблицю:

Таблиця 7.1

I				-2	-4

 

Значення функції мети для нульового базисного рішення:

;

Вичислимо значення відміток:

Дві оцінки позитивні. Знайдемо відповідні значення :

Знайдемо

Максимальне значення відповідає вектору . Для другого стовпця відповідає другому рядку.

Другий рядок і другий стовпець є напрямними.

Значить елемент – розв'язний. Отже вектор вводиться в базис, а – виводиться з базису.

Обчислюємо новий опорний план і розкладання векторів по новому базисі , . Для цього другий рядок поділяється на (розв'язний елемент). Результат записується в другий рядок таблиці7.2. Потім виробляється виключення в другому стовпці. Для цього отриманий другий рядок збільшується на (-4) і поелементно складається з першим рядком.

Друга симплекс-таблиця має вигляд:

Таблиця 7.2

I				-2	-4
				1,4			-0,8
		-4		0,4			0,2
	0,4			-0,8

Базисні перемінні , ;

Вільні перемінні: _, ;

Базисні вектори , ;

Перше базисне рішення:

Значення функції мети: (зменшилося).

Обчислимо значення оцінок:

Позитивна оцінка одна, отже вводиться в базис.

Знаходимо ;

Отже буде виведений з базису.

Розв'язний елемент -

Поділяємо перший рядок на розв'язний елемент і робимо виключення в першому стовпці. Одержуємо нову симплексну таблицю:

Таблиця 7.3

I				-2	-4
		-2				5/7	-4/7
		-4				-2/7	3/7
			-2/7	-4/7

Базисні перемінні: , _.

Базисні вектори: , .

Обчислимо значення оцінок:

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

Значення цільової функції: ($) – є максимальним.

Відповідь: виробів моделі А – 300 од.

виробів моделі В – 200 од.

максимальний прибуток

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

 

1) Яка постановка задачі?

2) Як реалізується геометричний метод?

3) Як приводиться система обмежень до стандартного виду?

4) Як будується базисне рішення?

5) Який критерій оптимальності?

6) Який алгоритм симплексного методу?

Використовувана література

1) [4] стор. 37-53

 

СПИСОК ЛІТЕРАТУРИ

 

1) Волков Е.А. Чисельні методи. - М. Наука, 1987.

2) Воробйова Г.Н., Данилова А.Н. Практикум по обчислювальній математиці.- М. Вища школа, 1990.

3) Дмитрієнко Г.Н. Методичні вказівки контрольній роботі, типовому розрахунку і лабораторним роботам по темі "Чисельні методи" - Сєвєродонецьк, 2000.

4) Дмитрієнко Г.Н., Дмитрієнко В.Т. Методичні вказівки за курсом "Чисельні методи" (методи оптимізації).- Сєвєродонецьк, 2000.

5) Дмитрієнко Г.Н. Методичні вказівки до виконання розрахункового завдання по темі "Наближені методи рішення алгебраїчних і трансцендентних рівнянь".- Сєвєродонецьк, 2000.

6) Дмитрієнко В.Т., Дмитрієнко Г.Н., Нагулин Н.И.. Методичні вказівки за курсом "Прикладна математика" і "Вища математика" (рівняння математичної фізики).- Харків, 1992

 

 

Навчальне видання

ЛЕКЦІЇ