Contribution to International Economy

  • Знайти значення вектора позитивних параметрів Хi, які
Білет №11. Для системи, яка описується математичною моделлю
Х1+2Х2-Х3+x4=3
X1-X2+2X3-X4≤6 (1)
2X1-2X2+3X3+3X4≥9
L(x) = -3X1+X2-3X3+4X4 -> max (2)
необхідно знайти значення вектора позитивних параметрів Хi, які
будуть задовольняти систему (1) та доставляти лінійній функції (2)
максимальне значення. При рішенні задачі виконати слідуючі дії:
1) привести систему (1) до канонічного виду; (10 балів)
2) побудувати симплексну таблицю; (15 балів)
3) визначити начальний план ; (5 балів)
4) виконати оцінку опорного плану; (5 балів)
5) визначити новий план; (15 балів)
Розв’язання:
1. Щоб привести систему (1) до канонічного виду, треба ввести додатні штучні змінні х5 та х6. Щоб перетворити другу нерівність у рівняння, додамо до лівої частини х5, а щоб перетворити у рівняння третю нерівність, віднімемо від до неї зліва х6.
Одержимо систему рівнянь:
Х1+2Х2-Х3+x4=3
X1-X2+2X3-X4+Х5=6
2X1-2X2+3X3+3X4-Х6=9
Введемо в базис змінні х4, х5 і х1, виразимо через х2, х3 і х6
х1=-8х2+6х3-х6
х4=3+6х2-5х3+х6
х5=9+15х2-13х3+2х6.
Виключимо з цільової функції змінні х1, х4, х5, одержимо:
L(x)=12+49х2-41х3+7х6 ─> max.
Ця функція досягає максимуму, коли лінійна форма L1(x)=- 12-49х2+41х3-7х6 досягає мінімуму. Отже задача лінійного програмування у канонічній формі записується так: знайти мінімум лінійної форми L1(x)= 12-49х2+41х3-7х6 для невід’ємних х1, x2, x3, x4, x5, x6, що задовольняють рівняння:
х1=-8х2+6х3-х6
х4=3+6х2-5х3+х6
х5=9+15х2-13х3+2х6.
2. Побудуємо симплексну таблицю:
Базисні невідомі Вільні члени X1 X2 X3 X4 X5 X6
Þ X4 3 1 2 -1 1 0 0
X5 6 1 -1 2 -1 1 0
X1 9 2 -2 3 3 0 -1
Форма L1 12 0 49 -41 0 0 7
Ý
3. Початковий план Х=(9,0,0,3,6,0), в якості базису вибрано х1, х4, х5. Цьому плану відповідає значення лінійної форми L1(x)=12..
4. У останньому рядку є додатній елемент 49, отже цей план може бути поліпшений. Виберемо розрішаючий стовпчик з елементом 49 і знайдемо додатній елемент у цьому стовпчику - це буде 2. В новий базис введемо х2 замість х4. Виділений рядок розділимо на 2 і результат запишеио в нову таблицю. Решту рядків перетворюємо так, щоб у відповідних клітинках цього стовпчика з’явилися нулі.
Базисні невідомі Вільні члени X1 X2 X3 X4 X5 X6
X2 1,5 0,5 1 -0,5 0,5 0 0
X5 7,5 1,5 0 1,5 -0,5 1 0
X1 12 3 0 2 4 0 -1

Форма L1 -61,5 -24,5 0 -16,5 -24,5 0 7

Зроблені перетворення зменшили значення лінійної форми до -61,5, новий опорний план (12,1.5,0,0,7.5,0). У останньому рядку є тільки один додатній член 7, але у відповідному стовпчику немає додатніх членів, тому Х7 не можна вводити в базис, отже цей опорний план не може бути поліпшений. Знайдений план оптимальний, цільова функція L набуває максимльного значення 61,5. при Х1=12: Х2=1,5; Х3=0; Х4=0; Х5=7,5; Х6=0.

Білет №12. Для системи, яка описується математичною моделлю
3Х1-2Х2+Х3-x4≥3
4X1-X2+3X3-2X4≤10 (1)
7X1-3X2-4X3+X4+Х5=5
L(x) = 4X1-X2+2X3+X4+3Х5 -> max (2)
необхідно знайти значення вектора позитивних параметрів Хi, які
будуть задовольняти систему (1) та доставляти лінійній функції (2)
максимальне значення. При рішенні задачі виконати слідуючі дії:
1) привести систему (1) до канонічного виду; (10 балів)
2) побудувати симплексну таблицю; (15 балів)
3) визначити начальний план ; (5 балів)
4) виконати оцінку опорного плану; (5 балів)
5) визначити новий план; (15 балів)
Розв’язання:
1. Щоб привести систему (1) до канонічного виду, треба ввести додатні штучні змінні х6 та х7. Щоб перетворити першу нерівність у рівняння, віднімемо від лівої частини х6, а щоб перетворити у рівняння другу нерівність, додамо до неї зліва х7.
Одержимо систему рівнянь:
3Х1-2Х2+Х3-x4-Х6=3
4X1-X2+3X3-2X4+Х7=10
7X1-3X2-4X3+X4+Х5=5
Введемо в базис змінні х3, х4 і х7, виразимо їх через х1, х2, х5 і х6
х3=-3+10/3х1+1/3х2+1/3х5-1/3х6
х4=-7+19/3х1-5/3х2+1/3х5-4/3х6
х7=10-4х1+ч2-3х3+2х4
Виключимо з цільової функції змінні х3, х4, х7, одержимо:
L(x)=-3+17х1-2х2+4х5-2х6 ─> max.
Ця функція досягає максимуму, коли лінійна форма L1(x)= 13-17х1+2х2-4х5+2х6 досягає мінімуму.
Отже задача лінійного програмування у канонічній формі записується так: знайти мінімум лінійної форми L1(x)= 13-17х1+2х2-4х5+2х6 для невід’ємних х1, x2, x3, x4, x5, x6, х7, що задовольняють рівняння:
3Х1-2Х2+Х3-x4-Х6=3
4X1-X2+3X3-2X4+Х7=10
7X1-3X2-4X3+X4+Х5=5
2. Побудуємо симплексну таблицю:
Базисні невідомі Вільні члени X1 X2 X3 X4 X5 X6 X6
X3 4 3 -2 1 -1 0 -1 0
X7 10 4 -2 3 -2 0 0 1
Þ X4 5 7 3 -4 1 1 0 0
Форма L1 13 -17 2 0 0 -4 2 0
Ý
3. Початковий план Х=(0,0,4,5,0,10), в якості базису вибрано х3, х4, х7. Цьому плану відповідає значення лінійної форми L1(x)=13..
4. У останньому рядку є додатній елемент 2, отже цей план може бути поліпшений. Виберемо розрішаючий стовпчик з елементом 2 і знайдемо додотній елемент у цьому стовпчику - це буде 3. В новий базис введемо х2 замість х4. Виділений рядок розділимо на 3 і результат запишеио в нову таблицю. Решту рядків перетворюємо так, щоб у відповідних клітинках цього стовпчика з’явилися нулі.
Базисні невідомі Вільні члени X1 X2 X3 X4 X5 X6 X7
X3 22/3 23/3 0 -5/3 -1/3 2/3 -1 -1
X7 40/3 26/3 0 1/3 -4/3 2/3 0 1
X2 5/3 7/3 1 -4/3 1/3 1/3 0 0

Форма L1 29/3 -65/3 0 8/3 -2/3 -14/3 2 0


Зроблені перетворення зменшили значення лінійної форми до 9,7 новий опорний план (0,1.7,7.3,0,0,0.0,13.3). У останньому рядку є два додатні члени: 2 - у відповідному стовпчику немає додатніх членів, тому Х6 не можна вводити в базис; 8/3 – йому відповідає змінна Х3, яка вже введена в базис. Отже цей опорний план не може бути поліпшений. Знайдений план оптимальний, цільова функція L набуває максимльного значення -9,7 при Х1=0: Х2=1,75; Х3=7,3; Х4=0; Х5=0; Х6=0; Х7=13,3.


Другие работы по теме: