Лінійне програмування (частина 1).

Тема: Лінійне програмування (частина 1).

Мета: Навчитися складати ЕММ задач, будувати опорні плани задач лінійного програмування.

План.

 

1.  Побудова економіко математичної моделі задачі планування виробництва.

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

3.  Побудова економіко математичної моделі задачі розпилу матеріалів (задача про відходи).

4. Побудова опорного плану задачі лінійного програмування.

5. Побудова розширеної задачі до вихідної. Знаходження штучного базису.

 

Номер та зміст завдання

Задача 1. Побудова економіко математичної моделі задачі планування виробництва

Підприємство випускає два види виробів А і В. Для їх виробництва використовуються три типи сировини S₁, S₂, S₃. Витрати сировини на виробництво одного виробу кожного виду та запаси сировини наведені в таблиці (числа умовні).

Вид сировини	Запаси сировини (кг)	Норми витрат сировини (кг) на одиницю продукції
		A	B
S1
S2
S3

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

Значення  обрати згідно варіанту з таблиці 1.

Таблиця 1

Варіант							S1	S2	S3	c1	c2
1	7	6	1	3	3	2	1365	1245	650	6	5
2	8	7	4	3	6	9	864	864	945	2	3
3	14	12	8	8	4	2	624	541	372	7	3
4	10	9	5	6	3	1	735	765	455	8	4
5	8	7	7	10	6	2	459	379	459	9	9
6	7	12	8	4	4	2	312	541	372	7	3
7	10	3	5	6	1	1	735	255	455	8	4
8	5	9	10	7	9	8	343	587	587	11	7
9	4	3	2	3	4	6	480	444	546	2	4
10	3	4	3	1	3	4	300	520	600	6	3
11	8	7	14	7	4	1	417	290	591	5	5
12	16	14	4	6	12	9	1728	1728	945	2	3
13	3	4	3	5	8	11	453	616	627	2	3
14	16	7	4	6	6	9	1728	864	945	2	3
15	19	16	19	26	17	8	868	638	853	5	4
16	15	15	18	33	25	6	571	577	890	8	10
17	19	32	19	26	34	8	868	1276	853	5	4
18	3	2	3	5	4	11	453	308	627	2	3
19	3	3	10	5	1	2	414	241	768	12	16
20	7	14	8	13	16	2	363	654	429	6	4
21	3	8	3	1	6	4	300	1040	600	6	3
22	2	3	2	3	6	8	428	672	672	3	8
23	2	1	2	3	2	8	428	224	672	3	8
24	8	3	3	6	4	5	880	393	450	6	5
25	8	3	6	6	4	10	880	393	900	6	5
26	5	6	7	7	6	1	256	283	363	9	7
27	15	15	9	33	25	3	571	577	445	8	10
28	9	15	15	27	15	3	606	802	840	11	6
29	10	18	10	14	18	8	686	1174	587	11	7
30	7	12	4	4	4	1	312	541	188	7	3

 

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

Нехай маємо два види кормів А і В, які містять поживні речовини S₁, S₂, S₃. Число одиниць поживних речовин в 1 кг кожного виду корму і необхідний мінімум поживних речовин наведені в таблиці (цифри умовні).

Поживні речовини (вітаміни)	Необхідний мінімум поживних речовин	Число одиниць поживних речовин в 1 кг корму
		A	B
S1
S2
S3

Вартість 1 кг корму Виду А і В становить, відповідно,  і  умовних грошових одиниць. Скласти денний раціон, який має мінімальну вартість і в якому поживних речовин кожного виду буде не менше встановленої норми.

Значення  обрати згідно варіанту з таблиці 1.

Задача 3. Побудова економіко математичної моделі задачі розпилу матеріалів (задача про відходи).

Для виготовлення брусу довжиною і м у співвідношенні  на розкрій поступають  колод довжиною  м. Визначити план розпилу, який забезпечить максимальне число комплектів.

Значення  обрати згідно варіанту (див. табл. 2).

Вказівка. Перш за все необхідно визначити всі можливі способи розпилу колод, вказавши відповідне число брусу, яке можна одержати з однієї колоди. Наприклад, . Згідно з цими даними отримуємо такі способи розпилу:

Спосіб розпилу	Можливе число брусків довжиною
	0,8 м	2 м	1,5 м
1	5	-	-
2	3	-	1
3	2	1	-
4	1	-	2
5	-	2	-
6	-	1	1

За змінні  обирають кількість колод, розпилених і-м способом. В даному випадку . Змінна  - число комплектів брусків.

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

Таблиця 2

Варіант
1	0,8	1,2	2,2	1	2	3	96	4,2
2	1	1,5	1,6	1	2	1	56	4
3	2	2,4	2,6	1	2	2	45	5,6
4	1	2	3	1	3	2	85	4,8
5	1,5	2,5	1	2	1	2	12	6
6	0,8	1	1,2	1	2	1	95	3,6
7	1,3	1,2	1	2	3	3	75	3,8
8	1,5	1,2	3,7	2	3	1	48	4,1
9	0,6	2,4	3,2	1	3	3	100	5
10	5	2,5	3	5	1	1	203	5,2
11	2,3	2,7	3	1	2	2	856	5,4
12	1	3	2	2	7	1	458	5,3
13	3	5	4	2	1	1	856	5,8
14	2,2	3,9	4	1	1	2	135	4,9
15	1,8	4	2,3	1	1	1	452	4,6
16	0,6	1,2	2,2	1	2	3	203	4,3
17	1,2	1,5	1,6	1	2	1	250	4,5
18	2,5	2,4	2,6	1	2	2	456	3
19	1,8	2	3	1	3	2	950	3,1
20	1,8	2,5	1	2	1	2	1000	3,3
21	1,6	1	1,2	1	2	1	560	3,6
22	2,3	1,2	1	2	3	3	589	3,8
23	2,5	1,2	3,4	2	3	1	975	3,4
24	2,6	2,4	3,2	1	3	3	461	3,2
25	2,5	2,5	3	5	1	1	543	3,7
26	3,3	2,7	3	1	2	2	458	4,7
27	4	3	2	2	7	1	764	4,2
28	4,5	2,5	4	2	1	1	964	4,6
29	3,2	3,9	4	1	1	2	542	6
30	2,8	4	2,3	1	1	1	125	6,2

 

4. Побудова опорного плану задачі лінійного програмування.

Фермер вирощує два види тварин - норок та нутрій. Для цього використовується три види кормів. Щоденна кількість корму кожного виду  наведена в таблиці. В ній також вказані запаси кормів та прибуток від реалізації 1 норки та 1 нутрії. Визначити, скільки тварин кожного виду слід вирощувати фермеру, щоб отримати максимальний прибуток.

Вид корму	Добовий раціон		Запаси кормів
	Норки	Нутрії
І	2	3	180
ІІ	4	1	240
ІІІ	6	7	426
Прибуток	16	6

Математична модель задачі має вигляд:

.

задачу лінійного програмування записують в основній формі:

.

Знаходять опорний план:

1. Визначають базисні змінні. Для цього:
   1. виписують вектори з координатами, що відповідають коефіцієнтам системи обмежень при відповідних змінних: ;
   2. серед виписаних векторів знаходять ті, що складають систему одиничних.

Нагадаємо, що одиничним називається вектор, у якого одна координата дорівнює одиниці, а всі інші – нулі. У систему одиничних векторів повинно входити стільки векторів, скільки координат має кожен з них, при чому таких, що в першому одиниця знаходиться на першому місці, а всі інші координати – нулі; в другому одиниця знаходиться на другому місці, а всі інші нулі і т.д.

У даному прикладі систему одиничних складають вектори .

Змінні, що відповідають одиничним векторам, називаються базисними. У даному випадку це змінні .

2. Заповнюють першу симплексну таблицю (табл. 3):
   1. у стовпчик „Базис” записують базисні змінні;
   2. над змінними  надписують коефіцієнти цільової функції при відповідних змінних;
   3. стовпчик „С_б” складають коефіцієнти цільової функції при базисних змінних;
   4. у стовпчик „План” записують координати вектора Р₀;
   5. у стовпчики  заносять відповідно координати векторів ;

Таблиця 3

№	Базис	Сб	План	16	6	0	0	0	Оціночне відно-шення
				Х1	Х2	Х3	Х4	Х5
1	х3	0	180	2	3	1	0	0	90
2	х4	0	240	4	1	0	1	0	60
3	х5	0	426	6	7	0	0	1	71
m+1			0	-16	-6	0	0	0

 

5. Побудова розширеної задачі до вихідної. Знаходження штучного базису.

У прикладі 4 за початковими умовами обмеження накладались тільки на кількість кормів. Введемо ще одне обмеження. Нехай фермер уклав угоду на продаж 20 тварин виду В. Тоді у систему обмежень вводиться ще одна нерівність: . Математична модель набуває вигляду:

.

Запишемо її в основній формі:

.

Знаходять опорний план:

1. Визначають базисні змінні. Для цього:
   1. виписують вектори з координатами, що відповідають коефіцієнтам системи обмежень при відповідних змінних:

;

2. серед виписаних векторів знаходять одиничні:

.

Як бачимо, ми маємо тільки три одиничних вектори, у той час як система одиничних векторів має містити чотири. Для системи одиничних векторів не вистачає вектора з координатами . Отже, для того, щоб стало можливим застосування симплексного методу, необхідно ввести в четверте обмеження деяку змінну, щоб відповідний вектор мав потрібні нам координати. Дана змінна не буде мати економічного змісту, вона вводиться лише для можливості отримання системи одиничних векторів. Такі змінні називаються штучними, позначаються , і вводяться в цільову функцію з коефіцієнтом . Математична модель набуде вигляду:

.

До векторів  додається ще один  - одиничний вектор, якого не вистачало.

Отже, систему одиничних векторів складають вектори , а відповідні змінні  є базисними.

2. Заповнюють таблицю, до якої додається ще один рядок з номером m+2 (табл. 4):

Таблиця 4

№	Базис	Сб	План	16	6	0	0	0	0	-М	Оціночні відношення
				Х1	Х2	Х3	Х4	Х5	Х6	У1
1	х3	0	180	2	6	1	0	0	0	0
2	х4	0	240	4	1	0	1	0	0	0
3	х5	0	426	6	7	0	0	1	0	0
4	у1	-М	20	0	1	0	0	0	-1	1
m+1			0	-16	-6	0	0	0	0	0
m+2			-20	0	-1	0	0	0	1	0

1. у стовпчик „Базис” записують базисні змінні;
2. над змінними  надписують коефіцієнти цільової функції при відповідних змінних;
3. стовпчик „С_б” складають коефіцієнти цільової функції при базисних змінних;
4. у стовпчик „План” записують координати вектора ;
5. у стовпчики  заносимо відповідно координати векторів .

 

Методичне забезпечення

1. Сергієнко В.А. Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання / В.А. Сергієнко, Л.П. Перхун, 2010. – 140 С.
2. Лавров Є.А. Математичне програмування: навчальний посібник / Є.А. Лавров, Л.П. Перхун, В.А. Сергієнко / За ред. Є.А. Лаврова. – Суми, 2010. – 224 С.

 

Рекомендована література

Базова

1. Бех О.Б. Збірник задач з математичного програмування. Навч. пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 212 С.
2. Бех О.Б. Математичне програмування. Пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 200 С.
3. Вдовин М. Л. Математичне програмування теорія та практикум. Пос. / М.Л. Вдовин, С.Г. Данилюк – К.: Видавництво Ліра-К, 2014. – 160 С.
4. Глушик М. М. Математичне програмування. Підручник / М. М. Глушик, І.М. Копич, В.М. Сороківський – К.: Видавництво Ліра-К, 2014. – 280 С.
5. Глушик М. Математичне програмування. Підручник / М. Глушик, І.Копич, О.Пенцак, В. Сорківський – К.: Видавництво Ліра-К, 2013. – 216 С.
6. Копич І.М. Математичні моделі в менеджменті та маркетингу. Навч. пос. / І.М. Копич, В.М. Сороківський ,В.І.Стефаняк – К.: Видавництво Ліра-К, 2014. – 376 С.
7. Кучма М.І. Математичне програмування: приклади та задачі. пос. / М.І. Кучма – К.: Видавництво Ліра-К, 2013. – 344 С.
8. Мартиненко М.А. Математичне програмування: підручник / М.А. Мартиненко, О.М. Нещадим, В.М. Сафонов – К.: Видавництво Ліра-К, 2010. – 311 С.

 

Інформаційні ресурси

(в т.ч. електронна бібліотека СНАУ)

1. http://web.archive.org/web/20070205063920/http://dims.karelia.ru/~alexmou/tpr/tpr_02_linear_programming.ppt – слайди по лінійному програмуванню
2. Український інститут ІТ в освіті Економіко-математичне моделювання (Демо-версія)  [Електронний ресурс]. – Режим доступу: http://moodle.ipo.kpi.ua/moodle/mod/resource/index.php?id=125
3. Іващук О.Т. Економіко-математичне моделювання [Електронний ресурс] / О.Т. Іващук. – Т.: ТНЕУ «Економічна думка», 2008. – 704 с.
4. Курило А.О. Математичне програмування. Конспект лекцій. - Суми, 2015 рік 136 ст., табл. 51, рис. 36.
5. Курило А.О. Математичне програмування. Частина 1: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.76, табл. 20, рис. 11.
6. Курило А.О. Математичне програмування. Частина 2: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.84, табл. 16, рис. 13.
7. Сергієнко В.А.  Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання./ В.А.Сергієнко, Л.П. Перхун. 2009 – 149 с.
8. Сергієнко В.А., Перхун Л.П. Електронний засіб навчального призначення: «Математичне програмування» для студентів денної та заочної форм навчання за напрямом підготовки 6.030601 «Менеджмент», 2010.