Дата конвертації18.04.2017
Розмір33.5 Kb.
Типконтрольна робота

математичне програмування

1.4. Вирішити задачу з використанням графічного методу

,

Рішення

1) Багатокутник рішень.

Знайдемо точки, через які пройдуть граничні прямі [1, c. 20].

Будуємо багатокутник рішень.


2) Оптимальні точки.

Будуємо вектор нормалі, координати якого . Пересуваючи лінію рівня r в напрямку нормалі, знаходимо, що Z min знаходиться в точці A, Z max - в точці C.

3) Обчислення координат екстремумів.

Точка A - перетин прямих L 1 і L 3:

Точка C - перетин прямих L 2 і L 3:

4) Підрахунок оптимальних значень.

Відповідь: 88/3, 46.


2.4. Для виготовлення 2-х видів продукції P 1 і P 2 використовується 3 види ресурсів R 1, R 2, R 3. Запаси ресурсів, норми їх використання і прибуток від реалізації одиниці продукції наведені в таблиці. Знайти план виробництва продукції, якої б при заданих умовах забезпечував найбільший прибуток.

Завдання вирішити графічним способом і симплексним методом, скласти двоїсту задачу до вихідної і виписати її оптимальний план з останньої симплекс-таблиці вирішеною вихідної задачі.

P i

R i

Р 1 Р 2

запаси

ресурсів

R 1 2 5 80
R 2 4 3 91
R 3 1 4 68
прибуток 15 12

Рішення

Складемо математичну модель задачі. Шуканий випуск продукції P 1 позначимо через x 1, продукції P 2 - через x 2. Оскільки є обмеження на виділені ресурси кожного виду, змінні x 1, x 2 повинні задовольняти такій системі нерівностей:

Загальна вартість продукції при цьому складає: z = 15x 1 + 12x 2.

За своїм економічним змістом змінні x 1, x 2 більше 0.

Отже, приходимо до математичної задачі: серед всіх невід'ємних розв'язків системи нерівностей потрібно знайти таке, при якому функція z прийме максимальне значення.

Вирішимо задачу графічним способом.

1) Багатокутник рішень

Знайдемо точки, через які пройдуть граничні прямі [1, c. 20].

Будуємо багатокутник рішень.

2) Оптимальні точки.

Будуємо вектор нормалі, координати якого . Пересуваючи лінію рівня r в напрямку нормалі, знаходимо, що F min знаходиться в точці O, F max - в точці C.

3) Обчислення координат екстремумів.

Точка C - перетин прямих L 1 і L 2:

4) Підрахунок оптимальних значень.

Відповідь: 4881/14.

Вирішимо задачу ЛП симплекс-методом [1, c. 30].

Запишемо цю задачу в формі основного завдання лінійного програмування. Для цього перейдемо до обмежень-рівнянь. Введемо додаткові 3 змінні - x 3, x 4, x 5, в результаті чого обмеження запишуться у вигляді рівнянь:

Побудуємо початкову симплекс-таблицю, де Q - невід'ємне відношення стовпця плану до ключового стовпця.

базис C б план 15 12 0 0 0 Q
x 1 x 2 x 3 x 4 x 5
1 x 3 0 80 2 5 1 0 0 40
2 x 4 0 91 4 3 0 1 0 91/4
3 x 5 0 68 1 4 0 0 1 68
4 0 -15 -12 0 0 0 -

Cтолбік 1 є ключовим, оскільки він містить мінімальний від'ємний елемент

Рядок 2 є ключовою, оскільки в ньому мінімальне Q 2 = 91/4.

Ключовий елемент знаходиться на їх перетині і рівний числу 4.

Замість вектора x 4, який виводимо з базису, вводимо вектор x 1.

Ділимо ключовий рядок на ключовий елемент 4.

Множимо його на 15 і додаємо до 4 рядку.

Множимо його на -2 і додаємо до 1 рядку.

Множимо його на -1 і додаємо до 3 рядку.

Отримаємо наступну симплекс-таблицю.

базис C б план 15 12 0 0 0 Q
x 1 x 2 x 3 x 4 x 5
1 x 3 0 69/2 0 7/2 1 -1/2 0 69/7
2 x 1 15 91/4 1 3/4 0 1/4 0 91/3
3 x 5 0 181/4 0 13/4 0 -1/4 1 181/13
4 1365/4 0 -3/4 0 15/4 0 -

Cтолбік 2 є ключовим, оскільки він містить мінімальний від'ємний елемент

Рядок 1 є ключовим, оскільки в ньому мінімальне Q 1 = 69/7.

Ключовий елемент знаходиться на їх перетині і рівний числу 7/2.

Замість вектора x 3, який виводимо з базису, вводимо вектор x 2.

Ділимо ключовий рядок на ключовий елемент 7/2.

Множимо його на 3/4 і додаємо до 4 рядку.

Множимо його на -3/4 і додаємо до 2 рядку.

Множимо його на -13/4 і додаємо до 3 рядку.

Отримаємо остаточну симплекс-таблицю.

базис C б план 15 12 0 0 0
x 1 x 2 x 3 x 4 x 5
1 x 2 12 69/7 0 1 2/7 -1/7 0
2 x 1 15 215/14 1 0 -3/14 5/14 0
3 x 5 0 185/14 0 0 -13/14 3/14 1
4 4881/14 0 0 3/14 51/14 0

Складемо двоїсту задачу до даної [1, c. 88]. Її коефіцієнти складаються з вихідної шляхом транспонування. Систему обмежень складуть коефіцієнти оптимізує функції. Коефіцієнтами оптимізує функції z будуть вільні члени вихідної системи. Знаки нерівностей зміняться на протилежні. Оптимизирующая функція - мінімум функції. Двоїста задача буде полягати в тому, щоб скласти такий план виробництва, при якому витрати ресурсів будуть мінімальними.

Отже, через y 1 позначимо вартість одиниці ресурсу 1 виду або А 1, y 2 - вартість одиниці А 2, y 3 - вартість одиниці А 3. тоді - вартість продукції Р 1, яка не може бути дешевше ніж 15 у.Д.Є. (Умовних грошових одиниць), тобто перша нерівність: . аналогічно .

Загальні втрати ресурсів виражаються оптимізує функцією:

при .

Отже, математично це запишеться так:


З 4 рядка останньої симплекс-таблиці віпісиваем оптимальний план, де y 1 = x 3, y 2 = x 4, y 3 = x 5, тобто .

.

значення відповідає значенню 4881/14, що знаходиться в 0 рядку планового стовпчика.

З економічної точки зору нульове значення змінної у 3 означає, що для мінімальних витрат вартість ресурсов R 3 повинна дорівнювати 0.

Таким чином, продукції P 1 і P 2 потрібно виробляти 215/14 і 69/14 од. відповідно. Максимальний прибуток при цьому складе 4881/14 у.д.е.

відповідь:


3.4. Знайти оптимальний план транспортної задачі.

Рішення

Запишемо умову задачі в економічному вигляді на підставі таблиці, де задані пункти відправлення та призначення, запаси і потреби [1, c. 135].

пункти відправлення пункти призначення запаси
B 1 B 2 B 3 B 4
A 1 9 8 7 4 220
A 2 5 6 10 3 120
A 3 2 3 5 7 150
потреби 200 200 140 180 720 \ 490

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

1) Діагональний метод

Знайдемо опорний план діагональним методом [1, c. 140].

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
200 20 - 0 +
2 120 5 6 10 3 -2
120
3 150 2 3 5 7 -5
60 + 90 -
4 230 0 0 0 0 -10
50 + 180 -
b 9 8 10 10

Вартість початкового плану перевезення:

z 0 = 200 · 9 + 20 · 8 + 120 · 6 + 60 · 3 + 90 · 5 + 50 · 0 + 180 · 0 = 3310.

Для базисних клітин система потенціалів така:

a 1 + b 1 = 9; a 1 + b 2 = 8;

a 2 + b 2 = 6;

a 3 + b 2 = 3; a 3 + b 3 = 5;

a 4 + b 3 = 0; a 4 + b 4 = 0.

Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 3 = 0 + 10 = 10> 7 [3]; a 1 + b 4 = 0 + 10 = 10> 4 [6];

a 2 + b 1 = -2 + 9 = 7> 5 [2]; a 2 + b 3 = -2 + 10 = 8 ≤ 10; a 2 + b 4 = -2 + 10 = 8> 3 [5];

a 3 + b 1 = -5 + 9 = 4> 2 [2]; a 3 + b 4 = -5 + 10 = 5 ≤ 7;

a 4 + b 1 = -10 + 9 = -1 ≤ 0; a 4 + b 2 = -10 + 8 = -2 ≤ 0;

Для клітини A 1 B 4 (з тих, що не виконується умова оптимальності) різниця потенціалів найбільша, тому для неї робимо цикл перерахунку на мінімальну величину негативних вершин: min (20, 90, 180) = 20.


Переходимо до наступної ітерації.

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
200 - 20 +
2 120 5 6 10 3 4
0 + 120 -
3 150 2 3 5 7 1
80 + 70 -
4 230 0 0 0 0 -4
70 + 160 -
b 9 2 4 4

Вартість 1 плану перевезення:

z 1 = 200 · 9 + 20 · 4 + 120 · 6 + 80 · 3 + 70 · 5 + 70 · 0 + 160 · 0 = 3190.

Для базисних клітин система потенціалів така:

a 1 + b 1 = 9; a 1 + b 4 = 4;

a 2 + b 2 = 6;

a 3 + b 2 = 3; a 3 + b 3 = 5;

a 4 + b 3 = 0; a 4 + b 4 = 0.

Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 2 = 0 + 2 = 2 ≤ 8; a 1 + b 3 = 0 + 4 = 4 ≤ 7;

a 2 + b 1 = 4 + 9 = 13> 5 [8]; a 2 + b 3 = 4 + 4 = 8 ≤ 10; a 2 + b 4 = 4 + 4 = 8> 3 [5];

a 3 + b 1 = 1 + 9 = 10> 2 [8]; a 3 + b 4 = 1 + 4 = 5 ≤ 7;

a 4 + b 1 = -4 + 9 = 5> 0 [5]; a 4 + b 2 = -4 + 2 = -2 ≤ 0;

Для клітини A 2 B 1 (з тих, що не виконується умова оптимальності) різниця потенціалів найбільша, тому для неї робимо цикл перерахунку на мінімальну величину негативних вершин: min (200, 160, 70, 120) = 70.

Переходимо до наступної ітерації.

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
130 - 90 +
2 120 5 6 10 3 -4
70 + 50 -
3 150 2 3 5 7 -7
150
4 230 0 0 0 0 -4
0 + 140 90 -
b 9 10 4 4

Вартість 2 плану перевезення:

z 2 = 130 · 9 + 90 · 4 + 70 · 5 + 50 · 6 + 150 · 3 + 140 · 0 + 90 · 0 = 2630.

Для базисних клітин система потенціалів така:

a 1 + b 1 = 9; a 1 + b 4 = 4;

a 2 + b 1 = 5; a 2 + b 2 = 6;

a 3 + b 2 = 3;

a 4 + b 3 = 0; a 4 + b 4 = 0.


Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 2 = 0 + 10 = 10> 8 [2]; a 1 + b 3 = 0 + 4 = 4 ≤ 7;

a 2 + b 3 = -4 + 4 = 0 ≤ 10; a 2 + b 4 = -4 + 4 = 0 ≤ 3;

a 3 + b 1 = -7 + 9 = 2 ≤ 2; a 3 + b 3 = -7 + 4 = -3 ≤ 5; a 3 + b 4 = -7 + 4 = -3 ≤ 7;

a 4 + b 1 = -4 + 9 = 5> 0 [5]; a 4 + b 2 = -4 + 10 = 6> 0 [6];

Для клітини A 4 B 2 (з тих, що не виконується умова оптимальності) різниця потенціалів найбільша, тому для неї робимо цикл перерахунку на мінімальну величину негативних вершин: min (50, 130, 90) = 50.

Переходимо до наступної ітерації.

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
80 - 140 +
2 120 5 6 10 3 -4
120
3 150 2 3 5 7 -1
0 + 150 -
4 230 0 0 0 0 -4
50 + 140 40 -
b 9 4 4 4

Вартість 3 плану перевезення:

z 3 = 80 · 9 + 140 · 4 + 120 · 5 + 150 · 3 + 50 · 0 + 140 · 0 + 40 · 0 = 2330.

Для базисних клітин система потенціалів така:


a 1 + b 1 = 9; a 1 + b 4 = 4;

a 2 + b 1 = 5;

a 3 + b 2 = 3;

a 4 + b 2 = 0; a 4 + b 3 = 0; a 4 + b 4 = 0.

Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 2 = 0 + 4 = 4 ≤ 8; a 1 + b 3 = 0 + 4 = 4 ≤ 7;

a 2 + b 2 = -4 + 4 = 0 ≤ 6; a 2 + b 3 = -4 + 4 = 0 ≤ 10; a 2 + b 4 = -4 + 4 = 0 ≤ 3;

a 3 + b 1 = -1 + 9 = 8> 2 [6]; a 3 + b 3 = -1 + 4 = 3 ≤ 5; a 3 + b 4 = -1 + 4 = 3 ≤ 7;

a 4 + b 1 = -4 + 9 = 5> 0 [5];

Для клітини A 3 B 1 (з тих, що не виконується умова оптимальності) різниця потенціалів найбільша, тому для неї робимо цикл перерахунку на мінімальну величину негативних вершин: min (80, 40, 150) = 40.

Переходимо до наступної ітерації.

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
40 - 0 + 180
2 120 5 6 10 3 -4
120
3 150 2 3 5 7 -7
40 + 110 -
4 230 0 0 0 0 -10
90 + 140 -
b 9 10 10 4

Вартість 4 плану перевезення:

z 4 = 40 · 9 + 180 · 4 + 120 · 5 + 40 · 2 + 110 · 3 + 90 · 0 + 140 · 0 = 2090.

Для базисних клітин система потенціалів така:

a 1 + b 1 = 9; a 1 + b 4 = 4;

a 2 + b 1 = 5;

a 3 + b 1 = 2; a 3 + b 2 = 3;

a 4 + b 2 = 0; a 4 + b 3 = 0;

Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 2 = 0 + 10 = 10> 8 [2]; a 1 + b 3 = 0 + 10 = 10> 7 [3];

a 2 + b 2 = -4 + 10 = 6 ≤ 6; a 2 + b 3 = -4 + 10 = 6 ≤ 10; a 2 + b 4 = -4 + 4 = 0 ≤ 3;

a 3 + b 3 = -7 + 10 = 3 ≤ 5; a 3 + b 4 = -7 + 4 = -3 ≤ 7;

a 4 + b 1 = -10 + 9 = -1 ≤ 0; a 4 + b 4 = -10 + 4 = -6 ≤ 0;

Для клітини A 1 B 3 (з тих, що не виконується умова оптимальності) різниця потенціалів найбільша, тому для неї робимо цикл перерахунку на мінімальну величину негативних вершин: min (40, 110, 140) = 40.

Переходимо до наступної ітерації.

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
40 180
2 120 5 6 10 3 -1
120
3 150 2 3 5 7 -4
80 70
4 230 0 0 0 0 -7
130 100
b 6 7 7 4

Вартість 5 плану перевезення:

z 5 = 40 · 7 + 180 · 4 + 120 · 5 + 80 · 2 + 70 · 3 + 130 · 0 + 100 · 0 = 1970. Наступні

Для базисних клітин система потенціалів така:

a 1 + b 3 = 7; a 1 + b 4 = 4;

a 2 + b 1 = 5;

a 3 + b 1 = 2; a 3 + b 2 = 3;

a 4 + b 2 = 0; a 4 + b 3 = 0;

Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 1 = 0 + 6 = 6 ≤ 9; a 1 + b 2 = 0 + 7 = 7 ≤ 8;

a 2 + b 2 = -1 + 7 = 6 ≤ 6; a 2 + b 3 = -1 + 7 = 6 ≤ 10; a 2 + b 4 = -1 + 4 = 3 ≤ 3;

a 3 + b 3 = -4 + 7 = 3 ≤ 5; a 3 + b 4 = -4 + 4 = 0 ≤ 7;

a 4 + b 1 = -7 + 6 = -1 ≤ 0; a 4 + b 4 = -7 + 4 = -3 ≤ 0;

Умова оптимальності виконується для всіх клітин, отже останній план є оптимальним. Його вартість становить 1970 у.о. Слід зауважити, що споживачі не дополучат 230 од. вантажу.

2) Метод мінімальної вартості


Знайдемо опорний план методом мінімальної вартості [1, c. 142].

B

A

1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
40 180
2 120 5 6 10 3 -1
120
3 150 2 3 5 7 -4
80 70
4 230 0 0 0 0 -7
130 100
b 6 7 7 4

Вартість початкового плану перевезення:

z 0 = 40 · 7 + 180 · 4 + 120 · 5 + 80 · 2 + 70 · 3 + 130 · 0 + 100 · 0 = 1970. Наступні

Для базисних клітин система потенціалів така:

a 1 + b 3 = 7; a 1 + b 4 = 4;

a 2 + b 1 = 5;

a 3 + b 1 = 2; a 3 + b 2 = 3;

a 4 + b 2 = 0; a 4 + b 3 = 0;

Оскільки кількість змінних менше, ніж рівнянь, то покладемо: a 1 = 0. Перевіряємо умову оптимальності для вільних клітин: a + b ≤ c

a 1 + b 1 = 0 + 6 = 6 ≤ 9; a 1 + b 2 = 0 + 7 = 7 ≤ 8;

a 2 + b 2 = -1 + 7 = 6 ≤ 6; a 2 + b 3 = -1 + 7 = 6 ≤ 10; a 2 + b 4 = -1 + 4 = 3 ≤ 3;

a 3 + b 3 = -4 + 7 = 3 ≤ 5; a 3 + b 4 = -4 + 4 = 0 ≤ 7;

a 4 + b 1 = -7 + 6 = -1 ≤ 0; a 4 + b 4 = -7 + 4 = -3 ≤ 0;

Умова оптимальності виконується для всіх клітин, отже останній план є оптимальним. Його вартість становить 1970 у.о. Слід зауважити, що споживачі не дополучат 230 од. вантажу.

Також зазначаємо збіг рішень двома методами.

Відповідь: 1970. Наступні


література

1. Акулич І. Л. Математичне програмування в прикладах і завданнях. М .: Вища школа, 1986. - 319 с.

2. Костевич Л. С. Математичне програмування. Мн .: Нове знання, 2003. - 424 с.