Графічний метод та симплекс метод розв’язування задач лінійного програмування

Мета: Навчитися розв’язувати задачі ЛП графічним та симплексним методами

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

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

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

Таблиця 4

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

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

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

Таблиця 2

Варіант							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. Скласти економіко-математичну модель задачі та розв’язати її графічним та симплексним методами

Фермер може вирощувати 4 культури на площі 80 га. Він вже вклав угоди на продаж певної продукції (обсяг продаж) і може придбати 250ц мінеральних добрив.

Площа просапних культур (соняшник, цукровий буряк, картопля, кукурудза) повинна бути 20 га.

Витрати праці та добрив, прибуток з 1 га наведено в таблиці 2.1.

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

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

Таблиця 2.1

Затрати праці, добрив і розмір прибутку в розрахунку на 1га посівів.

Варіант	Культури	Урожайність, ц/га	Обсяг продаж, ц	Затрати добрив на 1га, ц діючої речовини	Прибуток на 1га, грн.
1	Пшениця	30	300	4,2	160
Ячмінь	20		3,5	140
Овес	20		3,5	100
Соняшник	16		4,0	480
2	Пшениця	40		3,5	200
Цукровий буряк	220		5,0	50
Гречка	10	120	3,0	135
Овес	22		3,5	110
3	Просо	20	400	3,5	90
Гречка	12		2,5	120
Цукровий буряк	150		5,0	50
Овес	25		3,3	30
4	Ячмінь	20		3,5	60
Пшениця	20	250	3,5	70
Кукурудза	32		5,0	120
Просо	18		2,0	30
5	Картопля	230		6,0	380
Озиме жито	28	420	2,5	120
Ячмінь	20		2,9	90
Овес	25		2,8	80
6	Гречка	10	200	3,0	140
Ячмінь	30		3,0	110
Просо	25		2,0	120
Картопля	180		5,0	380
7	Пшениця	35	700	4,0	190
Кукурудза	33		3,0	180
Ячмінь	28		2,0	130
Овес	22		2,5	130
8	Озиме жито	37		3,0	160
Ячмінь	28		2,5	130
Овес	22	220	2,0	120
Цукровий буряк	250		5,0	130
9	Пшениця	40		4,0	150
Ячмінь	30	300	2,0	100
Овес	25		3,5	100
Кукурудза	35		5,0	235
10	Озиме жито	30	350	3,0	110
Просо	20		2,5	80
Ячмінь	20		2,5	110
Картопля	200		6,5	420
11	Кукурудза	34		3,5	240
Овес	24		3,0	90
Ячмінь	28		2,5	100
Просо	25	250	2,5	100
12	Гречка	15		2,0	140
Ячмінь	20	300	2,0	90
Просо	25		3,0	120
Картопля	180		6,0	480
13	Пшениця	25		2,5	150
Кукурудза	33		4,0	180
Ячмінь	28	280	2,5	130
Овес	22		2,0	110
14	Озиме жито	35		2,0	160
Ячмінь	28	280	2,5	130
Овес	22		2,0	120
Цукровий буряк	200		6,5	230
15	Пшениця	45		4,0	150
Ячмінь	30		2,0	100
Овес	20	200	2,5	90
Кукурудза	34		4,0	230
16	Озиме жито	30	350	3,0	110
Просо	20		2,5	80
Ячмінь	20		2,5	110
Картопля	200		6,5	420
17	Кукурудза	34		4,5	240
Пшениця	24	240	3,5	100
Ячмінь	28		2,5	110
Просо	20		2,0	100
18	Пшениця озима	30	300	4,0	160
Ячмінь	20		2,5	100
Пшениця яра	25		3,5	120
Соняшник	18		6,0	480
19	Пшениця	40	400	3,5	200
Цукровий буряк	210		6,5	70
Гречка	15		2,2	135
Овес	22		2,5	110
20	Просо	20	400	2,5	90
Гречка	12		2,5	120
Цукровий буряк	150		5,0	50
Овес	25		2,5	80
21	Ячмінь	20		2,5	60
Пшениця	20	250	3,5	70
Кукурудза	32		4,0	120
	Просо	18		2,4	30
22	Картопля	230		5,5	680
Озиме жито	28	420	2,0	120
Ячмінь	20		2,2	90
Овес	25		2,0	80
23	Гречка	10	200	2,5	140
Ячмінь	30		2,0	110
Просо	25		2,0	120
Картопля	180		5,0	380
24	Пшениця	35	700	3,0	190
Кукурудза	33		4,2	180
Ячмінь	28		2,0	130
Овес	22		2,0	130
25	Озиме жито	37		2,5	160
Ячмінь	28		2,5	130
Овес	22	220	2,0	120
Цукровий буряк	250		5,5	130
26	Пшениця	40		2,5	150
Ячмінь	30	300	2,0	100
Овес	25		2,5	100
Кукурудза	35		4,0	235
27	Пшениця озима	35		3,0	160
Кукурудза	33		2,0	180
Пшениця яра	28		2,0	130
Овес	22	220	2,0	130
28	Озиме жито	40		3,0	160
Ячмінь	28	280	2,5	130
Овес	22		2,0	120
Цукровий буряк	250		5,5	40
29	Пшениця	40		4,0	140
Ячмінь	30	300	2,0	80
Овес	25		2,5	50
Кукурудза	35		4,0	135
30	Пшениця	30	300	3,0	160
Ячмінь	20		2,0	140
Овес	20		2,5	100
Соняшник	16		5,0	480

Контрольні питання

4. 1. Прямі, що визначають багатокутник розв’язків при застосуванні графічного методу, Отримують шляхом:

1.  заміни в обмеженнях задачі знаків нерівностей на знаки рівнянь шляхом введення додаткових змінних;

2.  заміни в обмеженнях задачі знаків нерівностей на знаки рівнянь шляхом введення в ліву частину нерівностей додаткових невід’ємних змінних;

3.  заміни в обмеженнях задачі знаків нерівностей на знаки рівнянь;

4.  зведення задачі до канонічного вигляду;

2. При розв’язанні задачі лінійного програмування графічним методом вектор визначає:

1.  напрямок спадання цільової функції;

2.  напрямок зростання цільової функції;

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

4.  багатокутник розв’язків;

3. Вибрати невірне твердження. Якщо при розв’язанні задачі ЛП графічним методом пряма, що Перпендикулярна вектору С, співпадає з однією із сторін багатокутника розв’язків, то…

1.  точки даної сторони і є оптимальними розв’язками;

2.  задача має один оптимальний розв’язок;

3.  задача не має розв’язку;

4.  точка перетину вектора С з цією стороною є оптимальним розв’язком;

4. При побудові багатокутника розв’язків може бути утворена пуста область. В цьому випадку:

1.  задача не має розв’язку;

2.  задача має розв’язок;

3.  задача може мати чи не мати розв’язок;

4.  задача не завжди має розв’язок;

5. При розв’язків може бути утворений опуклий багатокутник, в цьому випадку:

1.  задача не має розв’язку;

2.  задача має розв’язок;

3.  задача може мати чи не мати розв’язку;

4.  задача може мати чи не мати розв’язку залежно від напрямку вектора С;

6. Вибрати невірну відповідь.

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

2.  при розв’язанні ЗЛП на max симплексним методом направляючий стовпчик визначає найбільший від’ємний коефіцієнт останнього рядка;

3.  генеральний елемент знаходиться на перетині направляючого рядка і стовпчика;

4.  при розв’язанні задачі лінійного програмування на max симплексним методом направляючий рядок визначає найменше оціночне відношення;

7. Вибрати невірну відповідь.

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

2.  при розв’язанні ЗЛП на max симплексним методом направляючий стовпчик визначає найменший від’ємний коефіцієнт останнього рядка;

3.  генеральний елемент знаходиться на перетині направляючого рядка і стовпчика;

4.  при розв’язанні задачі лінійного програмування на max симплексним методом направляючий рядок визначає найбільше оціночне відношення;

8. Вибрати вірну відповідь.

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

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

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

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

9. Вибрати невірне твердження.

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

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

3. при розв’язанні задачі лінійного програмування графічним методом вектор С, координати якого виписують з цільової функції, визначає напрямок зростання цільової функції;

4.  постановка задачі лінійного програмування в стандартній формі: знайти Max (min) значення лінійної цільової функції, змінні якої невід’ємні і задовольняють систему лінійних нерівностей;