институт.com.ua - національний студентський портал України
  • ТОП-оголошення
Система оголошень институт.com.ua допоможе Вам знайти або розмістити оголошення для студентів, пов'язані з освітою в Україні та закордоном, працевлаштуванням для студентів, репетиторством. Також Ви можете розмістити інформацію про послуги у сфері освіти.
Головна| Новини| Освіта в Україні| Реферати| Контакти

Тема: Розв’язування задач лінійного програмування симплекс.

Каталог пособий и учебных материалов | Математическое программирование | Лабораторная | Страниц: 5 | Год: 2010 | Размер: 17 кб. | Стоимость: 40 грн. | Смотреть | Купить

Розв’язування задач лінійного програмування симплекс.

Cмотрите также:
Задачі з математичного програмування

Задача 1. Розв'язати графічно задачу лінійного програмування: Задача 2. Розв'язати симплекс-методом задачу лінійного програ¬мування: Задача 3. Для заданої задачі лінійного програмування побудувати двоїсту, розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком знайти розв'язок двоїстої до неї: Задача 4. Розв'язати методом потенціалів транспортну задачу: Q1 Q2 Q3 Q4 Q5 а P1 7 3 1 5 4 30 Р2 7 5 8 3 2 25 Р3 6 4 8 3 2 45 Р4 3 1 7 6 2 20 b 10 35 15 25 35 Задача 5. Одним із методів відтинання розв'язати задачу цілочи¬слового програмування:

Двоїстий симплекс метод.

1.Теоретичні відомості В задачах лінійного програмування часто трапляється, що симплекс – метод використати не вдається. При розв’язуванні задач лінійного програмування симплекс - метод використовується для задач з невід’ємними правими частинами та від’ємними елементами оціночного рядка. Часто буває простіше знайти базис який задовольняв би умову оптимальності, але не задовольняв би критерій допустимості. Для розв’язування такого типу задач використовують двоїстий симплекс - метод . з його допомогою задачу приводять до задачі лінійного програмування, де , але умова не вимагається. Таку задачу називають задачею у двоїстій базисній формі Для задач такого типу можливі такі випадки: 1) Всі вільні члени , задача розв’язана ; 2) В стовпці вільних членів є від’ємний елемент, а відповідний рядок містить лише додатні елементи, система обмежень несумісна – задача розв’язків немає, 3) Існує рядок (r) в даному рядку існує хоча б один коефіцієнт , який є меншим нуля. Нехай це елемент з номером S, тоді знаходимо відношення додатного елемента з оціночного рядка до відповідного від’ємного коефіцієнта. Серед всіх отриманих відношень знаходимо максимальне, тоді Жордановими перетвореннями з ключовим елементом приведемо таблицю до еквівалентної в якій і значення цільової функції не збільшиться. Двоїстий симплекс – метод відрізняється від звичайного симплекс – методу лише порядком вибору ключового елемента, а як ми знаємо щоб вибрати ключовий елемент потрібно визначити ключовий рядок та стовпець. Слід пам’ятати, що двоїстий симплекс – метод зручно використовувати дЌя задач які містять одиничний базис, але не належить до задач у двоїстій базисній формі (оціночний рядок містить від’ємні елементи ). Алгоритм використання двоїстого симплекс – методу: Серед від’ємних елементів знаходимо найбільше за абсолютною величиною, відповідний рядок називаємо ключовим. В ключовому рядку перевіряємо знаки всіх коефіцієнтів, якщо всі додатні то розв’язків немає, якщо всі від’ємні то розв’язуємо далі. Оскільки ключовий рядок містить відємні елементи то утворюємо двоїсті симплексні відношення (відношення додатних елементів оціночного рядка до від’ємних елементів ключового рядка ). Над таблицею виконуємо Жорданові перетворення з ключовим елементом.

Задачі з лінійного програмування

1. Дайте геометричне розв’язання задачі лінійного програмування. Розв’язок : Систему рівнянь перетворимо наступним чином : Побудуємо графіки відповідних лінійних функцій : 1 2 3 3 0 3 0 0 3 0 3 4 6 1 4 Таким чином (див Рис.1.), досліджувана площина є закритою і обмежується ABCD. Максим функції досягається в точці C – перетин прямих Ох і 2 : , тоді . Рис.1. 2. Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу. Розв’язок : Канонічна форма матиме вигляд : Розв’яжемо за допомогою симплексної таблиці № Сіб Базис План 2 2 0 0 0 А1 А2 А3 А4 А5 1. 0 А3 -3 -1 -1 1 0 0 2. 0 А4 18 2 3 0 1 0 3. 0 А5 1 -1 1 0 0 1 4. Zi-Cj 0 -2 -2 0 0 0 1. 0 А3 -2 -2 0 1 0 1 2. 0 А4 15 5 0 0 1 -3 3. 2 А2 1 -1 1 0 0 1 4. Zi-Cj 2 -4 0 0 0 2 1. 2 А1 1 1 0 -1/2 0 -1/2 2. 0 А4 10 0 0 5/2 1 -1/2 3. 2 А2 2 0 1 -1/2 0 ½ 4. Zi-Cj 6 0 0 -2 0 0 1. 2 А1 3 1 0 0 1/5 -3/5 2. 0 А3 4 0 0 1 2/5 -1/5 3. 2 А2 4 0 1 0 1/5 2/5 4. Zi-Cj 14 0 0 0 4/5 -2/5 1. 2 А1 9 1 3/2 0 ½ 0 2. 0 А3 6 0 ½ 1 ½ 0 3. 0 А5 10 0 5/2 0 ½ 1 4. Zi-Cj 18 0 1 0 1 0 Таким чином, .

Канонічні форми задач лінійного програмування

Зміст Вступ 3 1. Постановка завдання лінійного програмування 5 2. Канонічна форма завдання лінійного програмування 6 Список використаної літератури. 10

Контрольна робота (задачі) з математичного програмування

Завдання №1 …………………………………………………………………3 Дайте геометричне розв’язання задачі лінійного програмування. Завдання №2 …………………………………………………………………4 Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу. Список використаної літератури …………………………………………..6

Задачі з матпрограмування

План Завдання №1 …………………………………………………………………3 Завдання №2 …………………………………………………………………4 Список використаної літератури …………………………………………..6 Завдання №1 Дайте геометричне розв’язання задачі лінійного програмування. Розв’язання На координатній площині зобразимо всі задані нерівності і визначимо область, в якій знаходиться розв’язок задачі: Замальована область, є областю в якій знаходиться розв’язок задачі. На цьому ж малюнку зобразимо пунктирною лінією графік функції: Шуканим розв’язком заданої задачі буде та точка замальованою області, яку останньою перетне лінія графіку функції (пунктирна) рухаючись по напрямку . З малюнка видно, що такою точкою буде точка з координатами (9;0). Отже, Завдання №2 Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу. Розв’язання Запишемо канонічну форму задачі лінійного програмування, тобто всі знаки нерівностей замінюємо на знаки рівності: Початковим буде наступний розв’язок: Для отримання шуканого розв’язку застосуємо симплекс-метод розв’язання задачі лінійного програмування. Для цього на основі системи рівнянь складемо допоміжну першу симплекс таблицю: 2 2 0 0 0 Бз Сб Ро 1 0,00 3,00 1,00 1,00 -1,00 0,00 0,00 2 0,00 18,00 2,00 3,00 0,00 1,00 0,00 3 0,00 -1,00 1,00 -1,00 0,00 0,00 -1,00 F 0,00 -2,00 -2,00 0,00 0,00 0,00 Використовуючи метод Жордана-Гауса проводимо ітерацію відносно визначеного нами елемента. Після проведення ітерації ми отримаємо наступну другу симплекс таблицю: 2 2 0 0 0 Бз Сб Ро 1 0,00 -6,00 0,00 -0,50 -1,00 -0,50 0,00 2 2,00 9,00 1,00 1,50 0,00 0,50 0,00 3 0,00 -10,00 0,00 -2,50 0,00 -0,50 -1,00 F 18,00 0,00 1,00 0,00 1,00 0,00 Отримана таблиця свідчить про те, що ми отримали оптимальний розв’язок, про це свідчить той факт, що коефіцієнти в останньому рядочку є додатними. Отже, .

Контрольна робота з математичного програмування. Варіант 4

Завдання 1 2 1. Побудувати математичну модель задачі лінійного програмування. 2. Звести дану задачу до канонічного вигляду. Два вироби В1 і В2 обробляються послідовно на трьох верстатах. Ко-жен виріб типу В1 потребує 1 год. для обробки на I-му верстаті, 2 год. – на II-му верстаті і A = 2,45 год. на III-му. Кожен виріб типу В2 потребує для обро-бки 2 год., A = 2,45 год. і 3 год. відповідно на I-му, II-му і III-му верстатах. Час роботи на I-му верстаті не повинен перевищувати 10N = 60 год., на II-му – 15N = 90 год., на III-му – 50 год. Скласти план виробництва при максима-льному прибутку, якщо відомо, що продаж одного виробу типу В1 приносить прибуток 5 грн., а типу В2 – 3 грн. Завдання 2 4 Завдання 2 Розв’язати задачу лінійного програмування графічним методом. Завдання 3 6 Завдання 3 Розв’язати систему лінійних рівнянь методом повного виключення змінних (методом Гаусса) за допомогою розрахункових таблиць. Завдання 4 8 Завдання 4 1. Розв’язати симплекс-методом задачу лінійного програмування. 2. Побудувати двоїсту задачу до даної задачі лінійного програмуван-ня. 3. Знайти розв’язок двоїстої задачі та дати економічну інтерпретацію отриманого розв’язку.

Лінійне програмування

Зміст : 1. 2 2. 4 Література 5 1. Дайте геометричне розв’язання задачі лінійного програмування. Розв’язок : Систему рівнянь перетворимо наступним чином : Побудуємо графіки відповідних лінійних функцій : 1 2 3 3 0 3 0 0 3 0 3 4 6 1 4 Таким чином (див Рис.1.), досліджувана площина є закритою і обмежується ABCD. Максим функції досягається в точці C – перетин прямих Ох і 2 : , тоді . Рис.1. 2. Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу. Розв’язок : Канонічна форма матиме вигляд : Розв’яжемо за допомогою симплексної таблиці № Сіб Базис План 2 2 0 0 0 А1 А2 А3 А4 А5 1. 0 А3 -3 -1 -1 1 0 0 2. 0 А4 18 2 3 0 1 0 3. 0 А5 1 -1 1 0 0 1 4. Zi-Cj 0 -2 -2 0 0 0 1. 0 А3 -2 -2 0 1 0 1 2. 0 А4 15 5 0 0 1 -3 3. 2 А2 1 -1 1 0 0 1 4. Zi-Cj 2 -4 0 0 0 2 1. 2 А1 1 1 0 -1/2 0 -1/2 2. 0 А4 10 0 0 5/2 1 -1/2 3. 2 А2 2 0 1 -1/2 0 ½ 4. Zi-Cj 6 0 0 -2 0 0 1. 2 А1 3 1 0 0 1/5 -3/5 2. 0 А3 4 0 0 1 2/5 -1/5 3. 2 А2 4 0 1 0 1/5 2/5 4. Zi-Cj 14 0 0 0 4/5 -2/5 1. 2 А1 9 1 3/2 0 ½ 0 2. 0 А3 6 0 ½ 1 ½ 0 3. 0 А5 10 0 5/2 0 ½ 1 4. Zi-Cj 18 0 1 0 1 0 Таким чином, . Л

Контрольна робота з математичного програмування

14.15. Розв’язати систему методом Жордана-Гаусса. . 18.15. Розв’язати графічним методом задачу лінійного програмування. , , . 19.15. Розв’язати симплексним методом задачу лінійного програмування (всі змінні ). , . 20.15. Скласти двоїсту задачу до задачі лінійного програмування. , , ( ). 21.15. На підприємствах ( ) виробляється однорідна продукція обсягом од. Готова продукція доставляється в пункти ( ), потреби яких становлять од. Транспортні витрати при перевезенні одиниці продукція з пункту до пункту становлять . Скласти план перевезень продукція, при якому буде перевозитися вся вироблена продукція з мінімальними сумарними потребами. 11 8 7 5 35 2 13 10 1 40 6 9 7 8 70 25 20 30 70