Приклад.

-24x₁+2x₃+6x₄®max

-3x₁+x₂+x₃+3x₄=4 y₁

2x₁+2x₂+x₃+x₄=6 y₂

x_{1, …,} x₄³ 0

4y₁+6y₂® min A: y₁+2y₂=0

-3y₁+2y₂³ -24 y₁+y₂ = 2

y₁+2y₂³ 0

y₁+y₂³ 2 Y = (4; -2)

На підставі теореми 2: Вирішимо дану систему рівнянь методом

(-3y₁+2y₂+24)x₁=0 підбору. Y=(4; -2)

(y₁+2y₂)x₂=0

(y₁+y₂-2)x₃=0

(3y₁+y₂-6)x₄=0

Підставивши в систему знайдені значення Y, отримаємо:

X = (0, 2, 2, 0)

Z = 4.

Доцільність використовування ПЗ:

Використовується з метою зниження розмірності задачі.

Зменшення кількості змінних.

Використовується в інших задачах (Подвійний симплекс метод).

ПОДВІЙНИЙ СИМПЛЕКС МЕТОД

Даний метод оснований на постійному поліпшенні неприпустимості рішень.

Якщо в ПРЗ симплекс методу основана на постійному поліпшенні значень ЦФ:

^k+1 _³ ^k

^{0 0}, то в ПЗ X_{базисне}: X_n Eх B; X_n £ 0.

Мета: X_n®max.

ВІДЗНАКА ПОДВІЙНОГО симплекс методу (ПСМ) від ПРЯМОГО (ПРСМ)

Вибір направляючого елементу (спочатку визначається рядок:

min(X_i0 ç X_i0 < 0), а потім стовпець: ;

Канонічна форма ПСМ повинна мати рівність та одиничний базис.

Для приведення до канонічного виду необхідно розрахувати псевдоплан. Псевдоплан – це нова модель, що містить в собі одиничний базис (сопряжённый базис) та неприпустиме опорне рішення.

Примітка: існують типові моделі, для яких псевдоплан можна записати відразу (наприклад, Задача змінно-добового планування).

Якщо в ПРСМ повинна бути хоча б одна Ітерація, то в ПСМ рішення може бути отримане відразу після перерахунку псевдоплану.

Всі останні Подвійні симплекс-перетворення аналогічні ПРСМ.

Приклад.

4x₁+3x₂+10x₃+5x₄®min 3 * 10 розмірність симплекс задачі.

3x₁+2x₂-x₃+5x₄³ 8 3 * 7 розмірність подвійної СЗ.

x₂-3x₃+6x₄³ 4

2x₁+x₃-x₄³ 0

x₁, …, x₄³ 0

необхідно привести до max та до рівностей (канонічний вигляд):

-4x₁-3x₂-10x₃-5x₄®max

3x₁+2x₂-x₃+5x₄-x₅=8 y₁

-x₂-3x₃+6x₄-x₆=4 y₂

2x₁+x₃-x₄-x₇=0 y₃

формуємо подвійну модель, щоб вибрати “сопряжённый” базис.

8y₁+4y₂®min A₀

3y₁+2y₃³ -4 A₁

2y₁-y₂³ -3 A₂

-y₁-3y₂+y₃³ -10 A₃

5y₁+6y₂-y₃³ -5 A₄

-y₁> 0 A₅

-y₂> 0 A₆

-y₃> 0 A₇

3) На підставі рядків ПЗ будуємо подвійні вектори А₀, А₁, А₂, А₃, А₄, А₅, А₆, А₇.

8 3 2 -1

А₀ = 4 А₁ = 0 А₂ = -1 А₃ = -3

0 2 0 1

5 -1 0 0

А₄ = 6 А₅ = 0 А₆ = -1 А₇ = 0

-1 0 0 -1

4) Вибір “сопряжённого” базису розміром m. Для цього необхідно:

свавільно вибрати m рівнянь (в даній задачі вибираємо рівняння (5, 6, 7), тут =(0, 0, 0));

розв’язуємо цю систему з m рівнянь;

підставляємо рішення в кожне з залишених (n-m) обмежень(в даній задачі це рівняння(2, 3, 4, 5)) та перевіряємо, чи задовольняє “сопряжённый” базис.

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

Якщо ж ні, то даний варіант не задовольняє, тому слід перейти до наступного

“сопряжённого ”базису.

Отже маємо складену симплекс таблицю:

			-4	-3	-10	-5
	Bx	A0	A1	A2	A3	A4	A5	A6	A7
	X5	-8	-3	-2		-5
	X6					-6
	X7		-2		-1
						­

A₀ = A₅X₅₀ + A₆X₆₀ + A₇X₇₀

8 = -1x₅₀ + 0x₆₀ + 0x₇₀

4 = 0x₅₀ - 1x₆₀ + 0x₇₀

0 = 0x₅₀ + 0x₆₀ – 1x₇₀

X_b = (-8; -4; 0).

Наступні розрахунки утворюються аналогічним чином.

Класифікація методів неперервного лінійного програмування

Симплекс метод використовується коли: ЦФ®max, а обмеження £ 0.

Симплекс метод (М-задача): обмеження ³ 0, = 0.

Подвійний симплекс метод без розрахунку псевдоплану,

цільова функція®min, а всі обмеження > 0 (задача змінно-добового планування).

Подвійний симплекс метод з розрахунком псевдоплану.

СПЕЦІАЛЬНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Задача призначення.

- задача про розподілення обладнання

Потрібно розподілити 5 екскаваторів між 4 кар’єрами з метою максимізації виробітки.

5 5

5 -100 7 -100 0

j = 1, M 7 8 8 -100 0

4 4 12 10 0

I = 1, N 8 7 10 11 0

10 -100 -100 14 0

X_ij ³ 0;

Для приведення задачі до закритого вигляду, необхідно ввести (додати) фіктивне обладнання.

Задача про розклад.

Для кожної пари вирішується задача призначення потоку групи в аудиторії.

Критерієм є вмісткість аудиторії, розвантаження сходів(мінімізація хвилин переходу).

C_ij-хвилини переходу; і - номер групи; j-аудиторія.

j=1, M; і=1, N;

3)Розподілення користувачем в класі ЕОМ.

Задана кількість користувачів та кількість комп’ютерів. Кожен користувач вирішує свою задачу за окремою ЕОМ. Необхідно розподілити користувачів

по критерію мінімума.

4)Транспортна задача.

A B

- вміщення матеріалів на складі;

- заявка.

С_ij - витрати

і=1, M; j=1, N;

5) Задача планування будівельного майданчика.