Властивості допоміжної задачі.

1. Допоміжна задача (4) завжди має оптимальний розв’язок.

Справді, за умови y_i ≥ 0 (i = 1, 2, …, m) завжди g ≥ 0. Отже, цільова функція цієї задачі обмежена знизу, а тому існує оптимальний розв’язок для задачі мінімізації.

1. Вектор α = (0; 0; …; 0; b₁; b₂; …; b_m) є опорним розв’язком задачі (4).

Це твердження є очевидним. Отже, приймаючи α за початковий опорний розв’язок, можна розв’язати задачу (4) симплекс – методом. Нехай β = (; ; …; ; ; ; …; ) – це оптимальний розв’язок задачі (4).

3. Якщо = = … = = 0, то γ = (; ; …; ) – це опорний розв’язок початкової задачі (3).

Справді, за цієї умови γ, по - перше, є розв’язком задачі (3). По – друге, всі основні змінні допоміжної задачі для β знаходяться серед x_j (j = 1, 2, …, n) і отже є основними змінними для γ. Тому всі вільні змінні γ дорівнюють нулю, тобто цей розв’язок є опорним.

4. Якщо серед чисел ; ; …; є додатні, то допустима множина задачі (3) є пустою.

Справді, за цієї умови оптимальне значення g > 0. Якщо ж існує бодай один допустимий розв’язок (; ; …; ) задачі (3), то, поклавши = = … = = 0, дістанемо допустимий розв’язок (; ; …; ; ; ; …; ) задачі (4), за яким g = 0.

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

f = 3х₁ + х₂ (mах)

.

Ввівши нові змінні х₃, х₄, зведемо цю модель до канонічної:

f = 3х₁ + х₂ (mах)

.

Її симплекс – таблиця виглядає так:

 

х1	х2	х3	х4	b
		-1

 

Розв’яжемо цю задачу, використовуючи метод штучного базису. Оскільки вектор умов змінної x₄ уже виглядає належним чином, то можна обмежитись додатковою змінною у₁:

g = у₁ (min) або g´ = – у₁ (mах)

.

Запишемо її у електронну симплекс – таблицю:

 

	A	B	C	D	E	F	G
	х1	х2	х3	х4	у1	b	b/aij
			-1
					– 1

 

Приведемо її до базису х₄, у₁: для цього додамо до четвертого рядка другий. Отже, виокремимо новий діапазон А6:G8, рядки 2 і 3 скопіюємо у рядки 6 і 7 відповідно, у чарунку Е8 задамо формулу =Е4 + Е2, а формули решти чарунок рядка 8 скопіюємо з неї. В результаті дістанемо:

	A	B	C	D	E	F	G
	х1	х2	х3	х4	у1	b	b/aij
			-1
			-1

 

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

1) Вибираємо оцінку δ₁ = 1, зафарбуємо її.

2), 3) Елементи у стовпці 2 додатні, отже треба застосувати умову допустимості:

 

	A	B	C	D	E	F	G
	х1	х2	х3	х4	у1	b	b/aij
			-1
			-1

 

5) Виконаємо жорданове перетворення з ведучим елементом у А7:

 

	A	B	C	D	E	F	G
	х1	х2	х3	х4	у1	b	b/aij
		0,5	-1	-0,5
		1,5		0,5
		0,5	-1	-0,5

 

5) Маємо симплекс – таблицю з новим набором основних змінних х₁, у₁, новий опорний розв’язок (3; 0; 0; 0; 2), нове значення цільової функції g = 2.

6) Оскільки знову існує додатна оцінка δ₂ = 0,5, то переходимо до другого кроку сиплекс – методу і починаємо його з перевірки умови допустимості. Ведучим обираємо рядок 11, звідси ведучий елемент В11; черговим жордановим перетворенням дістаємо:

 

	A	B	C	D	E	F	G
	х1	х2	х3	х4	у1	b	b/aij
	-0,33333		-1	-0,66667
	0,666667			0,333333
	-0,33333		-1	-0,66667

Нарешті всі оцінки невід’ємні, отримуємо оптимальний розв’язок допоміжної задачі (0; 2; 0; 1), g = 1. Отже, оскільки у₁ = 1 > 0, то початкова задача нерозв’язна. Точніше кажучи, множина допустимих розв’язків є пустою.

Наприкінці розглянемо ще графічне розв’язання початкової задачі

f = 3х₁ + х₂ (mах)

.

На рисунку 5 зображені прямі L₁: х₁ + 2х₂ = 5 і L₂: 2х₁ + 3х₂ = 6. Оскільки 0 + 2∙0 = 0 < 5, то множина Ω допустимих розв’язків цієї задачі повинна бути розміщена по інший бік від прямої L₁, ніж початок координат О(0;0). Аналогічно множина Ω повинна бути розміщена по той самий бік від прямої L₂, що і початок координат. Разом з тим Ω повинна міститись у першій чверті, оскільки х₁ ≥ 0, х₂ ≥ 0. Як видно з рисунку, ці умови одночасно не виконуються для жодної точки, що є зримим підтвердженням результатів, отриманих симплекс – методом.

 

х₂

 

 

 

 

L₂

 

 

L₁

 

О х₁

 

Рисунок 5

Питання, тести

 

1. Дана задача.

У господарстві є два вида кормів вартістю 20 та 30 гривен за одиницю корму відповідно. У першому кормі міститься 2 одиниці вітаміну А та 3 одиниці вітаміну В, у другому 5 одиниць А та 2 одиниці В. Раціон повинен містити не менш як 9 одиниць А та 8 одиниць В. Скласти найдешевший раціон, який задовольняє цим вимогам.

Математична модель такої задачі це

 

А: f = 20х_А + 30х_В (max) Б: f = 20х_А + 30х_В (min)

 

В: f = 20х_А + 30х_В (max) Г: f = 20х_А + 30х_В (min)

 

2. Дана задача.

Нехай з трьох пунктів відправлення Р₁, Р₂, Р₃ треба перевезти однорідний вантаж до трьох пунктів призначення М₁, М₂, М₃, в тому числі з пункту Р₁ – 12 т, з пункту Р₂ – 8 т, з пункту Р₃ – 10 т. Вантаж повинен надійти за призначенням у пункт М₁ – 6 т, пункт М₂ – 9 т, пункт М₃ – 15 т.

Система обмежень такої задачі це

А: Б:

В: Г:

 

 

3. Дана задача.

Для виготовлення продукції двох видів (А і Б) на заводі використовують сировину трьох типів (1, 2 и 3). Кількість одиниць сировини кожного типу, що витрачається на один виріб кожного виду, запаси сировини та прибуток від одиниці продукції кожного виду наведені у таблиці:

 

Вироби	Прибуток	Сировина
А
Б
Запаси сировини

 

Математична модель такої задачі це

А: f = 200 х_А + 300 х_Б (min) Б: f = 200 х_А + 300 х_Б (max)

В: f = 200 х_А + 300 х_Б (min) Г: f = 200 х_А + 300 х_Б (max)

 

4. Дана задача.

Для виготовлення продукції використовують три вида сировини і чотири способи виробництва. Запаси сировини, її витрати на одиницю продукції та кількість виготовляємої продукції по кожному способу (за годину роботи) наведені у таблиці.

 

Сировина	Спосіб виробництва	Запаси
Кількість продукції

 

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

 

Математична модель такої задачі це

 

А: f = 18x₁ + 30x₂ + 40x₃ (min) Б: f = 18x₁ + 30x₂ + 40x₃ (max)

В: f = 12x₁ + 7x₂ + 18x₃ + 10x₄ (max) Г: f = x₁ + 2x₂ + 3x₃ + 4x₄ (max)

5. На рисунку зображені множина Ω допустимих розв’язків задачі максимізації лінійного програмування ОАВСД, лінія нульового рівня цільової функції цієї задачі L₀, і її вектор нормалі N, L₁, L₂ ║ L₀.

 

х₂

L₁ L₂

А

В

 

 

Ω. С

L₀ N

 

 

х₁

О Д

 

 

Рисунок

 

Множина оптимальних розв’язків даної задачі це

 

А: точка С

Б: точка В

В: точка О

Г: відрізок ВС

 

6. На рисунку зображені множина Ω допустимих розв’язків задачі максимізації лінійного програмування АВСД, лінія нульового рівня цільової функції цієї задачі L₀, і її вектор нормалі N, L₁, L₂ ║ L₀.

х₂

Множина оптимальних розв’язків L₂

даної задачі це А

 

А: точка А Б: точка Д L₁

 

В: точка В Г: не існує Д: відрізок ВС Ω

В

Д

N

L₀ С

х₁

О

 

 

Рисунок

 

7. На рисунку зображені множина Ω допустимих розв’язків задачі максимізації лінійного програмування ОАВС, лінія нульового рівня цільової функції цієї задачі L₀ і її вектор нормалі N, L₁ ║ L₀.

х₂

 

 

3 N(1;3)

 

A

L₁

 

B

Ω L₂

O 1 C х₁

 

L₀

Рисунок

 

Множина оптимальних розв’язків даної задачі це

 

А: точка A

Б: відрізок AВ

В: точка О

Г: точка N(1;3)

Д: не існує

 

7. На рисунку зображені множина Ω допустимих розв’язків задачі максимізації лінійного програмування ВАСD, лінія нульового рівня цільової функції цієї задачі L₀, і її вектор нормалі N, L₁ ║ L₀.

 

х₂

B D

Ω L₂

A N

L₀ C L₁

х₁

О

Рисунок

 

Множина оптимальних розв’язків даної задачі це

А: точка С

Б: відрізок CD

В: точка О

Г: не існує

Д: відрізок AC

 

 

9. Канонічна форма даної задачі лінійного програмування

f = 2х₁ + 3х₂ + х₃ (min)

 

це А: f = 2х₁ + 3х₂ + х₃ (min) Б: f = 2х₁ + 3х₆ – 3х₇ + х₃ (min)

 

В: f = 2х₁ + 3х₂ + х₃ (min) Г: f = – 2х₁ – 3х₂ – х₃ (max)

10. Канонічна форма даної задачі лінійного програмування

f = 5x₁ – 2х₂ + 3х₃ (max)

це

А: f = 5x₁ – 2х₂ – 3х₃ (max) Б: f = – 5x₁ + 2х₂ + 3х₃ (min)

 

В: f = 5х₁ – 3x₃ – 2х₄ + 2х₅ (max) Г: f = 5x₁ – 2х₂ – 3х₃ (max)

 

11. Задача лінійного програмування наведена у канонічній формі:

А: f = 5x₁ – 2х₂ – 3х₃ (max) Б: f = – 5x₁ + 2х₂ + 3х₃ (min)

 

В: f = 2х₁ + 3х₆ – 3х₇ + х₃ (min) Г: f = 2х₁ + 3х₂ + х₃ (min)

 

12. Знайти опорний розв’язок, до базису якого приведена дана симплекс – таблиця і значення цільової функції на цьому розв’язку.

 

х1	x2	x3	x4	x5	х6	х7	b
	– 1			– 1 – 1
	– 17			– 12			– 216

 

Відповідь: х₁ =___ х₂ =___ х₃ =___ х₄ =___ х₅ =___ х₆ =___ х₇ =___ f =___

 

13. Знайти опорний розв’язок, до базису якого приведена дана симплекс – таблиця і значення цільової функції на цьому розв’язку.

 

х1	x2	x3	x4	x5	х6	х7	b
		– 1	– 1		– 1 – 1		– 12
	– 5	– 6	– 2		– 12		– 360

 

Відповідь: х₁ =___ х₂ =___ х₃ =___ х₄ =___ х₅ =___ х₆ =___ х₇ =___ f =___

 

14. Знайти опорний розв’язок, до базису якого приведена дана симплекс – таблиця і значення цільової функції на цьому розв’язку.

 

х1	x2	x3	x4	x5	х6	х7	b
	– 3/2 1/2			– 1/2 – 1/2		– 1/2 1/2
	– 22	– 4		– 7		– 5	– 326

 

Відповідь: х₁ =___ х₂ =___ х₃ =___ х₄ =___ х₅ =___ х₆ =___ х₇ =___ f =___

 

 

15. Ведучий елемент наступного жорданова перетворення

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij
	0,5		0,05
			-0,5				3,333333
	7,5		-0,75
			-15			-1500

знаходиться у чарунці А: В2 Б: D3 В: А4 Г: С2

16. Ведучий елемент наступного жорданова перетворення

 

	А	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij
	2/3		- 1/3		2 1/3
	4 2/3		- 1/3		9 1/3
	1 2/3		2/3		-4 2/3

знаходиться у чарунці А: А2 Б: Е2 В: С4 Г: не існує

 

17. Ведучий елемент наступного жорданова перетворення

 

	A	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij
						1,666667
	- 1

знаходиться у чарунці А: А2 Б: В3 В: В4 Г: D3

 

18. Яку чарунку треба вибрати, щоб отримати опорний розв’язок транспортної задачі, заданої таблицею?

	А	В	С	D

 

А: А2 Б: В1 В: С2 Г: D3

 

19. Розв’язок транспортної задачі, заданий у таблиці, є опорним:

	А	В	С	D

А: Б:

	А	В	С	D

	А	В	С	D

В: Г:

	А	В	С	D

 

 

20. Допустимий розв’язком задачі лінійного програмування у канонічній формі є оптимальним, якщо

А: у нього існує невироджений базис

Б: для нього виконуються умови допустимості

В: всі його оцінки відмінні від нуля

Г: всі його оцінки недодатні

 

 

1. Цільова функція задачі лінійного програмування не обмежена зверху, якщо

А: всі його оцінки недодатні

Б: серед оцінок існує додатна

В: серед оцінок існує додатна, а решта елементів цього стовпця недодатні

Г: всі його оцінки невід’ємні

 

1. Умова допустимості виконана, якщо

 

А: серед модулів відношень вільних членів до відповідних елементів стовпця обираємо найменше

Б: серед модулів відношень вільних членів до відповідних елементів стовпця обираємо найбільше

В: серед відношень вільних членів до відповідних додатних елементів стовпця обираємо найменше

Г: серед відношень вільних членів до відповідних додатних елементів стовпця обираємо найбільше

 

Завдання

1. Дана задача.

Для виготовлення продукції двох видів (А і Б) на заводі використовують сировину трьох типів (1, 2 и 3). Кількість одиниць сировини кожного типу, що витрачається на один виріб кожного виду, запаси сировини та прибуток від одиниці продукції кожного виду наведені у таблиці: Розв’язати цю задачу графічним методом.

 

Вироби	Прибуток	Сировина
А
Б
Запаси сировини

 

2. Дана задача. Для виготовлення продукції використовують три вида сировини і чотири способи виробництва. Запаси сировини, її витрати на одиницю продукції та кількість виготовляємої продукції по кожному способу (за годину роботи) наведені у таблиці.

 

Сировина	Спосіб виробництва	Запаси
Кількість продукції

 

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

Розв’язати цю задачу симплекс – методом.

1. Розв’язати задачу лінійного програмування

f = 200 х₁ + 300 х₂ (max)

 

використавши надбудову Excel “Пошук розв’язку”.

 

4. Розв’язати задачу лінійного програмування

f = 20х₁ + 30х₂ (min)

,

 

використавши метод жорданових перетворень для пошуку початкового допустимого опорного розв’язку.

 

5. Розв’язати задачу лінійного програмування

f = 3х₁ + х₂ (mах)

.

використавши метод штучного базису для пошуку початкового допустимого опорного розв’язку.