Розв’язати задачі цілочисельного програмування методом Гоморі

№1. На основі отриманих раніше оптимальних планів з рішеннями у дрібних числах розв’язати задачу цілочисельного програмування методом Гоморі. Звернути увагу на те, що розрахунок за допомогою ЕОМ може давати близькі до цілих чисел значення, а точні цілі числа отримуються, якщо розрахунок виконується вручну з дрібними числами, або якщо виконати спеціальну програму для ЕОМ.

№2. В результаті оптимізації симплекс-методом отримане розв’язання задачі ЛП табл. 1, яке отрібно привести до цілочисельного рішення методом Гоморі. Тут N – порядковий номер студента у групі. .

Таблиця 1

Оптимальний план

	Базисні змінні
		1/7		4/N
				5/N		6/7
	F					-60

№3. В результаті оптимізації симплекс-методом отримане розв’язання задачі ЛП табл. 2, яке отрібно привести до цілочисельного рішення методом Гоморі.

Таблиця 2.

Оптимальний план.

	Базисні змінні
			4N
					3N/7	26/7
	F					-73

 

№4. Знайти рішення таких задач лінійного цілочисельного програмування.

 

1. F(X) = X₁ +4 X₂ а Max; 2. F(X) = 2X₁ + X₂ а Max;

2X₁ – 4 X₂ <17,2 +A, X₁ – 2,1X₂ < 16,4+A,

10X₁ + 3X₂ <15+A, X₁ + 2X₂ >2+ A,

X₁,X₂ > 0 2X₁ + X₂ <16 +A,

X₁, X₂ – цілі числа. X₁, X₂ > 0,

X₁, X₂ – цілі числа.

 

3.F(X) = X₁ + 2X₂ а Min; 4. F(X) = 8X₁ + 6X₂ а Max;

2X₁ – 2,4X₂ <7,3 +A, 3X₁ - 5X₂ <11,5 +A,

4X₁ - 5X₂ <9+A, 4,2X₁ + X₂ <8+ A,

X₁, X₂ > 0, X₁,X₂ > 0,

X₁, X₂ – цілі числа.. X₁, X₂ – цілі числа.

 

№5. Розв¢язати задачу цілочисельного програмування методом відсікаючих площин (методом Гоморі).

F(X) = X₁ + 4 X₂ àMin;

2X₁ – 0,5*X₂ < 8,4;

5X₁ + (1/3)*X₂ < 15,3;

X₁,X₂ > 0; Х₁, X₂ – цілі числа.

 

№6. Розв¢язати задачу цілочисельного програмування методом відсікаючих площин (методом Гоморі).

F(X) = - 2X₁ - X₂ à Max;

X₁ + (1/2)*X₂ < 9,6;

X₁ + (1/3)*X₂ > 0,5;

X₁, X₂ > 0; X₁, X₂ – цілі числа.

 

№7. Розв¢язати задачу цілочисельного програмування методом відсікаючих площин (методом Гоморі).

F(X) = 8X₁ + 6X₂ à Min;

2X₁ + 5,2X₂ < 12,2;

4X₁ + 1,4X₂ < 10,5;

X₁,X₂ > 0; X₁, X₂ – цілі числа.

 

 

№1 min Z = x1+ x2 4x1+2x2³1 x1+3x2³1 3x1+4x2³1 x1³0, x2³0	№2   max Z = 3x1+4x2 3x1+2x2£8 x1+4x2£10 x1³0, x2³0
№3   max Z = x1+x2 3x1+2x2£5 x2£2 x1³0, x2³0	№4   max Z = 8x1+6x2 3x1+5x2£11 4x1+x2£8 x1³0, x2³0
№5   max Z = 2,5x1+4x2+3x3 4,5x1+3x2+5x3£14 2x1+6,3x2+x3£11 x1³0, x2³0, x3³0	№6   max Z = 2x1+4x2+x3+x4 x1+3x2+x4£4 2x1+x2£3 x2+4x3+x4£3 x1³0, x2³0, x3³0, x4³0
№7   max Z = x1–2x2 5x1–2x2£3 x1+x2³1 –3x1+x2£3 –3x1–3x2£3 x1³0, x2³0	№8   max Z = x1+2x2 x1–2x2£2 –2x1+x2£2 x1+x2£3 x1³0, x2³0
№9   max Z = 2x1+x2–3x3 x1+3x2–2x3£4 5x1–x3£12 2x1–x2+3x3£4 x1³0, x2³0, x3³0	№10   max Z = 3x1–4x2 –2x1+x2+x3=3 x1–2x2+x4=3 x1+0,5x2+x5=5 x1³0, x2³0, …, x5³0
№11   max Z = 3x1–x2+5x3+11x4–12x5 x1+2x4+x5=3 x2–3x4+4x5=2 x3+x4–2x5=1 x1³0, x2³0, …, x5³0	№12   max Z = 3x1+2x3+200x5+20x6 5x1+5x2+4x3+4x4£100 3x1+3x2+5x3+5x4+100x5+10x6£150 –2x2+10x5+11x6£0 –x4+10x5+x6£0 x1³0, x2³0, …, x6³0
№13   max Z = –2x1–x2+3x3 x1+x3£8 2x1+x2+3x3£29 3x1+x2–x3£3 –x1–x2+4x3£21 x1³0, x2³0, x3³0	№14   max Z = x1+x2+x3 x1+x2 £2 x1+2x3£3 x1+x2+x3£4 x1³0, x2³0, x3³0
№15   max Z = x1–3x2+2x3 3x1–x2+2x3³7 –2x1+4x2£12 –4x1+3x2+8x3£10 2x1+x2+2x3³4 x1³0, x2³0, x3³0	№16   max Z = x1+3x2+x3 x1+x2³1 x1+2x2–x3£4 2x1+3x2+x3³10 x2+2x3£6 x1³0, x2³0, x3³0
№17   max Z = x1+2x2-x3 2x1+x2–x3£8 x1+4x2+x3£9 –x1–2x2+2x3£3 3x1–x2–x3£6 x1³0, x2³0, x3³0	№18   max Z = 5x1+2x2–3x3+2x4+3x5–x6 5x1+6x2+4x3+2x4–3x5+5x6=11 5x1+5x2+7x3+3x5+5x6=10 2x1+2x2+2x3+3x5=4 x1³0, x2³0, …, x6³0
№19   max Z = 3x1–3x2–3x3–4x4+x5-2x6+x7+x8 2x1–x2–4x3–x4+3x5-5x6+x7=–1 5x1–x2+6x3–2x4–x5+4x6+x8=–2 x1³0, x2³0, …, x8³0	№20   max Z = x1+x2+1 –2x1+2x2+x3=2 x1–2x2+x4=3 x1+x2+x5=6 x1³0, x2³0, …, x5³0
№21   max Z = 2x1+3x2+x3 20x1+3x2–15x3³4 7x1–x2+5x3³32 4x1+10x2–3x3³50 x1³0, x2³0, x3³0	№22   max Z = 4x1+5x2+x3 3x1+2x2£10 x1+4x2£11 3x1+3x2+x3£13 x1³0, x2³0, x3³0
№23   max Z = 3x1–x2 3x1–2x2£3 –5x1–4x2£–10 2x1+x2£5 x1³0, x2³0	№24   max Z = –10x1–14x2–21x3 2x1+2x2+7x3³14 8x1+11x2+9x3³12 9x1+6x2+3x3³10 x1³0; x2³0; x3³0
№25   min Z = 120x1+42x2+8x3 20x1+7x2–3x3³4 15x1+2x2+x3³1 4x1+4x2+2x3³6 x1³0, x2³0, x3³0	№26   min Z = 4x1+20x2+4x3 x1+5x2+7x3³7 x1+11x2+x3³2 2x1+2x2–2x3³10 x1³0; x2³0, x3³0
№27   min Z = 3x1–5x2+3x3 x1–2x2+x3³3 5x1–4x2+2x3³16 2x1–x2+x3=10 x1³0, x2³0, x3³0	№28   max Z = x1+4x2 –x1+2x2£2 3x1+2x2£6 x1³0, x2³0
№29   max Z = 2x1–2x2+3x3–3x4 x1–2x2+x4=3 x2+x3–2x4=5 3x2+4x4£4 x1³0, x2³0, x3³0,x4³0	№30   min Z = x1+2x2+x5 x1+x2+x3+x4+x5=5 x2+x3+x4–x5=2 x3–x4+x5=1 xi³0, …, x5³0

 

 

Перевірте, як Ви засвоїли матеріал!:

1. Що таке цілочисельне програмування?

2. Які бувають задачі цілочисельного програмування?

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

4. Групи методів рішення задач цілочисельного програмування.

5. Які існують варіанти методу Гоморі? Чим вони відрізняються?

6. Сформулюйте підхід рішення цілком цілочисельних задач за 1-им методом Гоморі.

7. Що є ознакою відсутності рішення?

8. Розкрийте суть методу гілок та мереж.

9. Два шляхи вирішення задачі оптимального завантаження обладнання підприємства.

 

ТЕСТИ

1. Задача називається повністю цілочисельною, якщо умова цілочисельності накладена на:

а) праву частину обмежень

б) всі її змінні

в) хоча б на одну змінну

2. При застосуванні алгебраїчного методу відсікаючих площин (методу Гоморі) необхідно:

а) усі початкові обмеження задачі привести до вигляду з цілими коефіцієнтами і правими частинами

б) привести цільову функцію до цілочисельного вигляду

в) оптимізувати задачу симплексним методом

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

а) змінних кінцевих задач

б) змінних оптимальних задач

в) змінних початкових задач

г) цілих змінних кінцевих задач

4. При розв'язанні задачі цілочисельного програмування, якщо рішення не буде цілим, то:

а) вводимо додаткову змінну

б) вводимо додаткову цільову функцію

в) виводимо одну змінну

г) вводимо додаткове обмеження

д) задача розв'язана

5. За змінну, по якій буде вводитися відсікаюча площина, вибирається та, яка має:

а) найменшу дробову частину

б) найбільшу дробову частину

в) найменшу невід'ємну дробову частину

г) ціле значення

6. При розв'язанні задач симплексним методом з від'ємними базисними змінними вирішальний рядок вибирається по:

а) найбільшій по модулю від'ємній базисній змінній

б) найменшій по модулю від'ємній базисній змінній

в) найбільшій додатній базисній змінній

г) найбільшому значенню базисної змінної

7. При розв'язанні задач симплексним методом з від'ємними базисними змінними, щоб визначити вирішальний стовпчик потрібно:

а) базисні змінні помножити на відповідні коефіцієнти Z-рядка та вибрати найменше

б) коефіцієнти Z-рядка поділити на відповідні від'ємні коефіцієнти вирішального рядка і з отриманого вибрати найменше по модулю

в) базисні змінні поділити на відповідні коефіцієнти Z-рядка та вибрати найбільше

г) в Z-рядку вибрати найбільше по модулю значення

8. На перетині вирішального стовпчика і рядка знаходиться:

а) вирішальний елемент

б) оптимальний розв'язок задачі

в) змінна, по якій буде вводитись відсікаюча площина

г) Найбільша дробова частина

д) Точка локального екстремуму функції Z

9. В чому відмінність задач цілочисельного програмування від задач ЛП?

а) вільні члени обмежень –цілі;

б) коефіцієнти цільової функції – цілі числа;

в) змінні задачі – цілі числа;

г) коефіцієнти обмежень – цілі числа.

10. Для рішення цілочисельних задач лінійного програмування необхідно:

а) вільні члени системи обмежень зробити цілими;

б) коефіцієнти системи обмежень зробити цілими;

в) коефіцієнти цільової функції зробити цілими;

г) коефіцієнти при змінних зробити цілими.

11. За яким принципом вибирається рядок, за яким записується рівняння відсікаючої площини?

а) найбільший по модулю від’ємний вільний член;

б) найменше за модулем значення базисної змінної;

в) базисна змінна, що має найбільшу дробову частину;

г) базисна змінна, що має найменшу дробову частину.

12. Число – 6/5 має такі цілу і дробову частини:

а) –1; –1/5;

б) 0; –6/5;

в) –2; 4/5;

г) –2; 1/5.

13. Число 23/4 має такі цілу і дробову частини:

а) 5; 1/4;

б) 5; 3/4;

в) 6; –1/4;

г) 6; 3/4.

 

14. Як визначається поняття цілої частини нецілого числа?

а) найбільше додатне ціле число;

б) найменше від’ємне ціле число;

в) найбільше ціле число;

г) найменше ціле число.

15. За рядок, за змінною якого записується відсікаючи площина, вибирається:

а) який серед коефіцієнтів Z-рядка має найбільшу дробову частину;

б) який серед коефіцієнтів обмежень має найменшу дробову частину;

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

г) який серед коефіцієнтів цільової функції має найбільшу за модулем цілу частину;

д) який серед коефіцієнтів цільової функції має найменшу за модулем цілу частину.

 

16. Для якої із змінних буде записуватися відсікаюча площина

Х1	Х2	Х3	Х4
5,3	4,7	8/9	2,7

а) Х1

б) Х2

в) Х3

г) Х4

д) довільна.

 

17. Для якої із змінних буде записуватися відсікаюча площина

Х1	Х2	Х3	Х4	Х5
2/3	5/6	0,7	1/2	0,55

а) Х1

б) Х2

в) Х3

г) Х4

д) Х5

е) довільна.

18. Для якої із змінних буде записуватися відсікаюча площина

Х1	Х2	Х3	Х4
0,75	3/4	6,8	15/20

а) Х1

б) Х2

в) Х3

г) Х4

д) довільна.

 

19. З базису виключається змінна:

а) яка має найбільшу цілу частину;

б) найбільша по модулю від’ємна змінна;

в) найменша по модулю від’ємна змінна;

г) змінна, яка має найбільшу дробову частину

 

20. До базису включається змінна:

а) діляться вільні члени на коефіцієнти вирішального стовпчика і вибирається найменше відношення;

б) діляться вільні члени на коефіцієнти вирішального стовпчика і вибирається найбільше відношення;

в) діляться коефіцієнти Z-рядка на коефіцієнти вирішального рядка і вибирається найменше по модулю відношення;

г) діляться коефіцієнти Z-рядка на коефіцієнти вирішального рядка і вибирається найбільше по модулю відношення;