2 курс. Ден. ФК, УП, ЕП 12 / Економіко математичні методи та моделі (Оптимізаційні методи) Ч.1 Ден. 2010

другого типу (менш продуктивних) підприємство може придбати не більше 8 штук. Скласти математичну модель даної економічної задачі.

2.Меблева фабрика випускає крісла двох видів. На виготовлення крісла І виду витрачається 2 м2 дощок, 0,8 м2 оббивочної тканини і 2 людиногодини, а на виготовлення крісла другого виду, відповідно, 4 м2, 1,25 м2, 1,75 людино-години. Відомо, що ціна одного першого виду становить

150у.г.о., а другого виду – 200 у.г.о. Скільки крісел кожного типу потрібно випустити, щоб прибуток від випущеної продукції був максимальний, якщо фабрика має в наявності 4400 м дощок, 1500 м2 оббивочної тканини і може затратити 3200 людино-годин робочого часу на виготовлення цієї продукції? Скласти математичну модель даної економічної задачі.

3.Для виготовлення брусів довжиною 1,2 м, 3 м і 5 м у співвідношенні 2:1:3 на розпил надходять 195 колод довжиною 6 м. Визначити план розпилу, що забезпечує максимальне число комплектів. Скласти економіко-математичну модель задачі.

4.Є три пункти постачання однорідного вантажу А1, А2, А3 і п'ять пунктів В1, В2, В3, В4, В5 споживання цього вантажу. На пунктах А1, А2, А3 знаходиться вантаж у кількостях 90, 70, 110 тонн. У пункти В1, В2, В3, В4, В5 потрібно доставити відповідно 50, 60, 50, 40, 70 тонн вантажу. Відстані в сотнях кілометрах між пунктами постачання й споживання наведені в матриці-таблиці D:

Пункти		Пункти споживання
постачання
	В1	В2	В3		В4	В5
А1	9	1	1		5	6
А2	6	4	6		8	5
А3	2	9	3		5	3

Знайти такий план перевезень, при якому загальні витрати будуть мінімальними. Скласти економіко-математично модель транспортної задачі.

30

Питання для самоконтролю

1.Економічна та математична постановка оптимізаційних задач.

2.Класифікація оптимізаційних задач.

3.Загальна постановка задачі математичного програмування (МП).

4.Навести приклади економічних задач, які можна звести до задачі ЛП.

5.Етапи побудови моделі та розв'язання оптимізаційної задачі.

6.Сформулювати задачу оптимального використання ресурсів. Що і ній визначає цільова функція? обмеження на змінні?

Бібліографічний список до теми

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

Тема 3. Задача лінійного програмування та методи її розв'язування

Мета: опрацювання питань згідно запропонованого плану вивчення теми, закріплення, поглиблення та систематизація знань з економічної та математичної постановки задач лінійного програмування (ЗЛП), методів розв’язання ЗЛП.

План вивчення теми

1.Економічна та математична постановка задач лінійного програмування

(ЛП).

2.Канонічна форма лінійної оптимізаційної моделі.

3.Геометрична інтерпретація множини допустимих розв'язків задачі лінійного програмування. Графічне розв'язання задач лінійного програмування. з двома змінними.

4.Симплексний метод розв’язування задач ЛП.

5.Симплекс-таблиця та правила її заповнення. Алгоритм симплексметоду. Збіжність симплекс-методу.

6.М-метод, інші методи розв’язування задач лінійного програмування.

31

Методичні рекомендації до самостійної роботи

Загальна задача

F = f (x ,..., x )

1 n

gi (x1,..., xn ) =( ≤, ≥) bi

лінійного програмування. Нехай функція

є

лінійною

і

обмеження

також усі є лінійними. Загальною задачею

лінійного програмування (ЛП) називається задача, яка полягає у визначенні мінімального (мінімального) значення функції

F =c1x1 +c2x2 +...cnxn →min (max)

(3)

за умов

a11x1 +a12 x2 +... +a1n xn = (≤ , ≥ )b1
		+a22 x2 + +a2n xn							= (≤ , ≥ )b2
a21x1
.........................................
a	x	+a	m2	x	2	+... +a	mn	x	n	= (≤ , ≥ )b
	m1 1										m

x j ≥ 0,( j =1,n).

(4)

(5)

Функція (3) називається цільовою функцією (або лінійною формою)

задачі (3)–(5), а умови (4)–(5)– обмеженнями даної задачі. Як правило, в економічних застосуваннях коефіцієнти cj та aij є додатними.

Розв'язок системи обмежень, у якому вільні невідомі дорівнюють

нулю, називається базисним планом. Вектор X =(x1,x2..xn), який задовольняє умовам (4) та (5), називається допустимим планом задачі ЛП (3-5).

План	X =(x1,x2 ..xn) задачі ЛП називається опорним, якщо вектори
a
		1 j
a2 j				, які відповідають додатнім величинам	x j плану, є лінійно
A j =	...
a
		mj

незалежними, тобто допустимий базисний план є опорним.

32

Опорний план задачі ЛП називається невиродженим, якщо він містить рівно m додатних компонент. Опорний невироджений план, який, крім того, задовольняє умові (1), називається оптимальним.

В системі рівнянь різних наборів базисних невідомих може бути не більше від

Cnk =

n!

.

k!(n − k)!

Будь-яка задача лінійного програмування легко зводиться до

bi , i =

канонічної форми, коли в системі обмежень всі

1,m

невід’ємні,

а всі обмеження є рівностями.

ЗЛП, записана в канонічної формі має вигляд:

F =c1x1 +c2x2 +...cnxn →min

a11x1 + a12 x2 +... + a1n xn = b1,

+ a22 x2 +... + a2n xn

= b2 ,

a21x1

.........................................

a

x

+ a

m2

x

2

+... + a

mn

x

n

= b .

m1 1

m

x j ≥ 0,( j =

).

1,n

Якщо, наприклад, потрібно

знайти

max F ,

то

шукають такі

значення невідомих x1,...,xn, які приводять до min(−Z ) . Якщо деяке

обмеження	має вигляд		ai1 x1 + ai 2 x2 +... + ain xn ≤ bi ,				то	вводять
додаткову	змінну	xn+1	і	так	отримують	канонічний		вигляд
ai1 x1 + ai 2 x2	+... + ain xn + xn + 1			= bi , xn+1 ≥ 0. Якщо деяке обмеження має
вигляд ai1 x1 +ai 2 x2		+...+ain xn ≥bi , то вводять додаткову змінну –xn+1 та
отримують	канонічний		вигляд		ai1 x1 + ai 2 x2	+... + ain xn	− xn + 1 = bi ,
xn+1 ≥0.

33

Якщо на змінні x1,x2..xk (k ≤ m) не накладається умова невід'ємності, то для зведення ЗЛП до канонічної форми треба зробити

заміну x

= x'

− x'', (i =

) , де x' ≥ 0, x'' ≥ 0, (i =

).

1,k

1,k

i

i

i

i

i

Задачу (1)-(3) записують також у матричній формі:

F = CX →max

,

AX = B,

X ≥0

a

a

L

a

11

12

1n

a

21

a

22

L a

2n

де A ={aij } =

L

є матриця коефіцієнтів при

L

L

L

am

L a

a

m1

12

mn

змінних;

x

b

1

1

x

2

- вектор змінних,

b

X =

B = 2

- вектор вільних членів,

...

...

x

n

b

m

C =(c1,c2..cn)- вектор коефіцієнтів при змінних у цільової функції.

Задачу ЛП зручно також записувати у вигляді:

			n
			∑	c j x j
F		=	j =1		→ max
	n
		aij x j = bi (i =1, m);
∑j =1
			≥ 0 (j =1, n).
x j

ЗЛП у векторної формі виглядає так:

F =CX → max

за умов

34

A1x1 + A2 x2 +K+ An xn = B ,

a11

де A1 = a21 ,a...

m1

		a					a
		12					1n
A	=	a22		, ...,	A	=	a2n		є вектори
2					n
		...					...
		am2					amn

коефіцієнтів при змінних.

До методів вирішення ЗЛП відносяться таки:

−графічний метод;

−симплекс-метод.

Графічний метод відрізняється простотою та ілюстративністю, але він може бути використаний практично лише для двох змінних x1 та x2 ,

коли система обмежень сумісна.

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

F =c1x1 +c2x2 →min(max

(6)

за умов

a11x1 +a12 x2 = (≤ , ≥ )b1

a21x1 +a22 x2 = (≤ , ≥ )b2

(7)

.........................................

a

x

+a

m2

x

2

= (≤ , ≥ )b

m1 1

m

x j

≥ 0,( j =

).

1,n

(8)

Кожна з нерівностей (7), (8) системи обмежень задачі геометрично

визначає напівплощину відповідно з граничними прямими

a11x1 +a12 x2 =b1,

+a22 x2 =b2 ,

a21x1

.........................................

a

x

+a

m2

x

2

=b .

m1 1

m

x1 = 0, x2 = 0.

35

У тому разі, якщо система нерівностей (7), (8) сумісна, область її розв’язків є множина точок, які належать усім вказаним напівплощинам. Оскільки множина точок перетину даних напівплощин опукла, то областю можливих розв’язків задачі (5)–(7) є опукла множина, яка називається многокутником розв’язків. Сторони цього многокутника містяться на прямих, рівності яких випливають з початкової системи обмежень заміною знаків нерівності на знаки точних рівностей.

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

При вказаних умовах в одній із вершин многокутника розв’язків цільова функція набуває максимального значення. Для визначення даної вершини будують лінію рівня c1 x1 + c2 x2 =l (де l – деяка стала), яка проходить через многокутник розв’язків і пересувають її в напрямку

вектора c = ( с1; с2 ) до тих пір, поки вона не перейде через останню її загальну точку з многокутником розв’язків. Координати вказаної точки і визначають оптимальний план цієї задачі.

Алгоритм графічного методу:

1.Будуємо прямі лінії, рівняння яких дістаємо зміною в обмеження задачі знаків нерівностей на знаки рівностей. Визначаємо півплощіни, що відповідають кожному обмеженню задачі.

2.Знаходимо многокутник розв'язків ЗЛП.

3.Будуємо вектор-градієнт N = (c1;c2 ) , що задає напрям зростання значень цільової функції задачі.

4.Будуємо пряму l = c1x +c2x2 = const , перпендикулярну до вектора

N.

36

5.Переміщуючи пряму l в напрямі вектора N для задачі максимізації або в протилежному напрямі для задачі мінімізації, знаходимо вершину многокутника розв'язків А, де цільова функція досягає екстремального значення.

6.Визначаємо координати точки A(x1, x2 ) і обчислюємо екстремальне значення цільової функції в цій точці.

Втому разі, коли пряма l збігається зі стороною багатокутника розв'язків, це означає, що задача має альтернативні оптимальні плани. Будь який альтернативний оптимальний план задачі можна записати як

опуклу комбінацію отриманих двох крайніх розв'язків:

X * = λ1X1* + λ2 X 2* , де 0 ≤ λ1 ≤1;0 ≤ λ2 ≤1;λ1 + λ2 =1.

Симплекс-метод є аналітичним методом знаходження рішення

ЗЛП.

У загальному випадку рішення основної ЗЛП симплекс-методом складається з двох:

−знаходження опорного (або допустимого) рішення;

−знаходження оптимального рішення.

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

При вивченні цього питання рекомендується ретельне опрацювання теоретичного матеріалу лекції, а саме алгоритму симплексного методу .

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

1. Зведення задачі до канонічної форми запису за допомогою введення додаткових змінних. У цільовій функції додаткові змінні мають коефіцієнт нуль.

37

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

3.Побудова симплексної таблиці.

4. Перевірка опорного плану на оптимальність за допомогою оцінок

j = Z j −C j	( j =			)
			1,n				всі оцінки задовольняють		умові
				. Якщо
		j ≥ 0		( j =		)		j ≤ 0	( j =		)
оптимальності (					1,n		для задачі на максимум,			1,n

для задачі на мінімум), то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умові оптимальності, то переходять до нового опорного плану зміною базису, тобто виключенням з нього деякої змінної та введенням замість неї нової з числа вільних змінних задачі. При цьому вибирають найбільшу за абсолютною величиною оцінку і відповідну змінну вводять до базису. Відповідний стовпчик симплексної таблиці називають напрямним. Для визначення змінної, що має бути виключена з базису, знаходять для всіх

	θ =	bi
		aik та вибирають найменше
	додатних aik напрямного стовпчика

значення, яке вказує на змінну, що виводиться з базису. Відповідний рудок симплексної таблиці називають напрямним. Розв'язувальний елемент-це число, яке визначається перетином напрямного стовпчика та напрямного рядка.

5. Перехід до нового опорного плану задачі виконується визначенням розрахунком нової симплексної таблиці:

− кожний елемент розв`язувального рядка необхідно поділити на розв’язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці;

38

− усі інші елементи наступної симплексної таблиці розраховують за

	(1) (2) − (3) (4)
правилом прямокутника	(1)	, вершини якого

утворюються такими числами:

(1)– розв’язувальний елемент;

(2)– число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;

(3), (4) – елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.

2.Повторення п.3.

Слід також звернути увагу на те, що коли в системі обмежень немає необхідної кількості одиничних незалежних векторів, тоді для побудови першого опорного плану застосовують метод штучного базису.

Алгоритму метода штучного базису:

1.Зводять задачу до канонічної форми запису за допомогою введення додаткових змінних.

2.Будують розширену задачу і знаходять початковий опорний план методом штучного базису, а саме вводять штучні змінні з коефіцієнтом +1 . У цільовій функції ЗЛП штучні змінні мають коефіцієнт +М для задачі на мінімум або –М для задачі на максимум, де М-досить велике додатне число.

3.Розв'язують розширену задачу симплексним методом.

Алгоритм двоїстого симплексного методу:

1. Необхідно звести всі обмеження задачі до виду „≤”. Ввести додаткові невід'ємні змінні. Визначити початковий базис та перший опорний план

X = (b1,b2 ,K,bm ) .

2. Якщо всі оцінки векторів j = Fj	−c j ≤ 0 і компоненти вектора-
стовпчика „План” (b1,b2 ,K,bm ) ≥ 0	для всіх i =		, то ЗЛП
		1,m

39