Задача по формуванню оптимальних складів

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

Клас	Звичайні	Підвищеного комфорту	Парк	Кількість
1
2
3

Знайти оптимальну кількість електропоїздів для перевезення максимальної кількості пасажирів.

- кількість звичайних поїздів;

- кількість поїздів підвищеного комфорту;

- кількість вагонів класу в звичайних електропоїздах;

- кількість вагонів класу в електропоїздах підвищеного комфорту. Тоді отримуємо

В даному випадку необхідно задати умову, що ,- цілі числа. Тому задачу називають «задачею цілочисельного програмування».

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

Тип	Пас	Шв	К-ть	Парк
Б	1	-	-	5
П	8	4	54	44
К	6	8	36	48
Л	-	2	18	8

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

- багажних вагонів,

- плацкартних,

- купейних,

- люкс.

Враховуючи наявний парк вагонів, отримуємо наступні нерівності:

Дана система нерівностей є системою виробничих обмежень.

Оскільки ми не можемо сформувати від’ємну кількість потягів то .

Кількість пасажирів дорівнює

Відповідь.

Класифікація злп

1. Загальна форма запису ЗЛП . Частина виробничих обмежень, задана нерівностями, частина рівняннями. На деякі, або навіть усі змінні можуть бути накладені обмеження невід’ємності. Інші змінні будуть довільними. Цільова функція може прямувати як до мінімуму, так і до максимуму.

(1.4)

2. Стандартна форма запису ЗЛП. Всі виробничі обмеження задані нерівностями, змінні – невід’ємні. Цільова функція може прямувати як до мінімуму, так і до максимуму.

(1.5)

3. Канонічна форма запису ЗЛП. Всі виробничі обмеження задані рівняннями, змінні – невід’ємні. Цільова функція прямує до максимуму. - невід’ємні.

(1.6)

,,,

Перехід від загальної та стандартної форми до канонічної

Крок 1.

Нехай - довільна змінна, тобто на неї не накладено обмеження невід’ємності. Введемо дві нові невід’ємні змінні:,, і запишемо додаткове обмеження:.

Крок 2.

До лівих частин виробничих обмежень, заданих нерівностями, додаємо нові – невід’ємні змінні і знак «» замінюємо на «=». Тоді система обмежень з (1.4) набуває вигляду

Крок 3.

Якщо деяке від’ємне, то помножимо відповідне рівняння на «-1».

Крок 4.

Якщо , то.

Приклад 1.3. Звести ЗЛП до канонічної форми.

Розв’язання. Задача записана в загальній формі. Спочатку домножимо нерівність на -1 і отримаємо. Оскільки усі змінні – невід’ємні, то переходимо до кроку 2.

До лівих частин усіх виробничих обмежень, крім другого додаємо нові невід’ємні змінні і знак «» замінюємо на «=». Зауважимо, що друге обмеження вже задане рівністю, тому не потребує додаткових перетворень. Маємо

Оскілки - від’ємне, то домножимо четверте рівняння на -1.

Відповідь.

Зауваження 1.4. Змінні називають фіктивними, оскільки вони не впливають на значення цільової функції і після розв’язання ЗЛП відкидаються.

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

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

Варіант 1

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 3 4	4 2 0	1 1 2	0 3 1	1200 800 1000
Прибуток	5	3	1	1

Продукції першого виду необхідно виробити не більше 120 одиниць, а четвертого – не менше 200. Сировина С повинна бути використана повністю.

Варіант 3

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 5	4 2 0	1 1 2	0 3 1	600 800 1000
Прибуток	2	6	1	1

Продукції другого виду необхідно виробити не більше 120 одиниць, а четвертого – не менше 200. Сировина А повинна бути використана повністю.

Варіант 5

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 6	4 2 0	1 1 2	0 3 1	1200 800 1000
Прибуток	2	3	5	1

Продукції третього виду необхідно виробити не більше 120 одиниць, а четвертого – не менше 200. Сировина С повинна бути використана повністю.

Варіант 2

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 4 2	0 3 1	1200 800 900
Прибуток	2	5	1	1

Продукції другого виду необхідно виробити не більше 100 одиниць, а четвертого – не менше 200. Сировина С повинна бути використана повністю.

Варіант 4

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 4	4 2 0	0 1 2	0 3 1	1200 800 2000
Прибуток	2	3	5	1

Продукції третього виду необхідно виробити не більше 100 одиниць, а четвертого – не менше 180. Сировина А повинна бути використана повністю.

Варіант 6

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 4	4 2 0	1 0 2	0 3 1	1000 800 2000
Прибуток	6	3	1	2

Продукції першого виду необхідно виробити не більше 100 одиниць, а четвертого – не менше 180. Сировина А повинна бути використана повністю.

Варіант 7

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 8	4 2 0	1 0 2	0 3 1	600 800 2000
Прибуток	2	3	5	4

Продукції першого виду необхідно виробити не менше 120 одиниць, а третього – не більше 180. Сировина A повинна бути використана повністю.

Варіант 9

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 6	4 2 3	1 1 2	0 3 1	1000 1800 2000
Прибуток	2	6	1	4

Продукції першого виду необхідно виробити не менше 150 одиниць, а другого – не більше 180. Сировина A повинна бути використана повністю.

Варіант 11

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 8	4 2 0	1 1 0	0 3 1	1200 800 2000
Прибуток	2	1	5	4

Продукції другого виду необхідно виробити не менше 100 одиниць, а третього – не більше 200. Сировина А повинна бути використана повністю.

Варіант 13

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 1 2	0 3 1	1500 1000 600
Прибуток	3	5	1	4

Продукції другого виду необхідно виробити не більше 120 одиниць, а третього – не менше 180. Сировина С повинна бути використана повністю.

Варіант 8

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 4	4 2 0	1 1 2	0 3 1	1200 800 1000
Прибуток	6	3	1	4

Продукції першого виду необхідно виробити не більше 150 одиниць, а третього – не менше 100. Сировина C повинна бути використана повністю.

Варіант 10

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 8	4 2 0	1 1 0	0 3 1	1000 1800 1000
Прибуток	6	1	1	4

Продукції першого виду необхідно виробити не більше 200 одиниць, а другого – не менше 100. Сировина C повинна бути використана повністю.

Варіант 12

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 0 2	0 3 1	600 800 600
Прибуток	2	3	5	4

Продукції першого виду необхідно виробити не менше 120 одиниць, а третього – не більше 180. Сировина С повинна бути використана повністю.

Варіант 14

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 6	4 0 3	1 1 2	0 3 1	1000 1200 1000
Прибуток	2	6	1	4

Продукції першого виду необхідно виробити не менше 150 одиниць, а другого – не більше 180. Сировина С повинна бути використана повністю.

Варіант 15

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 0 0	0 3 1	1200 800 600
Прибуток	2	1	5	4

Продукції другого виду необхідно виробити не менше 100 одиниць, а третього – не більше 200. Сировина С повинна бути використана повністю.

Варіант 17

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 0 2	0 3 1	900 1000 1600
Прибуток	3	5	1	4

Продукції другого виду необхідно виробити не більше 120 одиниць, а третього – не менше 180. Сировина А повинна бути використана повністю.

Варіант 19

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 0 4	4 2 0	1 1 2	0 3 1	900 800 1000
Прибуток	6	3	1	4

Продукції першого виду необхідно виробити не більше 150 одиниць, а третього – не менше 100. Сировина А повинна бути використана повністю.

Варіант 21

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 1 0	0 3 1	1000 1200 800
Прибуток	6	1	1	4

Продукції першого виду необхідно виробити не більше 200 одиниць, а другого – не менше 100. Сировина А повинна бути використана повністю.

Варіант 16

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 5	4 2 0	1 0 2	0 3 1	600 1200 2000
Прибуток	1	3	6	4

Продукції першого виду необхідно виробити не менше 120 одиниць, а третього – не більше 180. Сировина A повинна бути використана повністю.

Варіант 18

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 6	4 2 0	1 0 2	0 3 1	1000 1800 2000
Прибуток	1	6	2	4

Продукції першого виду необхідно виробити не менше 150 одиниць, а другого – не більше 180. Сировина A повинна бути використана повністю.

Варіант 20

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 4	4 2 0	1 0 0	0 3 5	1000 800 2000
Прибуток	2	1	5	4

Продукції другого виду необхідно виробити не менше 100 одиниць, а третього – не більше 200. Сировина А повинна бути використана повністю.

Варіант 22

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	0 2 0	1 0 2	0 3 1	1500 1000 600
Прибуток	2	5	1	3

Продукції другого виду необхідно виробити не більше 120 одиниць, а третього – не менше 180. Сировина С повинна бути використана повністю.

Варіант 23

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 4	4 2 0	1 1 2	0 3 1	1200 800 600
Прибуток	6	3	1	2

Продукції першого виду необхідно виробити не більше 150 одиниць, а третього – не менше 100. Сировина C повинна бути використана повністю.

Варіант 25

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 2	1 1 0	0 3 1	1500 1800 800
Прибуток	6	1	1	3

Продукції першого виду необхідно виробити не більше 200 одиниць, а другого – не менше 100. Сировина C повинна бути використана повністю.

Варіант 27

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 0 2	0 3 1	1600 800 600
Прибуток	2	3	5	1

Продукції першого виду необхідно виробити не менше 120 одиниць, а третього – не більше 180. Сировина С повинна бути використана повністю.

Варіант 29

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 6	4 0 3	1 4 2	0 3 1	1000 1200 1000
Прибуток	2	6	1	3

Продукції першого виду необхідно виробити не менше 150 одиниць, а другого – не більше 180. Сировина С повинна бути використана повністю.

Варіант 24

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 0 4	0 3 1	1200 800 600
Прибуток	2	1	5	4

Продукції другого виду необхідно виробити не менше 100 одиниць, а третього – не більше 200. Сировина С повинна бути використана повністю.

Варіант 26

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 0 5	0 3 1	900 1000 1600
Прибуток	3	5	1	2

Продукції другого виду необхідно виробити не більше 120 одиниць, а третього – не менше 180. Сировина А повинна бути використана повністю.

Варіант 28

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 0 4	4 2 0	1 0 2	0 3 1	900 800 1000
Прибуток	6	3	1	2

Продукції першого виду необхідно виробити не більше 150 одиниць, а третього – не менше 100. Сировина А повинна бути використана повністю.

Варіант 30

Сировина	Види продукції				Запаси
	1	2	3	4
А В С	5 1 3	4 2 0	1 1 2	0 3 1	1000 1200 800
Прибуток	6	1	2	3

Продукції першого виду необхідно виробити не більше 200 одиниць, а другого – не менше 100. Сировина А повинна бути використана повністю.