Симплекс метод

Рис. 5.2. Область допустимих значень цільової функції

Лінія 4х₁ +1,5х₂ = 12 проходить через точки з координатами (х₁ =0, х₂ = 8); (х₁ = 3, х₂= 0); лінія 2х₁ +5х₂ = 20 – через точки з координатами ( х₁=0, х₂ = 4); (х₁ = 10, х₂= 0); лінія 2,5х₁ +2х₂=10 – через точки з координатами (х₁ = 0, х₂ = 5); (х₁ = 4, х₂ = 0), а лінія 2 х₂ = 5 (для всіх х₂ х₁ =2,5).

Таким чином, отримаємо область допустимих значень D, окреслену лініями і умовою, що х₁ ³ 0, х₂ ³ 0 (рис. 5.2).

Нанесемо на графік лінію цільової функції при F = 0. У цьому разі рівняння лінії 300х₁ + 225х₂ = 0 проходить через точки (х₁ = 0, х₂ = 0) і (х₁=–1,5, х₂ =2).

Розв‘язанням задачі може бути одна з кутових точок області допустимих значень: A, B, C, D, Е, найбільш віддалена від лінії цільової функції в напрямку її збільшення. Обчислимо координати цих точок і значення цільової функції в них. Для знаходження координати точки розв‘яжемо систему рівнянь із рівнянь ліній, на перетині яких знаходиться точка.

Для точки А отримаємо:

координати (х₁=0, х₂=4), F = 0×300+4×225=900.

Для точки B отримаємо:

координати (х₁=1¹/₃, х₂=3⁹/₁₇),

F = 1¹/₃×300+3⁹/₁₇×225 = 1147,06.

Для точки C отримаємо:

координати (х₁=2²/₁₇, х₂=2⁶/₁₇),

F = 2²/₁₇×300+2⁶/₁₇×225 = 1164,71.

Оптимальним розв‘язанням буде розв‘язання в точці С. Результатом є випуск продукції х₁ = 2,118 т і х₂ = 2,353 т. При цьому буде отриманий прибуток в розмірі 1164,71 грн.

Розв‘яжемо задачу прикладу 5.1 Симплекс-методом. Для цього запишемо умову задачі в канонічній формі, у вигляді рівностей :

х₁³ 0 і х₂³ 0.

Таблиця 5.2

і	Базис	С_баз				b	b/a_i,k
х₁	х₂	х₃	х₄	х₅	х₆
	х₃			1,5
	х₄
	х₅		2,5
	х₆						2,5	l
Рядок F	–300	–225
	k

Заповнимо початкову табл. 5.2 (нульовий план). Елементами базису виберемо ті елементи, які належать нульовій підматриці і мають коефіцієнт +1. Коефіцієнти рядка цільової функції рахуються, як сума добутку коефіцієнтів стовпчика на ціну відповідного базису за мінусом ціни змінної стовпчика. Так у стовпчику х₁ отримаємо 4×0 + 2×0 + 2,5×0 + 2×0 – 300 = – 300.

Ключовий елемент a_l,k знаходимо на перетині ключового k-го стовпчика, з найбільшим за модулем від’ємним коефіцієнтом в рядку цільової функції F, і ключового l-го рядка, з найменшим додатним числом b/a_i,k.

Обчислюємо нову таблицю за такими правилами:

базис у ключовому рядку х₆ замінюємо на змінну у ключовому стовпчику х₁;

на місце ключового елемента ставимо одиницю;

решту елементів ключового стовпчика перетворюємо на нулі;

елементи ключового рядка перераховуємо за формулою = a_l,j/ a_l,k, діленням чисел на ключовий елемент;

решту елементів обчислюємо за формулою = a_i,j – (a_i,k ×a_l,j)/ a_l,k, - правило квадрата із метода Жордана-Гаусса для систем рівнянь.

Заповнимо табл.5.3.

Таблиця 5.3

і	Базис	С_баз					b	b/a_i,k
х₁	х₂	х₃	х₄	х₅	х₆
	х₃			1,5		–2		1,33	l
	х₄					–1
	х₅					–1,25	3,75	1,88
	х₁					0,5	2,5	–
Рядок F		–225
		k

Наведена табл.5.3 не є оптимальним планом, оскільки в рядку F є від’ємні коефіцієнти. Через те знаходимо знову ключовий елемент a_l,k і перерахуємо таблицю за вказаними правилами (табл.5.4).

Таблиця 5.4

і	Базис	С_баз						b	b/a_i,k
х₁	х₂	х₃	х₄	х₅	х₆
	х₂				0,667		–1,33	1,333	–1
	х₄				–3,33		5,666	8,333	1,47
	х₅				–1,33		1,417	1,083	0,76	l
	х₁						0,5	2,5
Рядок F						–150
						k

План знову не оптимальний, тому знаходимо новий ключовий елемент і користуючись ним перерахуємо нову таблицю (табл.5.5).

Таблиця 5.5

і	Базис	С_баз					b	b/a_i,k
х₁	х₂	х₃	х₄	х₅	х₆
	х₂						2,353
	х₄
	х₆				–0,941	0,706	0,765
	х₁						2,118
Рядок F			8,823		105,9	1164,71

У табл.5.5 ми, в першу чергу, перераховуємо коефіцієнти рядка цільової функції F. Впевнившись, що отриманий план є оптимальним, бо від’ємних коефіцієнтів в рядку F немає, обчислюємо коефіцієнти стовпчика b. Решту коефіцієнтів таблиці можна не обчислювати.

Висновки по результатах розрахунків

З таблиці оптимального плану (див. табл. 5.5) робимо висновок, що потрібно виробити 2,118 т продукції х₁і 2,353 т продукції х₂. При цьому буде отримано прибуток в розмірі 1164,71 грн. Лишаються невикористаними чотири одиниці обладнання групи Б ( х₄ = 4 ) і 0,765 одиниці обладнання групи Г (х₆ = 0,765).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Приклад 5.1. Оптимізація використання обладнання на заводі	\|	Приклад 5.2. Оптимізація використання сировини

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.