18. геометричний. інтерпретація системи обмежень і цільової функції в задачі ЛП
19.Випуклое безліч: крайні (кутові) точки множини. опуклий багатогранник
Визначення Безліч М називається опуклим, якщо разом з будь-якими двома точками, які належать даній безлічі, воно містить і відрізок їх з'єднує.
Визначення Точка х безлічі М називається кутовий або крайньої, якщо вона не є внутрішньою ні для якого відрізка, цілком належить даній безлічі.
Теорема 1. Будь-яку точку відрізка можна представити у вигляді випуклої комбінації його кутових точок.
λ1. λ2 ≥ 0 опукла комбінація точок кутових точок А і В
Теорема 2. Будь-яку точку опуклого замкнутого безлічі можна представити у вигляді випуклої комбінації його кутових точок.
20. алгоритм графічного методу розв'язання задач ЛП
Алгоритм графічного методу.
1. Перевіряється, чи перебуває вихідна ЗЛП в стандартній формі, якщо немає, то завдання необхідно перетворити до стандартної форми.
2. Перевіряється кількість невідомих змінних. Якщо ця кількість більше трьох, то задача не може бути вирішена графічним методом (існують інші ефективні методи вирішення таких завдань).
3. Будується область допустимих значень змінних для ЗЛП.
4. Будується спрямовує вектор c.
5. Через ОДЗ проводиться вихідна ізоцель (перпендикулярно направляючої вектору).
6. Проводиться уявне переміщення вихідної ізоцелі в напрямку вектора c. якщо визначається максимальне значення цільової функції, або в протилежному напрямку, якщо визначається її мінімальне значення, до тих пір, поки ізоцель не стане опорною до ОДЗ. Точки перетину опорної ізоцелі і ОДЗ і будуть оптимальними точками завдання.
7. Для того, щоб визначити координати оптимальної точки, необхідно вирішити систему відповідних лінійних рівнянь.
8. Для знаходження оптимального значення цільової функції необхідно оптимальні значення змінних підставити в цільову функцію і обчислити її значення.
20. алгоритм графич. методу вирішення завдань ЛЗ
Алгоритм графічного методу.
Послідовним побудовою кожного з умов системи обмежень задачі здійснюється побудова ОДЗ.
Будується спрямовує вектор С за коефіцієнтами при змінних цільової функції.
Перпендикулярно направляючої вектору через початок координат проводиться вихідна ізоцель.
Проводиться уявне переміщення вихідної ізоцелі в напрямку зростання значень вектора С, якщо визначається максимальне значення цільової функції або в протилежному напрямку, якщо визначається її мінімальне значення, до тих пір, поки ізоцель не стане опорною до ОДЗ. Точки перетину опорної ізоцелі і ОДЗ будуть оптимальними точками завдання.
Для визначення координат оптимальної точки необхідно вирішити систему відповідних лінійних рівнянь тих умов, на перетині яких знаходиться оптимальна точка.
Для знаходження оптимального значення цільової функції, необхідно координати оптимальної точки підставити в цільову функцію і обчислити її значення.
23. теореми про область допустимих значень задачі ЛП і про цільову ф-ції
Теорема про ОДЗ. Область допустимих рішень задачі ЛП опукле безліч (замкнутий і обмежений в n-вимірному просторі)
Теорема 2. Про цільової функції задачі лінійного програмування.
Цільова функція ЗЛП приймає своє оптимальне значення в одній з кутових точок області допустимих значень змінних. Якщо цільова функція приймає своє оптимальне значення в декількох кутових точках, то таке ж значення вона приймає і в будь-якій точці, що є опуклою комбінацією даних кутових точок.
24. Теорема про кутовій точці. Достатня і необхідна умова
25. Наслідки з теореми про властивості рішень задач ЛП і висновки. Поняття опорного плану.
Наслідки з теорем.
Визначення. План = (х1, х2, ..., хn), позитивним координатами якого відповідають лінійно незалежні вектори, називається опорним планом ЗЛП.
Следствіе1. Опорний план має не більше m позитивних координат.
Якщо він має рівно m позитивних координат, то такий опорний план називається невироджених, в іншому випадку виродженим.
Слідство 2. Кожна кутова точка ОДЗ є опорним планом.
27. Алгоритм симплексного методу.
При вирішенні завдань ЛП симплексним методом необхідно виконати наступну послідовність дій.
Перевіряється, чи перебуває завдання ЛП в канонічній формі. Якщо немає, то необхідно вихідну модель перетворити в канонічну форму.
Виділяється початковий опорний план і значення цільової функції при цьому опорному плані.
Проводиться побудова вихідної симплексной таблиці.
Перевіряються значення оцінок оптимальності в індексному рядку. Якщо немає позитивних оцінок, то виписується оптимальне рішення і алгоритм закінчує свою роботу. В іншому випадку виконується пункт 5.
В базисі вводиться вектор, якому відповідає найбільша позитивна оцінка. Даний стовпець називається що дозволяє.
З базису виводиться вектор, якому відповідає симплексному відношення, розраховане за формулою 0 0, то план ХБ0 не є оптимальним і можна перейти до плану ХБ1 такому, що Z (ХБ1) ≤ Z (ХБ0).
Тут Zj = (С, Āj) - скалярний добуток векторів.
С - вектор, що складається з коефіцієнтів при базисних змінних цільової функції Z
Āj - вектор, що складається з коефіцієнтів розкладання відповідного вектора по векторах базису.
cj - коефіцієнт цільової функції Z при змінної Хj
Схожі роботи:
Шпаргалкапо Інформаційним системам і технології
ПО. Системний рівень ПО. Драйвери. Службовий рівень ПО. Утиліти. Прикладний рівень ПО. Програмне забезпечення (ПО.; • типові алгоритми управління; • методи математіческогопрограммірованія. Математичної статистики, теорії масового обслуговування та ін.
Шпаргалкапо Бухгалтерського обліку (2)
Шпаргалка >> Бухгалтерський облік і аудит
по економіко-управлінських дисциплін Квиток № 13 1. Класифікація організацій в менеджменті. 2. Спеціальні завдання математіческогопрограммірованія. завдання математіческогопрограммірованія Спеціальні завдання математіческогопрограммірованія. Завдання.
Шпаргалкапо Інформатиці і програмування
і програмних засобів; • розробка математичної моделі; • розробка структур даних. і уточнення в разі потреби математичної моделі з повторним виконанням етапів. 12 Класифікація мов програмування Мови розрізняються по залежності від.
Шпаргалкапо логіці: Відповіді на екзаменаційні квитки
Валерій Вечканов Шпаргалкапо логіці Володимир Едуардович Вечканов Шпаргалкапо логіці. також алго-метричні мови програмування для ЕОМ, які отримали. будь-яка наука повинна прагнути до математичного виразу цих законів; До соціологічним.
Шпаргалкіпо управлінським рішенням
що завдання формалізується моделлю нечіткого математіческогопрограммірованія. в якій в якості заданого критерію ефективності. рівня ієрархії S здійснюється по ітераційного алгоритму, реалізованого за вихідними даними, зафіксованим в матрицях.