       О проекте

       Цены и условия

       Готовые работы

       Заказ новых работ

       Вакансии

       Контакты

       Поиск рефератов

Р е к л а м а:

Все вопросы, связанные с заказом новых или уже готовых работ, Вы можете задать по тел.:
8 (044) 519-19-81

Информация о работе ID: 3693

Название	Задачі з математичного програмування
NEW! Просмотр ознакомительной версии!	Вы имеете возможность просмотреть материал с сайта http://infoworks.com.ua перед оформлением заказа! Предварительный просмотр ...
Раздел	Математическое программирование
Тип работы	Задача
Объем	9 стр.
Цена	20 у.е.
Размер	91 kb
Добавлена	11.12.2007
Купить	Нажмите здесь
Содержание	Задача 1.Розв’язати задачу лінійного програмування графічним методом Знайдемо точку мінімума Задача 2.Розв’язати симплекс-методом задачу лінійного програмування x1 x2 x3 3 -1 1 x4 10 -1 2 x5 36 4 1 Lmin 0 -2 3 Вибрали генеральний стовпчик, оскільки 3>0. генеральну строку берем по х3, оскільки(3/1)<(10/2)<(36/1) Перерахуємо таблицю x1 x3 x2 3 -1 1 x4 4 1 -2 x5 33 5 -1 Lmin -9 1 -3 Вибрали генеральний стовпчик, оскільки 1>0. генеральну строку берем по х4, оскільки(4/1)<(33/5) Перерахуємо таблицю x4 x3 x2 7 1 -1 x1 4 1 -2 x5 13 -5 9 Lmin -13 -1 -1 Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-13 x2=7 x1=4 x5=13 x4=x3=0 Задача 3. Для даної задачі лінійного програмування побудувати двоїсту, розв’язати одну з пари двоїстих задач симплекс-методом і за її розв’язком знайти розв’язок двоїстої до неї Запишемо двоїсту задачу Розв'яжемо пряму задачу симплекс-методом x1 x2 x3 3 -1 1 x4 10 -1 2 x5 36 6 1 Lmin 0 1 -9 Вибрали генеральний стовпчик, оскільки 1>0. генеральну строку берем по х5, оскільки 6>0 Перерахуємо таблицю x5 x2 x3 9 1/6 7/6 x4 46 1/6 13/6 x1 6 1/6 1/6 Lmin -6 -1/6 -55/6 Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-6, а Lmax=6 x2=0 x1=6 x5=0 x4=46 x3=9 х1 х2 х3 х4 х5 у4 у5 у1 у2 у3 y1=0 y3=1/6 y2=0 y5=55/6 y4=0 F=6 Задача 4. Розв’язати методом потенціалів транспортну задачу Q1 Q2 Q3 Q4 Q5 a P1 8 6 7 3 4 50 P2 7 4 9 3 4 50 P3 6 1 4 5 2 55 P4 7 8 3 4 2 50 b 35 30 50 25 65 Знайдемо опорний план методом найменшої вартості Q1 Q2 Q3 Q4 Q5 a P1 8(19) 6 (2) 7 (17) 3 (15) 4 (10) 50 P2 7 (20) 9 (3) 9 (18) 3 (16) 4 (11) 50 P3 6 (6) 1 (1) 4 (7) 5 (8) 2 (5) 55 P4 7 (13) 8 (4) 3 (12) 4 (14) 2 (9) 50 b 35 30 50 25 65 Цифри в дужках вказують порядок заповнення елементів в матриці Х0 Х0 0 0 25 25 0 25 25 0 35 0 15 0 0 15 35 0 0 30 0 0 25 30 25 0 0 0 10 0 40 40 10 0 35 30 10 25 25 0 0 25 0 40 15 0 0 Заповнено 8 клітинок(5+4-1), отже план невироджений Відповідне значення цільової функції дорівнює L=257+253+357+159+301+252+103+402=1020 Знайдемо потенціали: Нехай u1=0 u1+v3=7=>v3=7 u1+v4=3=>v4=3 u2+v3=9=>u2=2 u4+v3=3=>u4=-4 u2+v1=7=>v1=5 u4+v5=2=>v5=6 u3+v5=2=>u3=-4 u3+v2=1=>v2=-4 Перевіримо на оптимальність знайдене рішення Q1 Q2 Q3 Q4 Q5 a ui P1 5 8 5 6 7 25 7 3 25 3 6 4 50 0 P2 7 35 7 63 7 4 9 15 9 5 3 8 4 50 2 P3 1 6 1 30 1 3 4 -1 5 2 25 2 55 -4 P4 1 7 1 8 3 10 3 -1 4 2 40 2 50 -4 b 35 30 50 25 65 vj 5 5 7 3 6 Умова оптимальності(Сij≥ ui+ vj) не виконується в чотирьох клітинках, які виділені, тому план не оптимальний Перерахуємо план і потенціали і перевіримо план на оптимальність 4-2+3-9=-4 ∆L=-415=-60 L=1020-60=960 Q1 Q2 Q3 Q4 Q5 a ui P1 9 8 5 6 7 25 7 3 25 3 6 4 50 0 P2 7 35 7 63 3 4 5 9 1 3 4 15 4 50 -2 P3 5 6 1 30 1 3 4 -1 5 2 25 2 55 -4 P4 5 7 1 8 3 25 3 -1 4 2 25 2 50 -4 b 35 30 50 25 65 vj 9 5 7 3 6 Умова оптимальності(Сij≥ ui+ vj) не виконується в двох клітинках, які виділені, тому план не оптимальний Перерахуємо план і потенціали і перевіримо план на оптимальність 4-2+3-7=-2 ∆L=-225=-50 L=960-50=910 Q1 Q2 Q3 Q4 Q5 a P1 7 8 3 6 5 7 3 25 3 4 25 4 50 P2 7 35 7 63 3 4 5 9 3 3 4 15 4 50 P3 5 6 1 30 1 3 4 1 5 2 25 2 55 P4 5 7 1 8 3 50 3 1 4 2 2 50 b 35 30 50 25 65 Заповнено 7 клітинок, отже план вироджений, тому представимо план так Q1 Q2 Q3 Q4 Q5 a ui P1 7 8 3 6 5 7 3 25 3 4 25 4 50 0 P2 7 35 7 63 3 4 5 9 3 3 4 15 4 50 0 P3 5 6 1 30 1 3 4 1 5 2 25 2 55 -2 P4 5 7 1 8 3 50 3 1 4 2 0 2 50 -2 b 35 30 50 25 65 vj 7 3 5 3 4 Заповнено 8 клітинок(5+4-1), отже план невироджений Умова оптимальності(Сij≥ ui+ vj) виконується для всіх клітинок, тому план оптимальний L=910 Задача 5. Одним із методів відтинання розв'язати задачу цілочи¬слового програмування: Розв’яжемо задачу симплекс-методом x1 x2 x3 -3 1 -1 x4 10 -1 2 x5 -24 -5 -6 Lmin 0 1 -2 Вибрали генеральну строку, оскільки -24<0. 24/6<24/5, тому генеральний стовпчик береться по х2 Перерахуємо таблицю x1 x5 x3 1 11/6 -1/6 x4 2 -8/3 1/3 x2 4 5/6 -1/6 Lmin 8 8/3 -1/3 Вибрали генеральний стовпчик, оскільки 8/3>0. генеральну строку берем по х1, оскільки 1/(11/6)<4/(5/6) Перерахуємо таблицю x3 x5 x1 6/11 6/11 -1/11 x4 38/11 16/11 1/11 x2 39/11 -5/11 -1/11 Lmin 72/11 -16/11 -1/11 Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо перший алгоритм Гоморі x1=6/11-(6/11х3-1/11х5) Побудуємо пряму відсікання хвід= х6= Знайдемо оптимальне рішення, використовуючи пряму відсікання Перерахуємо таблицю x3 x5 x1 6/11 6/11 -1/11 x4 38/11 16/11 1/11 x2 39/11 -5/11 -1/11 x6 -6/11 -6/11 -10/11 Lmin 72/11 -16/11 -1/11 Вибрали генеральну строку, оскільки -6/11<0. генеральний стовпчик берем по х3 Перерахуємо таблицю x3 x6 x1 3/5 3/5 -1/10 x4 17/5 7/5 1/10 x2 18/5 -2/5 -1/10 x5 3/5 3/5 -11/10 Lmin 33/5 -7/5 -1/10 Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо другий алгоритм Гоморі x2=18/5-(-2/5х3-1/10х6) Побудуємо пряму відсікання хвід= х7= Знайдемо оптимальне рішення, використовуючи пряму відсікання Перерахуємо таблицю x3 x6 x1 3/5 3/5 -1/10 x4 17/5 7/5 1/10 x2 18/5 -2/5 -1/10 x5 3/5 3/5 -11/10 х7 -3/5 -3/5 -3/20 Lmin 33/5 -7/5 -1/10 Вибрали генеральну строку, оскільки -3/5<0. генеральний стовпчик берем по х6. Перерахуємо таблицю x3 x7 x1 1 1 -2/3 x4 3 1 2/3 x2 4 0 -2/3 x5 5 5 -22/3 х6 4 4 -20/3 Lmin 7 -1 -2/3 Оскільки коефіцієнти при цільовій функції <0 і х1 та х2 - цілі, то знайдене рішення оптимальне, тобто Lmin=7, a Lmax=-7 x4=3 x2=4 x1=1 x3=0 x5=5 x6=4 x7=0
Используемая литература	Список литературы...