Рішення. 1. Побудуємо математичну модель задачі

1. Побудуємо математичну модель задачі.

Позначимо через кількість машин типу А і B відповідно, через
f – загальну продуктивність.

Тоді математична модель задачі матиме вид:

2. Симплексним методом розв’язуємо цю задачу без урахування умови цілочисловості.

Одержуємо оптимальне рішення: . Цьому рішенню відповідає наступна симплекс-таблиця.

Таблиця 6.1
Б	с Б	b	x 1	x 2	x 3	x 4
–2	–3
x 2	–3	17/2	3/4		1/4
x 4		35/2	–3/4		–5/4
	–51/2	–1/4		–3/4

Рішення не задовольняє умові цілочисловості, тому що має дробові компоненти: 17/2, 35/2.

3. Компоненти 17/2, 35/2 мають однакові дробові частини, які дорівнюють 1/2. Тому обираємо одну з цих компонент, наприклад 17/2.

Рівняння відповідного рядка симплекс-таблиці (табл. 6.1):

,

де – базисна змінна, , – небазисні (вільні) змінні.

Виражаємо базисну змінну через небазисні змінні:

.

Записуємо нерівність відсікання Гоморі:

.

Знаходимо дробові частини чисел:

, , .

Отже, нерівність відсікання Гоморі має вид:

.

До лівої частини нерівності додаємо змінну і записуємо таке
рівняння:

або .

4. Включаємо це рівняння в систему обмежень, отриману на останньому кроці розв’язання задачі без умови цілочисловості (див. табл. 6.1), і продовжуємо вирішувати задачу, використовуючи симплекс-метод.

Так, розширена матриця системи обмежень матиме вид:

.

Приводимо дану матрицю до одиничного базису з невід’ємними вільними членами

.

Одержуємо опорний план: .

Перевіряємо даний опорний план на оптимальність за допомогою симплекс-таблиці.

Таблиця 6.2
Б	с Б	b	x 1	x 2	x 3	x 4	x 5
–2	–3
x 2	–3
x 4					–1		–1
x 1	–2	2/3			1/3		–4/3
		–76/3			–2/3		–1/3

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

5. Обираємо дробову компоненту 2/3.

Рівняння відповідного рядка симплекс-таблиці (табл. 7.2):

,

де – базисна змінна, , – небазисні змінні.

Виражаємо базисну змінну через небазисні змінні:

.

Записуємо нерівність відсікання Гоморі:

.

Знаходимо дробові частини чисел:

, , .

Отже, нерівність відсікання Гоморі має вид:

.

До лівої частини нерівності додаємо змінну і записуємо таке
рівняння:

або .

6. Включаємо це рівняння в систему обмежень (див. табл. 6.2) і продовжуємо розв’язувати задачу, використовуючи симплекс-метод.

Так, розширена матриця системи обмежень буде мати вид:

.

Приводимо дану матрицю до одиничного базису з невід’ємними вільними членами

.

Одержуємо опорний план: .

Перевіряємо даний опорний план на оптимальність за допомогою симплекс-таблиці.

Таблиця 6.3

Б	с Б	b	x 1	x 2	x 3	x 4	x 5	x 6
–2	–3
x 2	–3				–1/2			3/2
x 4					–1/2			–3/2
x 1	–2							–2
x 5					1/2			–3/2
		–25			–1/2			–1/2

Опорний план є оптимальним, тому що в останньому рядку табл. 6.3 всі оцінки недодатні. Крім того, задовольняє умові цілочисловості.

Оптимальне значення цільової функції: .

Отже, при оптимальному цілочисельному рішенні , тобто максимальну продуктивність 25 т сортового зерна за зміну можна одержати придбанням двох машин типу A і семи машин типу B; при цьому з виділених коштів залишки дорівнюють 0, незайнята площа приміщення складе 19 кв. м (п’ятий і шостий компоненти змістовного значення не мають).

Дата добавления: 2014-11-06