Похожие материалы
Уроки математики / Другое / Презентация к лекции по высшей математике на тему "Математика в экономике"

Презентация к лекции по высшей математике на тему "Математика в экономике"

Математика в экономике
Тема 2: «Линейное программирование» §1. Общая задача линейного программирован...
§1. Общая задача линейного программирования Тема 2: «Линейное программировани...
§1. Общая задача линейного программирования Пусть дана система с m неравенств...
§1. Общая задача линейного программирования Необходимо найти такое решение си...
§1. Общая задача линейного программирования Такую систему линейных неравенств...
§1. Общая задача линейного программирования Оптимальным решением, или оптимал...
§1. Общая задача линейного программирования Если система ограничений состоит...
§1. Общая задача линейного программирования Чтобы перейти от стандартной форм...
§1. Общая задача линейного программирования Решение экономической задачи можн...
§1. Общая задача линейного программирования Чтобы составить математическую мо...
§1. Общая задача линейного программирования III) Учитывая ограничения в испол...
§2. Система m линейных неравенств с n переменными В задачах Л. П. интерес пре...
§2. Система m линейных неравенств с n переменными Пусть дана система (1). Вып...
§2. Система m линейных неравенств с n переменными Любые m переменные этой сис...
§2. Система m линейных неравенств с n переменными Основными могут быть разные...
§2. Система m линейных неравенств с n переменными Теорема. Если для системы m...
§2. Система m линейных неравенств с n переменными Решение систем линейных ура...
§2. Система m линейных неравенств с n переменными В задачах Л. П. именно таки...
§3. Геометрический смысл решения неравенств и систем неравенств Наиболее прос...
§3.Геометрический смысл решения неравенств и систем неравенств Пусть дана сис...
§3.Геометрический смысл решения неравенств и систем неравенств Сама прямая на...
§3.Геометрический смысл решения неравенств и систем неравенств Для определени...
§3.Геометрический смысл решения неравенств и систем неравенств Если неравенст...
§3.Геометрический смысл решения неравенств и систем неравенств Системе нераве...
§3.Геометрический смысл решения неравенств и систем неравенств Множество точе...
§3.Геометрический смысл решения неравенств и систем неравенств Если область D...
§3.Геометрический смысл решения неравенств и систем неравенств При построении...
§3.Геометрический смысл решения неравенств и систем неравенств При построении...
§4. Геометрический метод решения задач линейного программирования Рассмотрим...
§4. Геометрический метод решения задач линейного программирования Множество д...
Значит задачу Л. П. можно сформулировать так: среди всех точек области D найт...
Этот вектор показывает направление наискорейшего изменения целевой функции. К...
Алгоритм решения задачи: 1) Находим область допустимых решений системы ограни...
3) Проводим линию уровня ℓ0 , которая перпендикулярна . 4) Линию уровня перем...
Решением задачи на min является первая точка, в которой прямая ℓ0 встречается...
Zmin = Z(A) 0 x2 x1 ℓ0 C B A D E Zmax = Z(C) Тема 2: «Линейное программирован...
При построении может получится многоугольник который не ограничен снизу, тогд...
Замечания : 1) Если окажется, что прямая ℓ0 при перемещении параллельна одной...
2) Аналогично, можно показать решение задачи линейного программирования с 3-м...
Пример : Для изготовления 2-х видов продуктов P1 и P2 используется 4 вида сыр...
Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач...
Необходимо составить план выпуска продукции, обеспечивающий max прибыль, если...
Тогда, используя технологические коэффициенты можно записать систему ограниче...
Экономико-математическая модель задачи Тема 2: «Линейное программирование» *...
Решим задачу графически: ℓ1: x1 + 3x2 = 18 ℓ2: 2x1 + x2 = 16 ℓ3: x2 = 5 (ℓ3 п...
0 x2 x1 ℓ0 ℓ1 ℓ4 ℓ3 ℓ2 ℓ5 ℓ6 A B C D E 6 5 16 7 8 18 Zmax = r (C) С: ℓ1 ∩ ℓ2...
С(6 ; 4) -5x2 = -20 x2 = 4 => x1 = 6 Zmax = Z(6 ; 4) = 2 * 6 + 3 * 4 = = 12 +...
Вывод: план выпуска продукции вида P1 составляет 6 единиц; вида P2 – 4 единиц...
§5. Симплекс-метод решения задач Л.П. (Симплекс – это простейший выпуклый мно...
§5. Симплекс-метод решения задач Л.П. Идея симплексного метода (метода послед...
§5. Симплекс-метод решения задач Л.П. Этот метод был предложен американским у...
§5. Симплекс-метод решения задач Л.П. Схема решения задачи симплексным методо...
§5. Симплекс-метод решения задач Л.П. Доказано, что таким путём через конечно...
§6. Геометрическая интерпретация симплекс-метода Из основных теорем Л. П. сле...
§6. Геометрическая интерпретация симплекс-метода 2) Для этого следует перебра...
4) Число перебираемых допустимых базисных решений можно сократить, если переб...
§7. Аналитический способ решения задач линейного программирования а) задача н...
§7.Аналитический способ решения задач линейного программирования Сколько след...
Решение: Пусть хозяйство приобрело: x1 – 3-х тонных машин x2 – 5-ти тонных ма...
Эконо- мико– матема-тическая модель задачи §7.Аналитический способ решения за...
Решим задачу аналитически: Перейдём от стандартной формы задания к каноническ...
r(A) = min(3; 4) ≤ 3 §7.Аналитический способ решения задач линейного программ...
1 шаг Выразим x1, x2, x3 и Z через x4: §7.Аналитический способ решения задач...
Итак, самое маленькое значение которое может принимать x4 = 0 : => т.к. xi ≥...
Итак, x1 = 4, x2 = 8, x3 = 6, x4 = 0. X1 = (4, 8, 6, 0) – первое допустимое б...
Так как прямая x4 входит в функцию Z со знаком “+”, то её увеличение увеличит...
Очевидно, что сохранение не отрицательности возможно, если не нарушается ни о...
Значит x4 следует вводить в базис, а x3 – в свободные (из подчеркнутого уравн...
§7.Аналитический способ решения задач линейного программирования Тема 2: «Лин...
§7.Аналитический способ решения задач линейного программирования Тема 2: «Лин...
Аналогично рассуждениям первого шага, анализируем формулу функции Z, т.к. x3...
X2 = (10, 5, 0, 3) – новое допустимое базисное решение. Но так как x3 увеличи...
Дана система уравнений: б) задача на минимум Среди допустимых решений найти,...
Замечания: При определении минимума линейной функции Z возможны 2 случая: 1)...
Рассмотрим второй случай: r(A) = 2 => базисных переменных две. 1 шаг x1, x2 –...
Решим систему относительно x1 и x2: X1 = (40; 48; 0; 0) Z = 0 первое допустим...
Анализируем полученную формулу функции Z: Так как x3 входит в Z со знаком «+»...
§7.Аналитический способ решения задач линейного программирования Тема 2: «Лин...
2 шаг Вводим x4 – в базис, а x2 – в свободные. Выразим x1 и x4 через x2 и x3...
§7.Аналитический способ решения задач линейного программирования Тема 2: «Лин...
Снова анализируем полученную формулу функции Z: т.к. x3 и x2 входят в Z со зн...
Замечания: 1) В общем виде критерий оптимальности решения задачи на максимум...
2) При решении задачи на минимум: Если в выражении функции Z через свободные...
3) Уравнение в котором достигается наиболее возможное значение переменной, пе...
§8. Симплексные таблицы. Симплекс-метод в общем виде Если система ограничений...
§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть дана совместная си...
§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть ранг этой системы...
§8. Симплексные таблицы. Симплекс-метод в общем виде Причём, чтобы начальное...
§8. Симплексные таблицы. Симплекс-метод в общем виде Составим симплекс таблиц...
§8. Симплексные таблицы. Симплекс-метод в общем виде Рассмотрим элементы посл...
§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть это γ4, это означа...
§8. Симплексные таблицы. Симплекс-метод в общем виде Столбец содержащий x4 на...
§8. Симплексные таблицы. Симплекс-метод в общем виде Составим отношение свобо...
§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть min является отнош...
§8. Симплексные таблицы. Симплекс-метод в общем виде Определение. Элемент сто...
§8. Симплексные таблицы. Симплекс-метод в общем виде a24 – разрешающий элемен...
§8. Симплексные таблицы. Симплекс-метод в общем виде Алгоритм перехода к симп...
§8. Симплексные таблицы. Симплекс-метод в общем виде 3) Остальные элементы ра...
§8. Симплексные таблицы. Симплекс-метод в общем виде 5) Все остальные элемент...
§8. Симплексные таблицы. Симплекс-метод в общем виде Тогда симплекс–таблица №...
§8. Симплексные таблицы. Симплекс-метод в общем виде Полагаем свободные перем...
§8. Симплексные таблицы. Симплекс-метод в общем виде Рассмотрим выражение для...
§8. Симплексные таблицы. Симплекс-метод в общем виде Следовательно функция Z...
§8. Симплексные таблицы. Симплекс-метод в общем виде При решении задачи на ma...
§8. Симплексные таблицы. Симплекс-метод в общем виде 2) Разрешающую строку вы...
§8. Симплексные таблицы. Симплекс-метод в общем виде 5) Критерий оптимальност...
§8. Симплексные таблицы. Симплекс-метод в общем виде Задача №1. Решить задачу...
§8. Симплексные таблицы. Симплекс-метод в общем виде Перейдём к канонической...
§8. Симплексные таблицы. Симплекс-метод в общем виде Поэтому в системе можно...
§8. Симплексные таблицы. Симплекс-метод в общем виде Выразим базисные перемен...
§8. Симплексные таблицы. Симплекс-метод в общем виде Итак, Тема 2: «Линейное...
§8. Симплексные таблицы. Симплекс-метод в общем виде Симплекс-таблица №1 Баз...
§8. Симплексные таблицы. Симплекс-метод в общем виде Симплекс-таблица №2 1) Р...
§8. Симплексные таблицы. Симплекс-метод в общем виде 3) Элементы разрешающего...
§8. Симплексные таблицы. Симплекс-метод в общем виде 5) Так как в строке Z(γ0...
§8. Симплексные таблицы. Симплекс-метод в общем виде Проверка. 10 ≤ 10 (полно...
Задача №2. Дана система ограничений в каноническом виде: §8. Симплексные табл...
Среди неотрицательных решений системы найти то которое обращает функцию Z в m...
Симплекс-таблица №1. §8. Симплексные таблицы. Симплекс-метод в общем виде Тем...
Составим симплекс-таблицу №2. §8. Симплексные таблицы. Симплекс-метод в общем...
Т.к. в строке Z элементы отрицательны (γ0 не рассматривать), то по критерию о...
Примечание. Если среди элементов разрешающего столбца нет положительных, то m...
§9. Метод искусственного базиса (М-метод) Если в задачи Л.П. сразу не получил...
§9. Метод искусственного базиса (М-метод) На основе результатов решения расши...
Алгоритм решения задачи методом искусственного базиса: 1) В каждое уравнение...
2) Эти искусственные переменные следует ввести и в целевую функцию Z. В задач...
3) Вводят новую линейную целевую функцию F = Z M(y1, y2, …, ym) и эту функцию...
4) Эти искусственные переменные выводят из базиса делая их свободными и потом...
5) Чтобы определить разрешающий столбец, находят в строке функции M (m + 2-я...
6) После переноса всех искусственных переменных y1, y2, …, ym в свободные, по...
7) И т.к. теперь есть допустимое решение далее задачу можно решать и на max и...
Решить задачу симплекс-методом: §9. Метод искусственного базиса (М-метод) Тем...
Решение: в первом уравнении нет оснований вводить переменную искусственного б...
§9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *
Составим симплекс-таблицу №1. §9. Метод искусственного базиса (М-метод) Тема...
В строке (m + 2), т.е. в строке M выбираем наибольший положительный элемент,...
Переходим к симплекс-таблице №2. §9. Метод искусственного базиса (М-метод) Те...
В данной таблице значения 1/3 расположены в двух столбцах, поэтому выбираем н...
Симплекс-таблица №3. §9. Метод искусственного базиса (М-метод) Тема 2: «Линей...
После заполнения симплекс-таблицы №3 мы пришли к строке M, которая является н...
Анализируя строку Z видим, что x5 входит в целевую функцию Z со знаком «+», п...
Симплекс-таблица №4. Баз Св §9. Метод искусственного базиса (М-метод) Тема 2:...
Симплекс-таблица №5. Базис Своб §9. Метод искусственного базиса (М-метод) Тем...
Т.к. в строке Z все коэффициенты отрицательные, следовательно, решение оптима...
§10. Теория двойственности задач Каждой задаче линейного программирования соо...
§10. Теория двойственности задач Задача №1. У некоторого предприятия №1 (прои...
§10. Теория двойственности задач Сырьё Прод Тема 2: «Линейное программировани...
§10. Теория двойственности задач Найти оптимальный план производства продукци...
§10. Теория двойственности задач Система ограничений: Тема 2: «Линейное прогр...
§10. Теория двойственности задач Zmax = 3267 (усл. ден. ед.) Решая задачу сим...
§10. Теория двойственности задач Задача №2. Допустим, что у предприятия №1 ес...
§10. Теория двойственности задач Пусть y1 – цена единицы сырья вида S1; y2 –...
§10. Теория двойственности задач Система ограничений: Тема 2: «Линейное прогр...
§10. Теория двойственности задач Под F понимается гарантированный доход от пр...
§11. Двойственные задачи в общем виде Z = c1x1 + c2x2 + + … + cnxn → max F =...
Составить такой план выпуска продукции X = (x1, x2, …, xn) при котором прибыл...
§11. Двойственные задачи в общем виде Свойства двойственных задач: 1o) В одно...
§11. Двойственные задачи в общем виде 4o) Матрицы коэффициентов при переменны...
§12. Алгоритм составления двойственной задачи 1) Привести все неравенства сис...
§12. Алгоритм составления двойственной задачи 2) Составить расширенную матриц...
§12. Алгоритм составления двойственной задачи 4) Сформировать двойственную за...
Для основной задачи с использованием ресурсов: а) составим расширенную матриц...
§12. Алгоритм составления двойственной задачи 5) Составляем по числам транспо...
§12. Алгоритм составления двойственной задачи Тема 2: «Линейное программирова...
§12. Алгоритм составления двойственной задачи 6) Мы имеем теперь две системы...
основная двойственная §12. Алгоритм составления двойственной задачи Тема 2: «...
§12. Алгоритм составления двойственной задачи В качестве основной системы бер...
§12. Алгоритм составления двойственной задачи Поэтому решаем систему (*) Симп...
§12. Алгоритм составления двойственной задачи Используя решение основной зада...
§12. Алгоритм составления двойственной задачи Симплекс-таблица №2. Базис Своб...
§12. Алгоритм составления двойственной задачи Итак, найдено оптимальное решен...
Таким образом: Zmax = 9800/3 ≈ 3267 решение основной задачи Fmin = 9800/3 ≈ 3...
§13. Транспортная задача Общая постановка задачи. Транспортная задача (Т.З.)...
§13. Транспортная задача Всё это сокращает время продвижения товаров, уменьша...
§13. Транспортная задача Наиболее часто встречаются следующие задачи относящи...
§13. Транспортная задача – отдельные задачи оптимальной загрузки промышленнос...
§13. Транспортная задача В общем виде задачу можно представить следующим обра...
§13. Транспортная задача Требуется составить план перевозок, позволяющий выве...
1) Если , то задача называется закрытой. 2) Если , то задача называется откры...
§13. Транспортная задача Поэтому если в исходных условиях дана открытая задач...
§13. Транспортная задача в) Если запасы поставщиков превышают потребности пот...
§13. Транспортная задача Т.З. присущи следующие особенности: а) распределению...
§13. Транспортная задача d) во всех уравнениях коэффициенты при неизвестных р...
§13. Транспортная задача Т.З. как задача Л.П. может быть решена симплексным м...
§13. Транспортная задача Поэтому для решения Т.З. разработан специальный мето...
§13. Транспортная задача Рассмотрим закрытую Т.З. Данные запишем в распредели...
c11 §13. Транспортная задача c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 Тема...
§13. Транспортная задача xij – количество груза, которое необходимо перевести...
§13. Транспортная задача Тема 2: «Линейное программирование» *
§13. Транспортная задача Если m – число пунктов отправления, а n – число пунк...
§13. Транспортная задача Таким образом в общем случае система Т.З. должна име...
§14. Построение начального плана перевозок п.1. Метод северо-западного угла....
п.1. Метод северо-западного угла. Определение. Не нулевые перевозки xij приня...
Определение. План перевозок в которых число базисных переменных равно n + m –...
Пример. На складах A1, A2, A3 имеются запасы продукции в кол-ве 90, 400, 110...
Расходы по перевозке 1 т. продукции заданы матрицей (усл. ед.): п.1. Метод се...
2 5 2 4 1 5 3 6 8 п.1. Метод северо-западного угла. Тема 2: «Линейное програм...
Метод северо-западного угла п.1. Метод северо-западного угла. Тема 2: «Линейн...
Для составления первоначального плана перевозок: 1) В плане заполняется клетк...
3) Если на некотором шаге возникает ситуация, когда несколько минимальных эле...
Метод минимального элемента п.2. Метод минимального элемента. Тема 2: «Линейн...
п.3. Метод потенциалов решения Т.З. Как уже отмечалось ранее математическая м...
Поэтому данные особенности позволили преобразовать симплекс-метод в метод пот...
Таким образом найденное исходное опорное решение (методом min элемента либо м...
Числа Ui и Vj называются потенциалами. В распределительную таблицу добавляют...
Ui Vj п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование»...
Так как в системе кол-во неизвестных больше числа уравнений, то система имеет...
Найденные значения потенциалов заносим в таблицу и проверяем потенциальность...
3 ≤ 5 – потенциальна 7 ≤ 2 – не потенциальна 0 ≤ 4 – потенциальна 4 ≤ 6 – пот...
Так как одна клетка не потенциальна, то план не оптимальный, а значит его мож...
2 5 2 4 1 5 3 6 8 Ui Vj 60 60 60 60 / 30 / 110 / 0 / 60 п.3. Метод потенциало...
Проверим полученный план на оптимальность методом потенциалов: Предполагаем U...
-2 ≤ 5 – потенциальна 5 ≤ 4 – не потенциальна -1 ≤ 6 – потенциальна 2 ≤ 8 – п...
п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» * 2 5...
Аналогично проверим полученный план на оптимальность методом потенциалов: Пре...
1 ≤ 2 – потенциальна -2 ≤ 5 – потенциальна 0 ≤ 6 – потенциальна 4 ≤ 8 – потен...
2 5 2 4 1 5 3 6 8 Ui Vj Ответ: минимальные затраты на транспортировку составл...
Тема 12: «Теория игр» §2. Матричные игры §1. Классификация игр п.1 Решение ма...
§1. Классификация игр Тема 12: «Теория игр» Классификацию игр можно проводить...
§1. Классификация игр По количеству стратегий игры делятся на конечные и беск...
§1. Классификация игр По характеру взаимодействия игры делятся на: 1) бескоал...
§1. Классификация игр По характеру выигрышей игры делятся на: игры с нулевой...
§1. Классификация игр По виду функций выигрыша игры делятся на: матричные, би...
§1. Классификация игр Матричная игра - это конечная игра двух игроков с нулев...
§1. Классификация игр Для матричных игр доказано, что любая из них имеет реше...
§1. Классификация игр Биматричная игра - это конечная игра двух игроков с нен...
§1. Классификация игр Непрерывной считается игра, в которой функция выигрышей...
§1. Классификация игр Оптимальной стратегией игрока называется такая стратеги...
§1. Классификация игр Стратегия первого игрока называется оптимальной, если п...
§1. Классификация игр Основными вопросами теории игр, которые возникают в ком...
§2. Матричные игры. п.1 Решение матричных игр в чистых стратегиях Матричная и...
п.1 Решение матричных игр в чистых стратегиях Каждый из игроков делает один х...
п.1 Решение матричных игр в чистых стратегиях Рассмотрим матричную игру следу...
п.1 Решение матричных игр в чистых стратегиях Где Ui – стратегии игрока 1 и с...
п.1 Решение матричных игр в чистых стратегиях Аналогичные ситуации возможны и...
п.1 Решение матричных игр в чистых стратегиях Подобный подход к решению рассм...
п.1 Решение матричных игр в чистых стратегиях Определение. Число , определённ...
п.1 Решение матричных игр в чистых стратегиях Аналогичные рассуждения можно п...
п.1 Решение матричных игр в чистых стратегиях Определение. Число , определяем...
п.1 Решение матричных игр в чистых стратегиях Максиминные стратегии игроков с...
п.1 Решение матричных игр в чистых стратегиях Седловая точка - это пара чисты...
п.2 Смешанное расширение матричной игры Исследование в матричных играх начина...
п.2 Смешанное расширение матричной игры Если же в игре нет седловой точки в ч...
п.2 Смешанное расширение матричной игры Улучшение решений матричных игр следу...
п.2 Смешанное расширение матричной игры Определение. Смешанной стратегией игр...
п.2 Смешанное расширение матричной игры Аналогично для игрока 2, который имее...
п.2 Смешанное расширение матричной игры Чистая стратегия есть частный случай...
п.2 Смешанное расширение матричной игры Определение. Средний выигрыш игрока 1...
п.2 Смешанное расширение матричной игры Первый игрок имеет целью за счёт изме...
п.2 Смешанное расширение матричной игры Аналогичной должна быть ситуация и дл...
п.2 Смешанное расширение матричной игры Величина Е(А, х0, у0) называется при...
п.2 Смешанное расширение матричной игры Оптимальные смешанные стратегии и цен...
п.3 Свойства решений матричных игр Обозначим через G(X, Y, A) игру двух лиц с...
п.3 Свойства решений матричных игр Определение. Стратегия х1 игрока 1 доминир...
п.3 Свойства решений матричных игр При этом стратегии х2 и у2 называются доми...
п.3 Свойства решений матричных игр Свойство 1. Если чистая стратегия одного и...
п.3 Свойства решений матричных игр Свойство 2. Ни одна строго доминируемая чи...
п.3 Свойства решений матричных игр Свойство 3. Пусть G = (X, Y, A) – конечная...
п.3 Свойства решений матричных игр Свойство 4. Пусть G = (X, Y, A) – конечная...
п.3 Свойства решений матричных игр Свойство 5. Если для чистой стратегии х' и...
п.3 Свойства решений матричных игр Свойство 6. Тройка (х0, у0, ) является реш...
п.3 Свойства решений матричных игр Свойство 7. Для того, чтобы х0 = ( х10, .....
п.3 Свойства решений матричных игр Аналогично для игрока 2: чтобы y0 = ( y10,...
п.3 Свойства решений матричных игр Из последнего свойства вытекает: чтобы уст...
п.3 Свойства решений матричных игр Таким образом, решение матричной игры свод...
п.3 Свойства решений матричных игр Поэтому в первую очередь следует, по возмо...
п.3 Свойства решений матричных игр Если оно выполняется, то игроки имеют чист...
п.3 Свойства решений матричных игр Замечание. Отметим, что исключение доминир...
п.3 Свойства решений матричных игр Пример 1. Пусть G = (X, Y, A), где Х = {1,...
п.3 Свойства решений матричных игр Решение. Прежде всего заметим, что по свой...
п.3 Свойства решений матричных игр Элементы 4-ой строки этой матрицы «≤» соот...
п.3 Свойства решений матричных игр В матричной форме игру G2 можно представит...
п.3 Свойства решений матричных игр Применяя свойство 5 получим, что всякое ре...
п.3 Свойства решений матричных игр А игра G3 не имеет решения в чистых страте...
п.3 Свойства решений матричных игр Действительно, если игрок 1 выбирает с рав...
п.3 Свойства решений матричных игр Следовательно, указанные стратегии являютс...
п.4 Игры порядка 2 x 2 В общем случае игра 2 х 2 определяется матрицей Прежде...
п.4 Игры порядка 2 x 2 Если же игра с матрицей выигрышей А не имеет чистых ст...
п.4 Игры порядка 2 x 2 Далее, по свойству 1 следует, что а11 = а12 = и матриц...
п.4 Игры порядка 2 x 2 Пусть Х = (ξ , 1 – ξ) – оптимальная стратегия игрока 1...
п.4 Игры порядка 2 x 2 Если же коэффициент пропорциональности равен 1, то мат...
п.4 Игры порядка 2 x 2 Следовательно, если υ  0 и игроки имеют только смешан...
п.4 Игры порядка 2 x 2 Аналогичные рассуждения приводят нас к тому, что оптим...
п.5 Графический метод решения игр 2 x n и m x 2 Пример 2. Рассмотрим игру, за...
п.5 Графический метод решения игр 2 x n и m x 2 На плоскости XОY введём систе...
п.5 Графический метод решения игр 2 x n и m x 2 В точках A1 и А2 восстановим...
x y A1 A2 2 5 7 2 3 11 B1 B2 B3 N M υ 0 1 п.5 Графический метод решения игр 2...
п.5 Графический метод решения игр 2 x n и m x 2 Если же игрок 1 применит стра...
п.5 Графический метод решения игр 2 x n и m x 2 Например, расстояние от любой...
п.5 Графический метод решения игр 2 x n и m x 2 Таким образом, ординаты точек...
п.5 Графический метод решения игр 2 x n и m x 2 Соответствующие два уравнения...
п.5 Графический метод решения игр 2 x n и m x 2 Таким образом, мы можем найти...
п.5 Графический метод решения игр 2 x n и m x 2 Пример 3. Найти решение игры,...
п.5 Графический метод решения игр 2 x n и m x 2 Матрица имеет размерность 2 х...
5 7 6 8 А4′ А3′ А2′ А1′ п.5 Графический метод решения игр 2 x n и m x 2 y x B...
п.5 Графический метод решения игр 2 x n и m x 2 Решение игры таково Тема 12:...
§3. Сведение матричной игры к задаче линейного программирования Предположим,...
§3. Сведение матричной игры к задаче линейного программирования Итак, пусть д...
§3. Сведение матричной игры к задаче линейного программирования Разделим все...
§3. Сведение матричной игры к задаче линейного программирования Поскольку пер...
§3. Сведение матричной игры к задаче линейного программирования Поскольку вто...
§3. Сведение матричной игры к задаче линейного программирования Формулы (3) и...
§3. Сведение матричной игры к задаче линейного программирования Пример 4. Най...
§3. Сведение матричной игры к задаче линейного программирования Составим тепе...
§3. Сведение матричной игры к задаче линейного программирования Решим вторую...
§3. Сведение матричной игры к задаче линейного программирования Симплекс-табл...
§3. Сведение матричной игры к задаче линейного программирования Симплекс-табл...
§3. Сведение матричной игры к задаче линейного программирования Из оптимально...
§3. Сведение матричной игры к задаче линейного программирования При этом опти...
Тема 13: «Теория графов» §2. Способы задания графов §1. Основные понятия и оп...
§1. Основные понятия и определения Тема 13: «Теория графов» Графом G называет...
§1. Основные понятия и определения Тема 13: «Теория графов» * При этом вершин...
§1. Основные понятия и определения При изображении графов на рисунках или схе...
§1. Основные понятия и определения Ребро, соединяющее две вершины, может имет...
§1. Основные понятия и определения Граф называется конечным, если множество е...
§1. Основные понятия и определения Локальной степенью вершины A V n-графа G н...
§1. Основные понятия и определения Для вершин орграфа определяется две локаль...
§1. Основные понятия и определения Два графа равны между собой, если множеств...
§1. Основные понятия и определения Длиной пути называется число ребер этого п...
§1. Основные понятия и определения Для каждой пары вершин дерева существует е...
§2. Способы задания графов Граф G считается полностью заданным, если нумераци...
§2. Способы задания графов Графический способ A B C D E r1 r2 r3 r4 Тема 13:...
§2. Способы задания графов Порядок указания вершин в n-графе при описании реб...
§2. Способы задания графов Если же G – орграф, то , если вершина Vj – начало...
§2. Способы задания графов Матрица смежности S = (sij) – квадратная матрица р...
§2. Способы задания графов Свойства матриц U(uij) и S(sij): 1o) Если два граф...
§2. Способы задания графов Еще один способ – задание графа списком ребер. Это...
g 1 2 3 4 g 1 2 3 4 §3. Примеры решения заданий Пример 1. Задать матрицами ин...
§3. Примеры решения заданий Матрицы инцидентности и смежности для G1: Тема 13...
§3. Примеры решения заданий Матрицы инцидентности и смежности для G2: Тема 13...
§3. Примеры решения заданий Список ребер G2: Список ребер n-графа G1 аналогич...
§3. Примеры решения заданий Пример 2. Представлена сетевая модель некоторого...
§3. Примеры решения заданий Решение. Сетевая модель представляет собой орграф...
§3. Примеры решения заданий Орграф может быть полностью задан следующими спос...
§3. Примеры решения заданий матрицей смежности: списком ребер: Тема 13: «Теор...
§3. Примеры решения заданий Пример 3. Передвигаться по схеме можно только в у...
§3. Примеры решения заданий Решение. Решить поставленную задачу помогают дере...
§3. Примеры решения заданий 0 ярус 1 ярус 2 ярус 3 ярус 4 ярус 5 ярус 6 ярус...
§3. Примеры решения заданий Наикротчайший путь заканчивается в меньшем ярусе...
§3. Примеры решения заданий Этот пример показывает, что понятие «длина пути»...
§3. Примеры решения заданий Задача 4. Может ли так случиться, что в одной ком...
§3. Примеры решения заданий Изобразим графы, которые могут соответствовать та...
Тема 14: «Сетевое планирование» §2. Расчет и анализ сетевых моделей §1. Постр...
§1. Построение сетевых моделей Тема 14: «Сетевое планирование» Построение сет...
§1. Построение сетевых моделей По количеству затрачиваемого времени, работа м...
§1. Построение сетевых моделей Если продолжительность такой работы несоизмери...
§1. Построение сетевых моделей Работы связаны друг с другом таким образом, чт...
§1. Построение сетевых моделей Взаимосвязь работ и событий, необходимых для д...
§1. Построение сетевых моделей Для указания конкретной работы используют код...
§1. Построение сетевых моделей Любое событие может считаться наступившим толь...
§1. Построение сетевых моделей При построении сетевого графика необходимо сле...
§1. Построение сетевых моделей между одними и теми же событиями не должно быт...
§1. Построение сетевых моделей не должно быть висячих событий (т.е. не имеющи...
§1. Построение сетевых моделей Исходные данные для построения сетевой модели...
§1. Построение сетевых моделей списком работ проекта с указанием их упорядоче...
§1. Построение сетевых моделей Если исходных работ несколько, то их стрелки в...
§1. Построение сетевых моделей Если завершающих исходных работ несколько, то...
§1. Построение сетевых моделей Для устранения параллельности работ вводят доп...
§1. Построение сетевых моделей Задача 1. Постройте сетевую модель программы о...
§1. Построение сетевых моделей Решение: Из условия задачи нам известно содерж...
§1. Построение сетевых моделей Исходной работой, начинающей сетевой график, в...
§1. Построение сетевых моделей Перед тем как разослать анкеты (F), их надо ра...
A B G D C F E §1. Построение сетевых моделей В результате этих рассуждений по...
§1. Построение сетевых моделей Задача 2. Постройте сетевую модель, включающую...
§1. Построение сетевых моделей Решение: В пункте (1) условия явно указано, чт...
§1. Построение сетевых моделей Но поскольку стрелки работ А и В также и начин...
A B §1. Построение сетевых моделей В данном случае фиктивная работа (2, 3) не...
A B G D C F E H J I K L §1. Построение сетевых моделей Дальнейшее построение...
§1. Построение сетевых моделей Согласно пункту (3) условия задачи из события...
§1. Построение сетевых моделей Для отображения в сетевой модели пункта (6) ус...
§1. Построение сетевых моделей Стрелка работы L выходит из события 8, т.е. по...
§1. Построение сетевых моделей Нумерацию событий проводят после построения се...
§2. Расчет и анализ сетевых моделей Календарное планирование предусматривает...
§2. Расчет и анализ сетевых моделей Расчет сетевой модели начинают с временны...
§2. Расчет и анализ сетевых моделей Tп( i ) - поздний срок наступления событи...
§2. Расчет и анализ сетевых моделей Путь - это последовательность работ в сет...
§2. Расчет и анализ сетевых моделей Работы, лежащие на критическом пути, назы...
§2. Расчет и анализ сетевых моделей По вертикальной оси графика привязки откл...
§2. Расчет и анализ сетевых моделей Задача. Компания разрабатывает строительн...
§2. Расчет и анализ сетевых моделей Тема 14: «Сетевое планирование» * Названи...
§2. Расчет и анализ сетевых моделей Решение: Построим сетевую модель и рассчи...
§2. Расчет и анализ сетевых моделей Согласно необходимому условию два полных...
§2. Расчет и анализ сетевых моделей Путь L2, начинающийся с работы (1, 3) не...
§2. Расчет и анализ сетевых моделей Таким образом, сетевая модель имеет единс...
§2. Расчет и анализ сетевых моделей Работа D или (2, 5) не является критическ...
§2. Расчет и анализ сетевых моделей 1 0 0 0 2 0 6 6 3 0 6 6 5 3 9 12 4 0 13 1...
§2. Расчет и анализ сетевых моделей Замечания: При поиске критических путей с...
§2. Расчет и анализ сетевых моделей Вследствие этого сдвиг любой из работ кри...
§2. Расчет и анализ сетевых моделей Поэтому на графике привязки первая из раб...
§2. Расчет и анализ сетевых моделей Таким образом, мы подошли к способу опред...
§2. Расчет и анализ сетевых моделей 2) из всех работ сети (k, i ), конечное с...
§2. Расчет и анализ сетевых моделей 3) из всех работ сети (i, k), конечное со...
§2. Расчет и анализ сетевых моделей 4) продолжать п.3 до тех пор, пока не буд...
§2. Расчет и анализ сетевых моделей Следует заметить, что если в сетевой моде...
Тема 15: «Динамическое программирование» §2. Некоторые экономические задачи,...
§1. Постановка задачи Тема 15: «Динамическое программирование» Динамическое п...
§1. Постановка задачи Совокупность решений, принимаемых в начале года (кварта...
§1. Постановка задачи Динамическое программирование позволяет свести одну сло...
§1. Постановка задачи Одним из основных методов динамического программировани...
§1. Постановка задачи Использование данного принципа гарантирует, что управле...
§1. Постановка задачи В других задачах разбиение на шаги вводится искусственн...
§2. Некоторые экономические задачи, решаемые методами динамического программи...
П.1. Оптимальная стратегия замены оборудования Старение оборудования включает...
П.1. Оптимальная стратегия замены оборудования Наступает время, когда старое...
П.1. Оптимальная стратегия замены оборудования Критерием оптимальности при эт...
П.1. Оптимальная стратегия замены оборудования Введем обозначения: r(t) — сто...
П.1. Оптимальная стратегия замены оборудования Рассмотрим период N лет, в пре...
П.1. Оптимальная стратегия замены оборудования Временные же стадии процесса н...
П.1. Оптимальная стратегия замены оборудования начало конец стадии возраст об...
П.1. Оптимальная стратегия замены оборудования Функциональные уравнения, осно...
П.1. Оптимальная стратегия замены оборудования Уравнение (1) описывает N-стад...
П.1. Оптимальная стратегия замены оборудования В уравнении (1) функция r(t) –...
П.1. Оптимальная стратегия замены оборудования Нижняя строка (1) характеризуе...
П.1. Оптимальная стратегия замены оборудования Последняя функция fN-1 в (1) п...
П.1. Оптимальная стратегия замены оборудования Уравнения (1) и (2) являются р...
П.1. Оптимальная стратегия замены оборудования Расчет начинают с использовани...
П.1. Оптимальная стратегия замены оборудования Пример 1. Определить оптимальн...
П.1. Оптимальная стратегия замены оборудования Решение. Уравнения (1) и (2) з...
П.1. Оптимальная стратегия замены оборудования Для N = 1 Тема 15: «Динамическ...
П.1. Оптимальная стратегия замены оборудования Для N = 2 Тема 15: «Динамическ...
П.1. Оптимальная стратегия замены оборудования Вычисления продолжаем до тех п...
П.1. Оптимальная стратегия замены оборудования табл. 2 Тема 15: «Динамическое...
П.1. Оптимальная стратегия замены оборудования Можно не решать каждый раз ура...
П.1. Оптимальная стратегия замены оборудования По результатам вычислений и по...
П.2. Оптимальное распределение ресурсов Пусть имеется некоторое количество ре...
П.2. Оптимальное распределение ресурсов Введем обозначения: xi — количество р...
П.2. Оптимальное распределение ресурсов Сформулированную задачу можно записат...
П.2. Оптимальное распределение ресурсов Для решения задачи необходимо получит...
П.2. Оптимальное распределение ресурсов Для максимизации суммарного дохода от...
П.3. Распределение инвестиций для эффективного использования потенциала предп...
Прирост выпуска продукции на предприятиях зависит от выделенной суммы, его зн...
П.3. Распределение инвестиций для эффективного использования потенциала предп...
Решение. Разобьем решение задачи на четыре этапа по количеству предприятий, н...
Решение будем проводить согласно рекуррентным соотношениям в четыре этапа. 1-...
2-й этап. Инвестиции выделяем первому и второму предприятиям. Рекуррентное со...
при х = 60 f2(60) = max(25; 16 + 10; 8 + 20; 28) = = max(25; 26; 28; 28) = 28...
3-й этап. Финансируем 2-й этап и третье предприятие. Расчеты проводим по форм...
при х = 60 f3(60) = max(28; 20+12; 10+21; 27) = = max(28; 32; 31; 27) = 32, п...
4-й этап. Инвестиции в объеме 120 млн.р. распределяем между 3-м этапом и четв...
Максимальный прирост выпуска продукции в 64 млн.р. получен на 4-м этапе как 4...
Таким образом, инвестиции в объеме 120 млн.р. целесообразно выделить второму,...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Задача по...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Пусть зад...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Введем об...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Необходим...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Экономиче...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Пример. В...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия табл. 4 З...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия В данном...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Решение....
П.4. Минимизация затрат на строительство и эксплуатацию предприятия 1-й этап....
П.4. Минимизация затрат на строительство и эксплуатацию предприятия 2-й этап....
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Вычислим...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Определим...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Вычислим...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия 3-й этап....
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Минимальн...
П.4. Минимизация затрат на строительство и эксплуатацию предприятия Ответ. Оп...
Тема 16: «Теория массового обслуживания» §2. Системы массового обслуживания с...
§1. Введение Тема 16: «Теория массового обслуживания» Теория массового обслуж...
§1. Введение Системы, в которых, с одной стороны, возникают массовые запросы...
§1. Введение Системы массового обслуживания классифицируют по разным признака...
§1. Введение Системы массового обслуживания, у которых требования, поступающи...
§1. Введение Системы массового обслуживания, допускающие очередь, но с ограни...
§1. Введение По числу каналов обслуживания СМО делятся на одноканальные и мно...
§1. Введение Одной из форм классификации систем массового обслуживания являет...
§1. Введение Для экспоненциального распределения принимают символ М, для любо...
§2. Системы массового обслуживания с отказами СМО с отказами является такая с...
§2. Системы массового обслуживания с отказами Вероятности состояний системы о...
§2. Системы массового обслуживания с отказами А вероятность отсутствия требов...
§2. Системы массового обслуживания с отказами К основным характеристикам каче...
§2. Системы массового обслуживания с отказами В системах с отказами события о...
§2. Системы массового обслуживания с отказами Абсолютная пропускная способнос...
§3. Системы массового обслуживания с ожиданием СМО с ожиданием аналогична сис...
§3. Системы массового обслуживания с ожиданием Вероятность состояний СМО с ож...
§3. Системы массового обслуживания с ожиданием При ρ / N > 1 наблюдается явле...
§3. Системы массового обслуживания с ожиданием К основным характеристикам кач...
§3. Системы массового обслуживания с ожиданием Вероятность занятости всех узл...
§3. Системы массового обслуживания с ожиданием Средняя длина очереди Mоч : Ср...
§3. Системы массового обслуживания с ожиданием Среднее число занятых каналов...
§3. Системы массового обслуживания с ожиданием Среднее время ожидания начала...
§3. Системы массового обслуживания с ожиданием Общее время, которое проводят...
§3. Системы массового обслуживания с ожиданием Среднее время Ттр , которое тр...
§3. Системы массового обслуживания с ожиданием Задача 1. В порту имеется два...
§3. Системы массового обслуживания с ожиданием Решение: Имеем: m = 2, λ = 0,8...
§3. Системы массового обслуживания с ожиданием Итак, Тема 16: «Теория массово...
§4. Замкнутые системы массового обслуживания В замкнутых системах массового о...
§4. Замкнутые системы массового обслуживания Пусть имеется m работающих устро...
§4. Замкнутые системы массового обслуживания Обозначим через S0 состояние, пр...
§4. Замкнутые системы массового обслуживания Вероятности состояний замкнутой...
§4. Замкнутые системы массового обслуживания Средняя длина очереди: Тема 16:...
где – коэффициент бинома Ньютона. §4. Замкнутые системы массового обслуживани...
§4. Замкнутые системы массового обслуживания Среднее число свободных каналов...
§4. Замкнутые системы массового обслуживания Вероятность занятости каналов об...
§4. Замкнутые системы массового обслуживания Задача 2. Автозаправочная станци...
§4. Замкнутые системы массового обслуживания Определить: вероятность отказа;...
§4. Замкнутые системы массового обслуживания Имеем одноканальную систему с от...
§4. Замкнутые системы массового обслуживания S0 - канал свободен; S1 - канал...
§4. Замкнутые системы массового обслуживания Вероятность отказа: P1 = 0,535 О...
§4. Замкнутые системы массового обслуживания Среднее число машин, ожидающих и...
§4. Замкнутые системы массового обслуживания Pk – вероятность того, что колон...
1 из 502

Описание презентации по отдельным слайдам:

№ слайда 1

Математика в экономике

№ слайда 2

Тема 2: «Линейное программирование» §1. Общая задача линейного программирования §2. Система m линейных неравенств с n переменными §3. Геометрический смысл решения неравенств и систем неравенств §4. Геометрический метод решения задач Л.П. §5. Симплекс­метод решения задач Л.П. §6. Геометрическая интерпретация симплекс-метода §7. Аналитический способ решения задач Л.П. §8. Симплексные таблицы. Симплекс-метод в общем виде §9. Метод искусственного базиса (М-метод) §10. Теория двойственности задач §11. Двойственные задачи в общем виде сокр. Л.П. §13. Транспортная задача §12. Алгоритм составления двойственной задачи §14. Построение начального плана перевозок * © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД

№ слайда 3

§1. Общая задача линейного программирования Тема 2: «Линейное программирование» Линейное программирование (Л.П.) – это наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения. * сокр. Л.П.

№ слайда 4

§1. Общая задача линейного программирования Пусть дана система с m неравенств с n неизвестными: x1,2…n должно быть всегда ≥ 0 (по смыслу экономических задач) Z = c1x1 + c2x2 + … + cnxn → max (min) (1) Тема 2: «Линейное программирование» *

№ слайда 5

§1. Общая задача линейного программирования Необходимо найти такое решение системы X = (x1, x2, …, xn), при котором линейная функция Z принимает оптимальное, т.е. max (или min) значение. Тема 2: «Линейное программирование» *

№ слайда 6

§1. Общая задача линейного программирования Такую систему линейных неравенств (1) называют системой ограничений, а функцию Z – целевой функцией (или линейной функцией, линейной формой, функцией цели). В общем виде задачу можно записать так: Тема 2: «Линейное программирование» *

№ слайда 7

§1. Общая задача линейного программирования Оптимальным решением, или оптимальным планом задачи Л. П. называется решение: X = (x1, x2, …, xn) системы ограничений, при котором линейная функция Z принимает оптимальное значение. Тема 2: «Линейное программирование» *

№ слайда 8

§1. Общая задача линейного программирования Если система ограничений состоит из одних неравенств, то задача называется стандартной. Если же из уравнений, то задача называется канонической. Если из уравнений и неравенств, то неканонической (или общей). Тема 2: «Линейное программирование» *

№ слайда 9

§1. Общая задача линейного программирования Чтобы перейти от стандартной формы к каноническому виду вводят дополнительные неотрицательные переменные со знаком «+», если знак неравенства «≤» и со знаком «–», если знак неравенства «≥», т.е. неравенство: можно заменить выражением Тема 2: «Линейное программирование» *

№ слайда 10

§1. Общая задача линейного программирования Решение экономической задачи можно разбить на три этапа: 1) Построение экономико - математической модели; 2) Нахождение оптимального решения; 3) Практическое внедрение полученных результатов в народном хозяйстве. Тема 2: «Линейное программирование» *

№ слайда 11

§1. Общая задача линейного программирования Чтобы составить математическую модель задачи Л. П. необходимо: I) Ввести обозначения переменных. II) Исходя из цели экономических исследований, составить целевую функцию. Тема 2: «Линейное программирование» *

№ слайда 12

§1. Общая задача линейного программирования III) Учитывая ограничения в использовании экономических показателей задачи и их количественные ограничения, написать систему ограничений. Для рассмотрения решения задач Л.П. необходимо вспомнить некоторые понятия линейной алгебры. Тема 2: «Линейное программирование» *

№ слайда 13

§2. Система m линейных неравенств с n переменными В задачах Л. П. интерес представляют системы, в которых ранг матрицы A меньше числа неизвестных, т.е. r < n или иначе, максимальное число независимых уравнений или неравенств системы меньше числа переменных. Тема 2: «Линейное программирование» *

№ слайда 14

§2. Система m линейных неравенств с n переменными Пусть дана система (1). Выпишем матрицу A: Будем предполагать, что в данной системе все m неравенств (уравнений) независимы, т. е. r(A) = m, m < n . Тема 2: «Линейное программирование» *

№ слайда 15

§2. Система m линейных неравенств с n переменными Любые m переменные этой системы называются основными или базисными, если определитель матрицы коэффициентов при них отличен от 0, тогда как остальные (n – m) переменные называются свободными или не основными. Тема 2: «Линейное программирование» *

№ слайда 16

§2. Система m линейных неравенств с n переменными Основными могут быть разные группы из n переменных и отличаться они будут друг от друга только самими элементами (переменными). Таких групп максимальное число может быть т.к. могут быть случаи, что ∆ = 0, то их число n ≤ Тема 2: «Линейное программирование» *

№ слайда 17

§2. Система m линейных неравенств с n переменными Теорема. Если для системы m линейных уравнений с n переменными, где m ≤ n, ранг матрицы коэффициентов при переменных r равен m, т.е. существует хотя бы одна группа базисных переменных, то эта система является неопределённой, причём каждому произвольному набору свободных переменных соответствует одно решение системы. Тема 2: «Линейное программирование» *

№ слайда 18

§2. Система m линейных неравенств с n переменными Решение систем линейных уравнений X = (x1, x2, …, xn) называется опорным или допустимым, если оно содержит лишь неотрицательные компоненты, в противном случае решение называется недопустимым. Тема 2: «Линейное программирование» *

№ слайда 19

§2. Система m линейных неравенств с n переменными В задачах Л. П. именно такие решения представляют интерес. Решение системы m уравнений с n переменными называется базисным, если все (n – m) свободные переменные равны 0. В случае если m ≠ n систему можно решать методом Гаусса (если ранг системы равен n). Тема 2: «Линейное программирование» *

№ слайда 20

§3. Геометрический смысл решения неравенств и систем неравенств Наиболее простым и наглядным методом Л. П. является графический метод. Он применяется для решения задач Л. П. с двумя переменными, заданными в неканонической форме, и многими переменными в канонической форме при условии, что они содержат не более двух свободных переменных (т.к. в декартовой системе координат на плоскости используются две переменные). Тема 2: «Линейное программирование» *

№ слайда 21

§3.Геометрический смысл решения неравенств и систем неравенств Пусть дана система линейных неравенств: Уравнение вида a11x1 + a12x2 = в1, определяет на плоскости OX1X2 прямую, которая разбивает эту плоскость на две полуплоскости, каждая из которых лежит по одну сторону от прямой. Тема 2: «Линейное программирование» *

№ слайда 22

§3.Геометрический смысл решения неравенств и систем неравенств Сама прямая называется граничной и принадлежит обеим полуплоскостям. Координаты точек, лежащих в одной полуплоскости от прямой удовлетворяют неравенству a11x1 + a12x2 ≥ в1, а координаты точек, лежащих в другой полуплоскости удовлетворяют неравенству a11x1 + a12x2 ≤ в1. Тема 2: «Линейное программирование» *

№ слайда 23

§3.Геометрический смысл решения неравенств и систем неравенств Для определения по какую сторону от граничной прямой расположена заданная полуплоскость, надо взять произвольную точку на плоскости (лучше начало координат) и подставить координаты этой точки в неравенство. Тема 2: «Линейное программирование» *

№ слайда 24

§3.Геометрический смысл решения неравенств и систем неравенств Если неравенство справедливо, то полуплоскость обращена в сторону этой точки, если несправедливо, то в противоположную сторону от точки. Тема 2: «Линейное программирование» *

№ слайда 25

§3.Геометрический смысл решения неравенств и систем неравенств Системе неравенств удовлетворяет множество точек (x1, x2), лежащих в пересечении полуплоскостей заданных неравенствами системы. Пересечение плоскостей есть некоторая многоугольная, выпуклая область D, которая называется областью решения системы неравенств. Тема 2: «Линейное программирование» *

№ слайда 26

§3.Геометрический смысл решения неравенств и систем неравенств Множество точек называется выпуклым, если оно вместе со своими двумя точками содержит и весь отрезок, соединяющий эти точки. выпуклое множество невыпуклое множество A B C D E A F B C D E Тема 2: «Линейное программирование» *

№ слайда 27

§3.Геометрический смысл решения неравенств и систем неравенств Если область D ограничена, то её называют многоугольником решений системы неравенств (или уравнений). Многоугольник решений – это выпуклая область. Тема 2: «Линейное программирование» *

№ слайда 28

§3.Геометрический смысл решения неравенств и систем неравенств При построении области решений системы неравенств возможны следующие случаи: открытая область единственная точка A 0 x2 x1 0 x1 x2 D A 1) 2) Тема 2: «Линейное программирование» *

№ слайда 29

§3.Геометрический смысл решения неравенств и систем неравенств При построении области решений системы неравенств возможны следующие случаи: пустое множество закрытая область 0 x2 x1 0 x1 x2 D A B C E D 3) 4) Тема 2: «Линейное программирование» *

№ слайда 30

§4. Геометрический метод решения задач линейного программирования Рассмотрим задачи Л. П. в стандартной форме с двумя переменными: Тема 2: «Линейное программирование» *

№ слайда 31

§4. Геометрический метод решения задач линейного программирования Множество допустимых решений представляет собой выпуклый многоугольник (или выпуклую многогранную область), а оптимальное решение задачи находится по крайней мере в одной из угловых точек этого многоугольника решений. Тема 2: «Линейное программирование» *

№ слайда 32

Значит задачу Л. П. можно сформулировать так: среди всех точек области D найти ту, которая обращает в max (min) целевую функцию Z. Для нахождения экстремального значения целевой функции при геометрическом методе решения используется ( на плоскости X1O X2 ) вектор который обозначается . Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 33

Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора являются коэффициенты целевой функции Z, т.е. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 34

Алгоритм решения задачи: 1) Находим область допустимых решений системы ограничений задачи; 2) Строим радиус-вектор ( радиус–вектор – это вектор начало которого находится в начале координат.) Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 35

3) Проводим линию уровня ℓ0 , которая перпендикулярна . 4) Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном вектору , для задач на минимум. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 36

Решением задачи на min является первая точка, в которой прямая ℓ0 встречается с областью D при перемещении ℓ0 в положительном направлении вектора . Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 37

Zmin = Z(A) 0 x2 x1 ℓ0 C B A D E Zmax = Z(C) Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 38

При построении может получится многоугольник который не ограничен снизу, тогда задача на min решений не имеет, если же будет не ограничен сверху, то задача не имеет решения на max. 5) Находим координаты точки экстремума и значение целевой функции в ней. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 39

Замечания : 1) Если окажется, что прямая ℓ0 при перемещении параллельна одной из сторон многоугольника, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача будет иметь бесчисленное множество решений, в таком случае говорят, что задача имеет альтернативный оптимум. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 40

2) Аналогично, можно показать решение задачи линейного программирования с 3-мя переменными. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 41

Пример : Для изготовления 2-х видов продуктов P1 и P2 используется 4 вида сырья S1, S2, S3, S4. Запасы сырья, технологические коэффициенты (затраты сырья на производство единицы продукции) приведены в таблице. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 42

Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования Виды сырья Технологические коэффициенты Запасы P1 P2 S1 1 3 18 S2 2 1 16 S3 0 1 5 S4 1 0 7

№ слайда 43

Необходимо составить план выпуска продукции, обеспечивающий max прибыль, если прибыль от продажи продукции вида P1 = 2 у.е. , а P2 = 3 у.е. Решение: Обозначим x1 – количество единиц продукции вида P1, которое необходимо выпустить предприятию; x2 – количество единиц продукции P2. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 44

Тогда, используя технологические коэффициенты можно записать систему ограничений, которая показывает, что количество сырья расходуемое на изготовление продукции не может превысить имеющихся запасов: Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 45

Экономико-математическая модель задачи Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 46

Решим задачу графически: ℓ1: x1 + 3x2 = 18 ℓ2: 2x1 + x2 = 16 ℓ3: x2 = 5 (ℓ3 параллельно ОX1 ) ℓ4: x1 = 7 (ℓ4 параллельно ОX2 ) ℓ5: x1 = 0 (ОX1 ) ℓ6: x2 = 0 (ОX2 ) Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования x1 0 18 x2 6 0 x1 0 8 x2 16 0

№ слайда 47

0 x2 x1 ℓ0 ℓ1 ℓ4 ℓ3 ℓ2 ℓ5 ℓ6 A B C D E 6 5 16 7 8 18 Zmax = r (C) С: ℓ1 ∩ ℓ2 Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 48

С(6 ; 4) -5x2 = -20 x2 = 4 => x1 = 6 Zmax = Z(6 ; 4) = 2 * 6 + 3 * 4 = = 12 + 12 = 24 Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 49

Вывод: план выпуска продукции вида P1 составляет 6 единиц; вида P2 – 4 единиц. При этом максимальная прибыль составляет 24 у. е. Xopt = (6 ; 4) Zmax = 24 руб. Тема 2: «Линейное программирование» * §4. Геометрический метод решения задач линейного программирования

№ слайда 50

§5. Симплекс-метод решения задач Л.П. (Симплекс – это простейший выпуклый многоугольник) Метод является универсальным, т. к. позволяет решить практически любую задачу Л.П., записанную в каноническом виде. Тема 2: «Линейное программирование» *

№ слайда 51

§5. Симплекс-метод решения задач Л.П. Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Тема 2: «Линейное программирование» *

№ слайда 52

§5. Симплекс-метод решения задач Л.П. Этот метод был предложен американским учёным Данцингом и опубликован в 1951 г., хотя идеи этого метода разработал Канторович ещё в 1939 г. В настоящее время название “симплекс” используется независимо от формы линейных ограничений. Тема 2: «Линейное программирование» *

№ слайда 53

§5. Симплекс-метод решения задач Л.П. Схема решения задачи симплексным методом: 1) указывается способ вычисления первоначального допустимого решения задачи. 2) при помощи признака оптимальности проверяется не является ли это решение оптимальным. 3) по выбранному начальному решению строятся другие решения, более близкие к оптимальному. Тема 2: «Линейное программирование» *

№ слайда 54

§5. Симплекс-метод решения задач Л.П. Доказано, что таким путём через конечное число шагов (итераций) можно получить оптимальное решение задачи. В ходе решения задачи симплекс-методом можно установить является ли задача разрешимой. Тема 2: «Линейное программирование» *

№ слайда 55

§6. Геометрическая интерпретация симплекс-метода Из основных теорем Л. П. следует: 1) Если задача Л. П. имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многоугольника решений и совпадает по крайней мере с одним из допустимых базисных решений. Тема 2: «Линейное программирование» *

№ слайда 56

§6. Геометрическая интерпретация симплекс-метода 2) Для этого следует перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то на котором целевая функция Z принимает оптимальное решение. 3) Геометрически это соответствует перебору всех угловых точек многоугольника решений. Тема 2: «Линейное программирование» *

№ слайда 57

4) Число перебираемых допустимых базисных решений можно сократить, если перебор производить с учетом изменений целевой функции Z, т. е. добиваясь того, чтобы каждое следующее решение было лучше (по крайней мере не хуже) предыдущего. Если Z → max, то Z должно увеличиваться. Если Z → min, то Z должно уменьшаться. §6. Геометрическая интерпретация симплекс-метода Тема 2: «Линейное программирование» *

№ слайда 58

§7. Аналитический способ решения задач линейного программирования а) задача на максимум Хозяйству требуется не более десяти 3-х тонных машин и не более восьми 5-ти тонных. Отпускная цена машины одной марки 2000 у.е., другой марки 4000 у.е. Хозяйство может выделить для приобретения машин 40000 у.е. Тема 2: «Линейное программирование» *

№ слайда 59

§7.Аналитический способ решения задач линейного программирования Сколько следует приобрести машин каждой марки в отдельности, чтобы их общая суммарная грузоподъёмность была максимальной. Тема 2: «Линейное программирование» *

№ слайда 60

Решение: Пусть хозяйство приобрело: x1 – 3-х тонных машин x2 – 5-ти тонных машин Тогда план покупки: X = (x1, x2) §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 61

Эконо- мико– матема-тическая модель задачи §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 62

Решим задачу аналитически: Перейдём от стандартной формы задания к каноническому виду, введя дополнительные переменные x3 и x4: r(A) ≤ 3 §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 63

r(A) = min(3; 4) ≤ 3 §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» * r(A) = 3, значит в системе три базисные переменные – x1, x2, x3 , а x4 – свободная.

№ слайда 64

1 шаг Выразим x1, x2, x3 и Z через x4: §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 65

Итак, самое маленькое значение которое может принимать x4 = 0 : => т.к. xi ≥ 0, то §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 66

Итак, x1 = 4, x2 = 8, x3 = 6, x4 = 0. X1 = (4, 8, 6, 0) – первое допустимое базисное решение. Z = 52 , т.е. грузоподъёмность будет равна 52 тонны. Это соответствует вершине с координатами (4; 8) многоугольника решений. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 67

Так как прямая x4 входит в функцию Z со знаком “+”, то её увеличение увеличит и формулу Z, но увеличивать x4 можно до тех пор пока базисные переменные x1, x2, x3 остаются положительными. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 68

Очевидно, что сохранение не отрицательности возможно, если не нарушается ни одна из полученных во всех уравнениях границ: §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 69

Значит x4 следует вводить в базис, а x3 – в свободные (из подчеркнутого уравнения). 2 шаг x1, x2, x4 – базисные, x3 – свободная Выразим x1, x2, x4 и Z через x3: §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 70

§7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 71

§7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 72

Аналогично рассуждениям первого шага, анализируем формулу функции Z, т.к. x3 входит в функцию Z со знаком «–», то увеличение x3 приведёт к уменьшению Z, значит x3 необходимо оставить равным 0, тогда: §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 73

X2 = (10, 5, 0, 3) – новое допустимое базисное решение. Но так как x3 увеличивать нельзя, то оно является оптимальным решением: Zmax = 55. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 74

Дана система уравнений: б) задача на минимум Среди допустимых решений найти, то которое обращает в минимум целевую функцию : Z = x3 – 2x4 → min §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 75

Замечания: При определении минимума линейной функции Z возможны 2 случая: 1) Отыскание max функции F полагая, что F = –Z и учитывая, что Zmin = –Fmax . 2) Модифицировать симплекс-метод, т.е. на каждом шагу уменьшать функцию Z за счёт увеличения свободных переменных, которые входят в Z с отрицательными коэффициентами. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 76

Рассмотрим второй случай: r(A) = 2 => базисных переменных две. 1 шаг x1, x2 – базисные x3, x4 – свободные §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 77

Решим систему относительно x1 и x2: X1 = (40; 48; 0; 0) Z = 0 первое допустимое базисное решение  §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 78

Анализируем полученную формулу функции Z: Так как x3 входит в Z со знаком «+», то его увеличение только увеличит функцию Z, значит x3 оставим равным 0. Так как x4 входит в Z со знаком «–», то его увеличение уменьшит функцию Z. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 79

§7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 80

2 шаг Вводим x4 – в базис, а x2 – в свободные. Выразим x1 и x4 через x2 и x3 , начиная с подчёркнутого уравнения: §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 81

§7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 82

Снова анализируем полученную формулу функции Z: т.к. x3 и x2 входят в Z со знаком «+», то их увеличивать нельзя, значит x3 = x2 = 0, тогда x1 = 16, x4 = 6. Таким образом X2 = (16; 0; 0; 6) – второе допустимое базисное решение, которое является оптимальным: Zmin = 12. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 83

Замечания: 1) В общем виде критерий оптимальности решения задачи на максимум имеет вид: Если в выражении функции Z через свободные переменные отсутствуют положительные коэффициенты при них, то решение оптимальное. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 84

2) При решении задачи на минимум: Если в выражении функции Z через свободные переменные отсутствуют отрицательные коэффициенты при них, то решение оптимальное. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 85

3) Уравнение в котором достигается наиболее возможное значение переменной, переводимой в базисную называется разрешающим и его подчёркивают. §7.Аналитический способ решения задач линейного программирования Тема 2: «Линейное программирование» *

№ слайда 86

§8. Симплексные таблицы. Симплекс-метод в общем виде Если система ограничений задана в стандартной форме, то её переводят в каноническую путём добавления новых переменных. Тема 2: «Линейное программирование» *

№ слайда 87

§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть дана совместная система уравнений: Тема 2: «Линейное программирование» *

№ слайда 88

§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть ранг этой системы равен 3, значит базисных переменных 3. Разрешим систему относительно x1 , x2 , x3 , а x4 , x5 – свободные. Тема 2: «Линейное программирование» *

№ слайда 89

§8. Симплексные таблицы. Симплекс-метод в общем виде Причём, чтобы начальное решение было допустимым, необходимо чтобы в1 > 0, в2 > 0, в3 > 0. Тема 2: «Линейное программирование» *

№ слайда 90

§8. Симплексные таблицы. Симплекс-метод в общем виде Составим симплекс таблицу № 1: Базис Своб γ0 γ4 γ5 Тема 2: «Линейное программирование» * вi x4 x5 x1 в1 a14 a15 x2 в2 a24 a25 x3 в3 a34 a35 Z

№ слайда 91

§8. Симплексные таблицы. Симплекс-метод в общем виде Рассмотрим элементы последней строки (функция Z) и среди γ4 и γ5 (γ0 не рассматривать) найдём наименьшее положительное. Тема 2: «Линейное программирование» *

№ слайда 92

§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть это γ4, это означает, что x4 входит в Z со знаком «–», поэтому для уменьшения Z нужно увеличивать x4, но увеличивать x4 можно до тех пор, пока все базисные переменные будут неотрицательными. Тема 2: «Линейное программирование» *

№ слайда 93

§8. Симплексные таблицы. Симплекс-метод в общем виде Столбец содержащий x4 называется разрешающим. Если в последней строке нет положительных элементов, то все свободные переменные входят в функцию Z с положительными коэффициентами и Zmin достигается при равенстве 0 всех свободных переменных. Тема 2: «Линейное программирование» *

№ слайда 94

§8. Симплексные таблицы. Симплекс-метод в общем виде Составим отношение свободных членов к положительным элементам разрешающего столбца: По min отношений выбирают строку, которую называют разрешающей. Тема 2: «Линейное программирование» *

№ слайда 95

§8. Симплексные таблицы. Симплекс-метод в общем виде Пусть min является отношение в2 / a24, тогда строка x2 – разрешающая. Базис Своб Тема 2: «Линейное программирование» * вi x4 x5 x1 в1 a14 a15 x2 в2 a24 a25 x3 в3 a34 a35 Z γ0 γ4 γ5

№ слайда 96

§8. Симплексные таблицы. Симплекс-метод в общем виде Определение. Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим. Тема 2: «Линейное программирование» *

№ слайда 97

§8. Симплексные таблицы. Симплекс-метод в общем виде a24 – разрешающий элемент, значит x4 нужно перевести в базисные, а x2 в свободные переменные. Замечание: если в разрешающем столбце нет положительных коэффициентов, то функция Z минимума не достигнет, т.е. Z не ограничена снизу. Тема 2: «Линейное программирование» *

№ слайда 98

§8. Симплексные таблицы. Симплекс-метод в общем виде Алгоритм перехода к симплекс-таблице № 2: 1) Неизвестные x2 и x4 меняют местами. 2) Разрешающий элемент a24 заменяют обратной величиной. Тема 2: «Линейное программирование» *

№ слайда 99

§8. Симплексные таблицы. Симплекс-метод в общем виде 3) Остальные элементы разрешающей строки делим на разрешающий элемент. 4) Элементы разрешающего столбца, кроме разрешающего элемента, делят на разрешающий элемент и меняют знаки. Тема 2: «Линейное программирование» *

№ слайда 100

§8. Симплексные таблицы. Симплекс-метод в общем виде 5) Все остальные элементы симплекс–таблицы № 2 получают по правилу прямоугольника: Из произведения элементов диагонали, содержащей искомый элемент, вычитают произведение элементов противоположной диагонали и делят всё на элемент, противоположный искомому. Тема 2: «Линейное программирование» *

№ слайда 101

§8. Симплексные таблицы. Симплекс-метод в общем виде Тогда симплекс–таблица № 2 примет вид: Базис Своб Тема 2: «Линейное программирование» * вi x2 x5 x1 –a14 / a24 x4 в2 / a24 1 / a24 a25 / a24 x3 –a34 / a24 Z –γ4 /a24

№ слайда 102

§8. Симплексные таблицы. Симплекс-метод в общем виде Полагаем свободные переменные x2 и x5 равными нулю и получаем значение новых базисных переменных: и т.д. Тема 2: «Линейное программирование» *

№ слайда 103

§8. Симплексные таблицы. Симплекс-метод в общем виде Рассмотрим выражение для функции Z. По условию в1, в2, в3 > 0. Разрешающий элемент больше 0 (по выбору); γ4 > 0 (по выбору), значит Тема 2: «Линейное программирование» *

№ слайда 104

§8. Симплексные таблицы. Симплекс-метод в общем виде Следовательно функция Z уменьшилась. Значит, если в последней строке все элементы не положительны, т.е. ≤ 0 , то базисное решение оптимальное и задача решена. В противоположном случае переходим к симплекс–таблице № 3. Тема 2: «Линейное программирование» *

№ слайда 105

§8. Симплексные таблицы. Симплекс-метод в общем виде При решении задачи на max: 1) Разрешающий столбец выбирают также, рассматривая строку Z (кроме γ0) и среди γ4 и γ5 находят отрицательный элемент больший по модулю, этому элементу и соответствует разрешающий столбец. Тема 2: «Линейное программирование» *

№ слайда 106

§8. Симплексные таблицы. Симплекс-метод в общем виде 2) Разрешающую строку выбирают по минимуму отношений свободных членов к положительным элементам разрешающего столбца. 3) На их пересечении оказывается разрешающий элемент. 4) Алгоритм перехода к симплекс-таблице №2 тот же, что и для задачи на min. Тема 2: «Линейное программирование» *

№ слайда 107

§8. Симплексные таблицы. Симплекс-метод в общем виде 5) Критерий оптимальности на max: если в последней строке Z нет отрицательных коэффициентов. Замечание: если первоначальное базисное решение не является допустимым, то применяют метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 108

§8. Симплексные таблицы. Симплекс-метод в общем виде Задача №1. Решить задачу симплекс-методом (см. задачу о приобретении хозяйством машин наибольшей грузоподъёмности) Тема 2: «Линейное программирование» *

№ слайда 109

§8. Симплексные таблицы. Симплекс-метод в общем виде Перейдём к канонической форме задания введя дополнительные переменные x3 , x4 ≥ 0. Составим матрицу: m = 3, n = 4, r(A) ≤ 3. Тема 2: «Линейное программирование» *

№ слайда 110

§8. Симплексные таблицы. Симплекс-метод в общем виде Поэтому в системе можно оставить 3 базисных и одну свободную переменную. Пусть x1, x2, x3 – базисные, а x4 – свободная переменная. r(A) = 3. Тема 2: «Линейное программирование» *

№ слайда 111

§8. Симплексные таблицы. Симплекс-метод в общем виде Выразим базисные переменные через x4: Тема 2: «Линейное программирование» *

№ слайда 112

§8. Симплексные таблицы. Симплекс-метод в общем виде Итак, Тема 2: «Линейное программирование» *

№ слайда 113

§8. Симплексные таблицы. Симплекс-метод в общем виде Симплекс-таблица №1 Баз Св min{ 8 / 1 ; 6 / 2 } = 3 , значит x3 нужно перевести в свободные, а x4 – в базисные. Тема 2: «Линейное программирование» * вi x4 x1 4 -2 x2 8 1 x3 6 2 Z 52 -1

№ слайда 114

§8. Симплексные таблицы. Симплекс-метод в общем виде Симплекс-таблица №2 1) Разрешающий элемент «2» заменяют обратной величиной «½». 2) Элементы разрешающей строки делят на разрешающий элемент «2». Тема 2: «Линейное программирование» * Баз Св вi x4 x1 10 1 x2 5 -½ x3 3 ½ Z 55 ½

№ слайда 115

§8. Симплексные таблицы. Симплекс-метод в общем виде 3) Элементы разрешающего столбца делят на разрешающий элемент и меняют знаки. 4) Остальные элементы заменяют по правилу прямоугольника: и т.д. Тема 2: «Линейное программирование» *

№ слайда 116

§8. Симплексные таблицы. Симплекс-метод в общем виде 5) Так как в строке Z(γ0 не рассматривается), коэффициенты положительны, то план оптимальный. Z = 55, x1 = 10, x2 = 5, x3 = 0, x4 = 3. X = (10; 5; 0; 3). Тема 2: «Линейное программирование» *

№ слайда 117

§8. Симплексные таблицы. Симплекс-метод в общем виде Проверка. 10 ≤ 10 (полностью удовлетворяют требованиям по 3-тонным машинам) 5 ≤ 8 (не полностью удовлетворяют требованиям по 5-тонным машинам) 10 + 10 = 20 ≤ 20 (полностью использованы все денежные ресурсы) Zmax = 55 т. Тема 2: «Линейное программирование» *

№ слайда 118

Задача №2. Дана система ограничений в каноническом виде: §8. Симплексные таблицы. Симплекс-метод в общем виде Тема 2: «Линейное программирование» *

№ слайда 119

Среди неотрицательных решений системы найти то которое обращает функцию Z в min. §8. Симплексные таблицы. Симплекс-метод в общем виде x1, x2 – базисные; x3, x4 – свободные. Тема 2: «Линейное программирование» *

№ слайда 120

Симплекс-таблица №1. §8. Симплексные таблицы. Симплекс-метод в общем виде Тема 2: «Линейное программирование» * Базис Своб вi x3 x4 x1 40 10 4 x2 48 6 8 Z 0 -1 2

№ слайда 121

Составим симплекс-таблицу №2. §8. Симплексные таблицы. Симплекс-метод в общем виде Тема 2: «Линейное программирование» * Базис Своб вi x3 x4 x1 16 7 -½ x2 6 6/8 1/8 Z -12 -20/8 -¼

№ слайда 122

Т.к. в строке Z элементы отрицательны (γ0 не рассматривать), то по критерию оптимальности задачи на минимум, решение оптимальное, т.е. Zmin = -12. X = (16; 0; 0; 6) §8. Симплексные таблицы. Симплекс-метод в общем виде Тема 2: «Линейное программирование» *

№ слайда 123

Примечание. Если среди элементов разрешающего столбца нет положительных, то min отношений искать нельзя, поэтому Z не ограничена и задача решений не имеет. §8. Симплексные таблицы. Симплекс-метод в общем виде Тема 2: «Линейное программирование» *

№ слайда 124

§9. Метод искусственного базиса (М-метод) Если в задачи Л.П. сразу не получилось допустимое решение (т.е. вi ≤ 0 или если ограничения системы неравенств ≥ 0), то применяют метод искусственного базиса, т.е. составляется так называемая расширенная задача, которая решается симплексным методом. Тема 2: «Линейное программирование» *

№ слайда 125

§9. Метод искусственного базиса (М-метод) На основе результатов решения расширенной задачи либо находится оптимальное решение, либо устанавливается причина его отсутствия. Тема 2: «Линейное программирование» *

№ слайда 126

Алгоритм решения задачи методом искусственного базиса: 1) В каждое уравнение дающее отрицательную компоненту в базисном решении вводят искусственные переменные y1, y2, …, ym прибавляя их к левым частям уравнений. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 127

2) Эти искусственные переменные следует ввести и в целевую функцию Z. В задаче на max с коэффициентом (–M), а в задаче на min с коэффициентом (+M): M(y1, y2, …, ym), где M – очень большое число. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 128

3) Вводят новую линейную целевую функцию F = Z M(y1, y2, …, ym) и эту функцию обычно записывают в виде двух строк: F = (0 – (c1x1 + c2x2 + … + cnxn)) (m0 – (m1y1 + m2y2 + … + mmym)) §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 129

4) Эти искусственные переменные выводят из базиса делая их свободными и потом назад в базис не возвращают, поэтому эти столбцы в новой симплекс-таблице зачёркивают и не рассчитывают. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 130

5) Чтобы определить разрешающий столбец, находят в строке функции M (m + 2-я строка) наибольший положительные элемент, ему соответствует разрешающий столбец. Разрешающую строку ищут как обычно с помощью минимума отношений и переходят к новой симплекс-таблице по обычному алгоритму. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 131

6) После переноса всех искусственных переменных y1, y2, …, ym в свободные, получают допустимое базисное решение. Строка M должна получится из нулей и её отбрасывают. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 132

7) И т.к. теперь есть допустимое решение далее задачу можно решать и на max и на min. 8) Все остальные элементы симплекс-таблицы вычисляются по правилу прямоугольника. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 133

Решить задачу симплекс-методом: §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 134

Решение: в первом уравнении нет оснований вводить переменную искусственного базиса, поэтому в нём можно выделить в базис переменную x3. Во второе и третье уравнения введём две искусственные переменные y1 и y2 (для удобства в правые части уравнений). Т.о. получаем (x3, y1, y2) – базис, (x1, x2, x4, x5) – свободные. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 135

§9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 136

Составим симплекс-таблицу №1. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» * Базис Своб x1 x2 x4 x5 вi x3 3 -5 2 0 1 y1 -2 2 -1 1 4 y2 -1 3 -2 1 5 Z -1 -2 0 0 0 M -3 5 -3 2 9

№ слайда 137

В строке (m + 2), т.е. в строке M выбираем наибольший положительный элемент, т.е. 5, т.к. он максимально тянет в положительную сторону функцию цели в задаче на min. Строку выбираем по минимуму отношений: §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 138

Переходим к симплекс-таблице №2. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» * Своб Базис x1 y2 x4 x5 вi x3 4/3 -4/3 5/3 28/3 y1 -4/3 -1/3 1/3 2/3 x2 -1/3 -4/3 1/3 5/3 Z -5/3 -4/3 2/3 10/3 M -4/3 1/3 1/3 2/3

№ слайда 139

В данной таблице значения 1/3 расположены в двух столбцах, поэтому выбираем наиболее для нас удобный. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 140

Симплекс-таблица №3. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» * Своб Базис x1 y1 x5 вi x3 -4 3 13 x4 -4 -1 2 x2 -3 1 3 Z -7 2 6 M 0 0 0

№ слайда 141

После заполнения симплекс-таблицы №3 мы пришли к строке M, которая является нулевой и её отбрасывают вместе с y1 и получают первое допустимое базисное решение. Столбец вi не отрицателен поэтому теперь задачу можно решать, как на max так и на min. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 142

Анализируя строку Z видим, что x5 входит в целевую функцию Z со знаком «+», поэтому продолжаем переход к симплекс-таблице №4. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 143

Симплекс-таблица №4. Баз Св §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» * x1 x4 вi x3 8 -3 6 x5 -4 1 2 x2 1 -1 1 Z 1 -2 2

№ слайда 144

Симплекс-таблица №5. Базис Своб §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» * x3 x4 вi x1 1/8 -3/8 3/4 x5 ½ -½ 5 x2 -1/8 -5/8 ¼ Z -1/8 -13/8 10/8

№ слайда 145

Т.к. в строке Z все коэффициенты отрицательные, следовательно, решение оптимальное: X = (3/4; 14; 0; 0; 5); Zmin = 10/8. §9. Метод искусственного базиса (М-метод) Тема 2: «Линейное программирование» *

№ слайда 146

§10. Теория двойственности задач Каждой задаче линейного программирования соответствует другая задача, называемая двойственной задачей или сопряженной по отношению к исходной. Теория двойственности оказалась полезной для проведения качественных исследований. Рассмотрим задачу об использовании ресурсов. Тема 2: «Линейное программирование» *

№ слайда 147

§10. Теория двойственности задач Задача №1. У некоторого предприятия №1 (производитель продукции) имеется 2 вида сырья. Из этого сырья можно изготовить 3 вида продукции затраты сырья на единицу продукции даны в таблице: Тема 2: «Линейное программирование» *

№ слайда 148

§10. Теория двойственности задач Сырьё Прод Тема 2: «Линейное программирование» * P1 P2 P3 Запасы S1 4 2 5 800 S2 4 6 5 1400 Цена реализации 8 14 10

№ слайда 149

§10. Теория двойственности задач Найти оптимальный план производства продукции из имеющегося сырья обеспечивающий максимум прибыли. Модель задачи. x1, x2, x3 – количество единиц продукции вида Р1, Р2, Р3. Тема 2: «Линейное программирование» *

№ слайда 150

§10. Теория двойственности задач Система ограничений: Тема 2: «Линейное программирование» *

№ слайда 151

§10. Теория двойственности задач Zmax = 3267 (усл. ден. ед.) Решая задачу симплекс-методом получаем: X = (0; 700/3; 0) Вывод: для предприятия выгодно выпускать 700/3 единиц продукции Р2, а продукцию Р1 и Р3 производить не выгодно. В этом случае прибыль будет максимальной, т.е. 3267 усл. ден. ед. Тема 2: «Линейное программирование» *

№ слайда 152

§10. Теория двойственности задач Задача №2. Допустим, что у предприятия №1 есть альтернативная возможность продать все сырьё, а предприятие №2 решило закупить все ресурсы, которыми располагает предприятие №1. Цель предприятия №2 другая, а именно оно хочет установить оптимальные цены на эти ресурсы, чтобы реализовать его было выгодно, чем производить из него продукцию. Тема 2: «Линейное программирование» *

№ слайда 153

§10. Теория двойственности задач Пусть y1 – цена единицы сырья вида S1; y2 – цена единицы сырья вида S2. В одной единице готовой продукции P1 содержится 4 ед. сырья S1 по цене y1 и 2 ед. S2 по цене y2. Тема 2: «Линейное программирование» *

№ слайда 154

§10. Теория двойственности задач Система ограничений: Тема 2: «Линейное программирование» *

№ слайда 155

§10. Теория двойственности задач Под F понимается гарантированный доход от продажи сырья. Fmin = 3267 при y1 = 1 усл. ед., а y2 = 1 усл. ед. Тема 2: «Линейное программирование» *

№ слайда 156

§11. Двойственные задачи в общем виде Z = c1x1 + c2x2 + + … + cnxn → max F = в1y1 + в2y2 + + … + вnyn → max Задача №1 (исходная) Задача №2 (двойственная) Тема 2: «Линейное программирование» *

№ слайда 157

Составить такой план выпуска продукции X = (x1, x2, …, xn) при котором прибыль (или выручка) от реализации будет max при условии, что потребление ресурсов по каждому виду не превзойдёт имеющихся запасов. Найти такой набор цен (оценок) ресурсов Y = (y1, y2, …, ym) при котором общие затраты на ресурсы будут min при условии, что затраты на ресурсы при производстве продукции каждого вида не менее прибыли от реализации. §11. Двойственные задачи в общем виде Тема 2: «Линейное программирование» *

№ слайда 158

§11. Двойственные задачи в общем виде Свойства двойственных задач: 1o) В одной задаче ищется max Z, во второй min F. 2o) Коэффициенты при переменных Z одной задачи являются свободными членами системы ограничений другой задачи. 3о) Каждая из задач задана в стандартной форме. Тема 2: «Линейное программирование» *

№ слайда 159

§11. Двойственные задачи в общем виде 4o) Матрицы коэффициентов при переменных в системе ограничений являются транспонированными друг к другу. 5о) Число неравенств одной задачи совпадают с числом переменных другой. 6о) Условие неотрицательности переменных в обеих задачах Тема 2: «Линейное программирование» *

№ слайда 160

§12. Алгоритм составления двойственной задачи 1) Привести все неравенства системы ограничений исходной задачи к одному смыслу. Если на max, то к виду «≤». Если на min, то к виду «≥». Для этого, неравенства у которых данные требования не выполняются, умножают на (–1). Тема 2: «Линейное программирование» *

№ слайда 161

§12. Алгоритм составления двойственной задачи 2) Составить расширенную матрицу исходной задачи. В неё входят коэффициенты при переменных, столбец свободных членов системы ограничений, строка коэффициентов при переменных в Z. 3) Составить транспонированную матрицу. Тема 2: «Линейное программирование» *

№ слайда 162

§12. Алгоритм составления двойственной задачи 4) Сформировать двойственную задачу на основании составленной транспонированной матрицы и условии не отрицательности переменных. Тема 2: «Линейное программирование» *

№ слайда 163

Для основной задачи с использованием ресурсов: а) составим расширенную матрицу: б) транспонируем её: Тема 2: «Линейное программирование» * §12. Алгоритм составления двойственной задачи

№ слайда 164

§12. Алгоритм составления двойственной задачи 5) Составляем по числам транспонированной матрицы систему неравенств с новыми переменными для двойственной задачи (задача №2): Тема 2: «Линейное программирование» *

№ слайда 165

§12. Алгоритм составления двойственной задачи Тема 2: «Линейное программирование» *

№ слайда 166

§12. Алгоритм составления двойственной задачи 6) Мы имеем теперь две системы неравенств в стандартной форме. Перейдём к канонической форме задания систем ограничений: Тема 2: «Линейное программирование» *

№ слайда 167

основная двойственная §12. Алгоритм составления двойственной задачи Тема 2: «Линейное программирование» * (*) (**)

№ слайда 168

§12. Алгоритм составления двойственной задачи В качестве основной системы берём систему (*), т.к. систему (**) необходимо решать методом искусственного базиса (поскольку знаки в системе ограничений «≥»), поэтому: Первое допустимое решение (*) при x1 = x2 = x3 = 0 – получается (0; 0; 0; 800; 1400), т.е. все вi – положительные (чего мы не можем наблюдать в системе (**)). Тема 2: «Линейное программирование» *

№ слайда 169

§12. Алгоритм составления двойственной задачи Поэтому решаем систему (*) Симплекс-таблица №1. Базис Своб Тема 2: «Линейное программирование» * y3 y4 y5 F x1 x2 x3 вi y1 x4 4 2 5 800 y2 x5 4 6 5 1400 Z -8 -14 -10 0

№ слайда 170

§12. Алгоритм составления двойственной задачи Используя решение основной задачи сразу находим решение двойственной, т.е. меняются местами базисные и свободные переменные (сделаем обозначения в симплекс-таблице №1). Тема 2: «Линейное программирование» *

№ слайда 171

§12. Алгоритм составления двойственной задачи Симплекс-таблица №2. Базис Своб Тема 2: «Линейное программирование» * y3 y2 y5 F x1 x5 x3 вi y1 x4 8/3 -1/3 10/3 1000/3 y4 x2 2/3 1/6 5/6 1400/3 Z 4/3 7/3 5/3 9800/3

№ слайда 172

§12. Алгоритм составления двойственной задачи Итак, найдено оптимальное решение т.к. строка Z неотрицательна, поэтому записываем решение, как основной задачи, так и двойственной. Решение основной задачи берём по горизонтали в симплекс-таблице №2, а решение двойственной задачи в ней же по вертикали. Тема 2: «Линейное программирование» *

№ слайда 173

Таким образом: Zmax = 9800/3 ≈ 3267 решение основной задачи Fmin = 9800/3 ≈ 3267 решение двойственной задачи §12. Алгоритм составления двойственной задачи Тема 2: «Линейное программирование» *

№ слайда 174

§13. Транспортная задача Общая постановка задачи. Транспортная задача (Т.З.) одна из распространённых задач Л.П. Её цель – разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних, встречных и повторных перевозок. Тема 2: «Линейное программирование» *

№ слайда 175

§13. Транспортная задача Всё это сокращает время продвижения товаров, уменьшает затраты предприятий связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д. Под термином Т.З. понимается широкий круг задач не только транспортного характера. Тема 2: «Линейное программирование» *

№ слайда 176

§13. Транспортная задача Наиболее часто встречаются следующие задачи относящиеся к транспортным: – прикрепление потребителей ресурса к производителям; – привязка пунктов отправления к пунктам назначения; – взаимная привязка грузопотоков прямого и обратного направлений; Тема 2: «Линейное программирование» *

№ слайда 177

§13. Транспортная задача – отдельные задачи оптимальной загрузки промышленности оборудования; – оптимальное распределение объёмов выпуска промышленной продукции между заводами-изготовителями. Тема 2: «Линейное программирование» *

№ слайда 178

§13. Транспортная задача В общем виде задачу можно представить следующим образом: в m пунктах производства A1, A2, …, Am имеется однородный груз в кол-ве соответственно a1, a2, …, am. Этот груз необходимо доставить в n пунктов назначения B1, B2, …, Bn в кол-ве соответственно в1, в2, …, вn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна Cij. Тема 2: «Линейное программирование» *

№ слайда 179

§13. Транспортная задача Требуется составить план перевозок, позволяющий вывести все грузы и имеющий минимальную стоимость. В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нём. Т.З. могут быть закрытыми и открытыми: Тема 2: «Линейное программирование» *

№ слайда 180

1) Если , то задача называется закрытой. 2) Если , то задача называется открытой. Тема 2: «Линейное программирование» * §13. Транспортная задача

№ слайда 181

§13. Транспортная задача Поэтому если в исходных условиях дана открытая задача то её необходимо привести к закрытой форме: а) Если потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объёмом отправления. Тема 2: «Линейное программирование» *

№ слайда 182

§13. Транспортная задача в) Если запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объёмом потребления. Тарифы, связывающие фиктивные пункты с реальными имеют нулевые оценки. Тема 2: «Линейное программирование» *

№ слайда 183

§13. Транспортная задача Т.З. присущи следующие особенности: а) распределению подлежат однородные ресурсы; в) условия задачи описываются только уравнениями; с) все переменные выражаются в одинаковых единицах измерения; Тема 2: «Линейное программирование» *

№ слайда 184

§13. Транспортная задача d) во всех уравнениях коэффициенты при неизвестных равны единице; е) каждая неизвестная встречается только в 2-х уравнениях системы ограничений. Тема 2: «Линейное программирование» *

№ слайда 185

§13. Транспортная задача Т.З. как задача Л.П. может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Тема 2: «Линейное программирование» *

№ слайда 186

§13. Транспортная задача Поэтому для решения Т.З. разработан специальный метод имеющий те же этапы, что и симплексный метод, а именно: 1) Нахождение исходного опорного решения; 2) Проверка этого решения на оптимальность; 3) Переход от одного опорного решения к другому. Тема 2: «Линейное программирование» *

№ слайда 187

§13. Транспортная задача Рассмотрим закрытую Т.З. Данные запишем в распределительную таблицу, которую будем использовать для нахождения решения: Тема 2: «Линейное программирование» *

№ слайда 188

c11 §13. Транспортная задача c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 Тема 2: «Линейное программирование» * B1 B2 B3 B4 Запасы A1 x11 x12 x13 x14 а1 A2 x21 x22 x23 x24 а2 A3 x31 x32 x33 x34 а3 Потребности в1 в2 в3 в4

№ слайда 189

§13. Транспортная задача xij – количество груза, которое необходимо перевести из пункта Ai в пункт Bj. cij – тарифы транспортных расходов. Тема 2: «Линейное программирование» *

№ слайда 190

§13. Транспортная задача Тема 2: «Линейное программирование» *

№ слайда 191

§13. Транспортная задача Если m – число пунктов отправления, а n – число пунктов назначения, то уравнений составлено m + n, а переменных – m * n. Можно также показать, что если одно из уравнений системы лишнее (оно является следствием остальных), то его можно исключить из системы. Тема 2: «Линейное программирование» *

№ слайда 192

§13. Транспортная задача Таким образом в общем случае система Т.З. должна иметь m + n – 1 уравнений с m * n – переменными. Определение. План перевозок обращающий в min суммарные транспортные издержки называется оптимальным разрешением Т.З. Тема 2: «Линейное программирование» *

№ слайда 193

§14. Построение начального плана перевозок п.1. Метод северо-западного угла. Определение. Алгоритм в соответствии с которым элементы плана xij определяют, начиная с левого верхнего угла таблицы, называется методом северо-западного (С–З) угла (тарифы не учитываются). Тема 2: «Линейное программирование» *

№ слайда 194

п.1. Метод северо-западного угла. Определение. Не нулевые перевозки xij принято называть базисными, а нулевые – свободными. Начальный план перевозок составленный по методу С–З угла является допустимым. Тема 2: «Линейное программирование» *

№ слайда 195

Определение. План перевозок в которых число базисных переменных равно n + m – 1 называется невырожденным. Если меньше этого числа, то план вырожденный и значит, необходимо ввести перевозку с нулевым тарифом. п.1. Метод северо-западного угла. Тема 2: «Линейное программирование» *

№ слайда 196

Пример. На складах A1, A2, A3 имеются запасы продукции в кол-ве 90, 400, 110 т. соответственно. Потребители B1, B2, B3 должны получить эту продукцию в кол-ве 140, 300, 160 т. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. п.1. Метод северо-западного угла. Тема 2: «Линейное программирование» *

№ слайда 197

Расходы по перевозке 1 т. продукции заданы матрицей (усл. ед.): п.1. Метод северо-западного угла. Тема 2: «Линейное программирование» *

№ слайда 198

2 5 2 4 1 5 3 6 8 п.1. Метод северо-западного угла. Тема 2: «Линейное программирование» * B1 B2 B3 Запасы A1 90 A2 400 A3 110 Потреб ности 140 300 160

№ слайда 199

Метод северо-западного угла п.1. Метод северо-западного угла. Тема 2: «Линейное программирование» * /50 /0 /0 /0 /110 600 90 50 /350 /50 /0 /0 300 50 110 /0 B1 B2 B3 Запасы A1 90 A2 400 A3 110 Потребности 140 300 160

№ слайда 200

Для составления первоначального плана перевозок: 1) В плане заполняется клетка, которая соответствует минимальному тарифу. 2) Затем заполняется клетка с минимальным тарифом среди оставшихся и т.д. п.2. Метод минимального элемента. Тема 2: «Линейное программирование» * п.2. Метод минимального элемента.

№ слайда 201

3) Если на некотором шаге возникает ситуация, когда несколько минимальных элементов одинаковы, то рассматривается тот где больше груза можно перевезти. 4) В общем случае нельзя сказать какой план перевозок ближе к оптимальному, но чаще оказывается ближе метод минимального элемента. п.2. Метод минимального элемента. Тема 2: «Линейное программирование» *

№ слайда 202

Метод минимального элемента п.2. Метод минимального элемента. Тема 2: «Линейное программирование» * /50 /0 /0 /0 /60 600 90 50 / 100 / 0 / 60 300 100 60 /0 / 0 B1 B2 B3 Запасы A1 90 A2 400 A3 110 Потребности 140 300 160

№ слайда 203

п.3. Метод потенциалов решения Т.З. Как уже отмечалось ранее математическая модель Т.З. имеет ряд особенностей: 1) все ограничения представлены уравнениями. 2) коэффициенты при неизвестных в ограничениях равны либо 0, либо 1. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 204

Поэтому данные особенности позволили преобразовать симплекс-метод в метод потенциалов и тем самым существенно упростить решение Т.З. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 205

Таким образом найденное исходное опорное решение (методом min элемента либо методом С–З угла) проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение Т.З. является оптимальным, то ему соответствует система m + n действительных чисел Ui и Vj , удовлетворяющих условиям: 1) Ui + Vj = Cij – для всех заполненных клеток xij. 2) Ui + Vj ≤ Cij – для свободных клеток. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 206

Числа Ui и Vj называются потенциалами. В распределительную таблицу добавляют строку Vj и столбец Ui . Выбираем из двух опорных решений, то которое имеет минимальные затраты, т.е. метод min элемента и проверяем его на оптимальность, добавив в распределительную таблицу строку Vj и столбец Ui . п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 207

Ui Vj п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» * B1 B2 B3 Запасы 2 3 7 A1 0 90 90 A2 -2 300 100 400 A3 1 50 60 110 Потреб 140 300 160 600

№ слайда 208

Так как в системе кол-во неизвестных больше числа уравнений, то система имеет множество решений. Нас этот вариант не устраивает. Предполагаем U1 = 0. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 209

Найденные значения потенциалов заносим в таблицу и проверяем потенциальность незаполненных клеток по критерию: Ui + Vj ≤ Cij. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 210

3 ≤ 5 – потенциальна 7 ≤ 2 – не потенциальна 0 ≤ 4 – потенциальна 4 ≤ 6 – потенциальна п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 211

Так как одна клетка не потенциальна, то план не оптимальный, а значит его можно улучшить с помощью цикла, т.е. перераспределения груза по свободным клеткам, чтобы в обязательном порядке была заполнена не потенциальная клетка. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 212

2 5 2 4 1 5 3 6 8 Ui Vj 60 60 60 60 / 30 / 110 / 0 / 60 п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» * + – + – B1 B2 B3 2 3 7 A1 0 90 0 A2 -2 300 100 A3 1 50 60

№ слайда 213

Проверим полученный план на оптимальность методом потенциалов: Предполагаем U1 = 0: U1 = 0, V1 = 2, U3 = 1, V3 = 2, U2 = 3, V2 = 2. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 214

-2 ≤ 5 – потенциальна 5 ≤ 4 – не потенциальна -1 ≤ 6 – потенциальна 2 ≤ 8 – потенциальна Так как одна клетка не потенциальна, то план не оптимальный и его можно улучшить: п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 215

п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» * 2 5 2 Ui Vj 4 1 5 3 6 8 30 30 / 0 / 70 / 90 + – 0 / 30 30 30 + – B1 B2 B3 2 -2 2 A1 0 30 60 A2 3 300 100 A3 1 110

№ слайда 216

Аналогично проверим полученный план на оптимальность методом потенциалов: Предполагаем U1 = 0 : U1 = 0, V3 = 2, U2 = 3, V2 = -2, V1 = 1, U3 = 2. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 217

1 ≤ 2 – потенциальна -2 ≤ 5 – потенциальна 0 ≤ 6 – потенциальна 4 ≤ 8 – потенциальна Так как все клетки потенциальны, то план оптимальный и его улучшить нельзя. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» *

№ слайда 218

2 5 2 4 1 5 3 6 8 Ui Vj Ответ: минимальные затраты на транспортировку составляют 1280 у.е. п.3. Метод потенциалов решения Т.З. Тема 2: «Линейное программирование» * B1 B2 B3 Запасы 1 -2 2 A1 0 90 90 A2 3 30 300 70 400 A3 2 110 110 Потреб 140 300 160 600

№ слайда 219

Тема 12: «Теория игр» §2. Матричные игры §1. Классификация игр п.1 Решение матричных игр в чистых стратегиях п.2 Смешанное расширение матричной игры п.3 Свойства решений матричных игр п.4 Игры порядка 2 x 2 §3. Сведение матричных игры к задаче линейного программирования п.5 Графический метод решения игр 2 x n и m x 2 * © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД

№ слайда 220

§1. Классификация игр Тема 12: «Теория игр» Классификацию игр можно проводить по: количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д. В зависимости от количества игроков различают игры двух и п игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей. Чем больше игроков - тем больше проблем. *

№ слайда 221

§1. Классификация игр По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной. Тема 12: «Теория игр» *

№ слайда 222

§1. Классификация игр По характеру взаимодействия игры делятся на: 1) бескоалиционные – игроки не имеют права вступать в соглашения, образовывать коалиции; 2) коалиционные (кооперативные) – игроки могут вступать в коалиции. (в кооперативных играх коалиции наперёд определены) Тема 12: «Теория игр» *

№ слайда 223

§1. Классификация игр По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю); игры с ненулевой суммой. Тема 12: «Теория игр» *

№ слайда 224

§1. Классификация игр По виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др. Тема 12: «Теория игр» *

№ слайда 225

§1. Классификация игр Матричная игра - это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец - номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям). Тема 12: «Теория игр» *

№ слайда 226

§1. Классификация игр Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования. Тема 12: «Теория игр» *

№ слайда 227

§1. Классификация игр Биматричная игра - это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец - стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице - выигрыш игрока 2.) Для биматричных игр также разработана теория оптимального поведения игроков, однако решать такие игры сложнее, чем обычные матричные. Тема 12: «Теория игр» *

№ слайда 228

§1. Классификация игр Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения. Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры. Тема 12: «Теория игр» *

№ слайда 229

§1. Классификация игр Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры, обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш). Очевидно, выбирая ту или иную стратегию, каждый из игроков стремится удовлетворить свои интересы: первый – обеспечить себе максимально возможный выигрыш, а второй – минимально возможный проигрыш. Тема 12: «Теория игр» *

№ слайда 230

§1. Классификация игр Стратегия первого игрока называется оптимальной, если при её применении выигрыш первого игрока не может быть уменьшен, какими бы стратегиями ни пользовался второй игрок. Стратегия второго игрока является оптимальной в том случае, если проигрыш второго игрока не может быть увеличен, какими бы стратегиями ни пользовался первый игрок. Тема 12: «Теория игр» *

№ слайда 231

§1. Классификация игр Основными вопросами теории игр, которые возникают в коммерческой деятельности, являются: В чем состоит оптимальность поведения каждого из игроков в игре, какие свойства стратегий следует считать признаками оптимальности; Существуют ли стратегии игроков, которые обладали бы атрибутами оптимальности; Если существуют оптимальные стратегии, то как их найти? Тема 12: «Теория игр» *

№ слайда 232

§2. Матричные игры. п.1 Решение матричных игр в чистых стратегиях Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков. Первый игрок имеет m стратегий i = 1, 2, ..., m; второй имеет n стратегий j = 1, 2, ..., n. Каждой паре стратегий (i, j) поставлено в соответствие число aij , выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию. Тема 12: «Теория игр» *

№ слайда 233

п.1 Решение матричных игр в чистых стратегиях Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию ( i = 1, m ), игрок 2 – свою j-ю стратегию ( j = 1, n ), после чего игрок 1 получает выигрыш aij за счёт игрока 2 (если aij < 0, то это значит, что игрок 1 платит второму сумму |aij|). На этом игра заканчивается. Тема 12: «Теория игр» *

№ слайда 234

п.1 Решение матричных игр в чистых стратегиях Рассмотрим матричную игру следующего вида: Тема 12: «Теория игр» * Vj Ui V1 V2 V3 V4 V5 U1 3 4 5 2 1 U2 1 8 4 3 4 U3 10 3 1 7 6 U4 4 5 3 4 8

№ слайда 235

п.1 Решение матричных игр в чистых стратегиях Где Ui – стратегии игрока 1 и соответствующий выигрыш, а Vj – стратегии игрока 2 и соответствующий проигрыш (т.к. в парной игре выигрыш одного влечет за собой проигрыш другого). Игроку 1 предпочтительнее выбрать стратегию с наибольшим выигрышем, поэтому он, очевидно, выберет стратегию U3. Однако, у игрока 2 имеется выбор из пяти стратегий, поэтому он может воспользоваться стратегией V3 , и тогда выигрыш игрока 1 окажется минимальным (= 1). Тема 12: «Теория игр» *

№ слайда 236

п.1 Решение матричных игр в чистых стратегиях Аналогичные ситуации возможны и при использовании игроком 1 других стратегий. Вместе с тем, минимальные значения выигрыша для различных стратегий игрока 1 различны между собой. В этой связи для него имеет смысл выбрать такую стратегию Ui , для которой минимальный выигрыш будет наибольшим на множестве остальных стратегий. Тема 12: «Теория игр» *

№ слайда 237

п.1 Решение матричных игр в чистых стратегиях Подобный подход к решению рассматриваемой задачи называют принципом гарантированного результата. Выбранную с его использованием стратегию называют максиминной, а полученный в результате её применения выигрыш называют максиминным, или нижней ценой игры, т.е. находится (1) Тема 12: «Теория игр» *

№ слайда 238

п.1 Решение матричных игр в чистых стратегиях Определение. Число , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2, поэтому для нашего примера: Тема 12: «Теория игр» *

№ слайда 239

п.1 Решение матричных игр в чистых стратегиях Аналогичные рассуждения можно провести для игрока 2, который при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается Поэтому, для нашего примера: (2) Тема 12: «Теория игр» *

№ слайда 240

п.1 Решение матричных игр в чистых стратегиях Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1. Вывод: применяя свои чистые стратегии, игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем . Тема 12: «Теория игр» *

№ слайда 241

п.1 Решение матричных игр в чистых стратегиях Максиминные стратегии игроков становятся устойчивыми, пока оба игрока их придерживаются и выигрыш одного из них равен проигрышу другого (т.е. нет места риску). Такая игра с матрицей A имеет седловую точку в чистых стратегиях и чистую цену игры: Тема 12: «Теория игр» *

№ слайда 242

п.1 Решение матричных игр в чистых стратегиях Седловая точка - это пара чистых стратегий (i0 , j0 ) соответственно игроков 1 и 2, при которых достигается равенство . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Тема 12: «Теория игр» *

№ слайда 243

п.2 Смешанное расширение матричной игры Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Тема 12: «Теория игр» *

№ слайда 244

п.2 Смешанное расширение матричной игры Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Тема 12: «Теория игр» *

№ слайда 245

п.2 Смешанное расширение матричной игры Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью. Тема 12: «Теория игр» *

№ слайда 246

п.2 Смешанное расширение матричной игры Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий. Таким образом, если игрок 1 имеет m чистых стратегий 1, 2, ..., m, то его смешанная стратегия х - это набор чисел х = (x1, ..., xm) удовлетворяющих соотношениям: Тема 12: «Теория игр» *

№ слайда 247

п.2 Смешанное расширение матричной игры Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия у – это набор чисел y = ( y1, …, yn ) удовлетворяющих соотношениям: Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями. Тема 12: «Теория игр» *

№ слайда 248

п.2 Смешанное расширение матричной игры Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока. Тема 12: «Теория игр» *

№ слайда 249

п.2 Смешанное расширение матричной игры Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей Тема 12: «Теория игр» *

№ слайда 250

п.2 Смешанное расширение матричной игры Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е(А, х, у), а второй - за счёт своих смешанных стратегий стремится сделать Е(А, х, у) минимальным, т.е. для решения игры необходимо найти такие х и у, при которых достигается верхняя цена игры Тема 12: «Теория игр» *

№ слайда 251

п.2 Смешанное расширение матричной игры Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы х0, у0 соответственно, которые удовлетворяют равенству Тема 12: «Теория игр» *

№ слайда 252

п.2 Смешанное расширение матричной игры Величина Е(А, х0, у0) называется при этом ценой игры и обозначается через . Имеется и другое определение оптимальных смешанных стратегий: х0, у0 называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку: Тема 12: «Теория игр» *

№ слайда 253

п.2 Смешанное расширение матричной игры Оптимальные смешанные стратегии и цена игры называются решением матричной игры. и равны между собой Тема 12: «Теория игр» * Теорема (о минимаксе). Для матричной игры с любой матрицей А величины Основная теорема матричных игр

№ слайда 254

п.3 Свойства решений матричных игр Обозначим через G(X, Y, A) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х X, игрок 2 - у Y, после чего игрок 1 получает выигрыш А = А(х, у) за счёт игрока 2. Тема 12: «Теория игр» *

№ слайда 255

п.3 Свойства решений матричных игр Определение. Стратегия х1 игрока 1 доминирует (строго доминирует) над стратегией х2 , если A(x1, y) ≥ A(x2, y) y Y Определение. Стратегия у1 игрока 2 доминирует (строго доминирует) над стратегией y2, если A(x, y1) ≤ A(x, y2) x X Тема 12: «Теория игр» *

№ слайда 256

п.3 Свойства решений матричных игр При этом стратегии х2 и у2 называются доминируемыми (строго доминируемыми). Спектром смешанной стратегии игрока в конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна. Тема 12: «Теория игр» *

№ слайда 257

п.3 Свойства решений матричных игр Свойство 1. Если чистая стратегия одного из игроков содержится в спектре некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной чистой стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры. Тема 12: «Теория игр» *

№ слайда 258

п.3 Свойства решений матричных игр Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии. Игра G' = ( X', Y', А' ) называется подыгрой игры G(X, Y, A), если X' X, Y' Y, а матрица А' является подматрицей матрицы А. Матрица А' при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям X' и Y', а остальные "вычеркиваются". Всё то что "останется" после этого в матрице А и будет матрицей А'. Тема 12: «Теория игр» *

№ слайда 259

п.3 Свойства решений матричных игр Свойство 3. Пусть G = (X, Y, A) – конечная антагонистическая игра, G' = (X \ x', Y, A) – подыгра игры G, а х' - чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией , спектр которой не содержит х', тогда всякое решение (х0, у0, ) игры G' является решением игры G. Тема 12: «Теория игр» *

№ слайда 260

п.3 Свойства решений матричных игр Свойство 4. Пусть G = (X, Y, A) – конечная антагонистическая игра, G' = (X, Y \ у', А) - подыгра игры G, а, у' – чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией , спектр которой не содержит у', тогда всякое решение игры G' является решением G. Тема 12: «Теория игр» *

№ слайда 261

п.3 Свойства решений матричных игр Свойство 5. Если для чистой стратегии х' игрока 1 выполнены условия свойства 3, а для чистой стратегии у' игрока 2 выполнены условия свойства 4, то всякое решение игры G' = (X \ x', Y \ у', А) является решением игры G = (X, Y, A). Тема 12: «Теория игр» *

№ слайда 262

п.3 Свойства решений матричных игр Свойство 6. Тройка (х0, у0, ) является решением игры G = (X, Y, A) тогда и только тогда, когда (х0, у0, k + a) является решением игры С(Х, Y, к * А + а), где а - любое вещественное число, k > 0. Тема 12: «Теория игр» *

№ слайда 263

п.3 Свойства решений матричных игр Свойство 7. Для того, чтобы х0 = ( х10, ..., хi0, ..., хm0) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры , необходимо и достаточно выполнение следующих неравенств: (*) Тема 12: «Теория игр» *

№ слайда 264

п.3 Свойства решений матричных игр Аналогично для игрока 2: чтобы y0 = ( y10, ..., yj0, ..., yn0) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств: (**) Тема 12: «Теория игр» *

№ слайда 265

п.3 Свойства решений матричных игр Из последнего свойства вытекает: чтобы установить, являются ли предполагаемые (х, у) решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями получим решение матричной игры. ) ( Тема 12: «Теория игр» *

№ слайда 266

п.3 Свойства решений матричных игр Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений ( ). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3 х 3 имеем систему из 6 неравенств и 2 уравнений). Тема 12: «Теория игр» *

№ слайда 267

п.3 Свойства решений матричных игр Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства: Тема 12: «Теория игр» *

№ слайда 268

п.3 Свойства решений матричных игр Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 - чистую максиминная, а игрок 2 - чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные. Для матричных игр небольшого размера эти решения можно найти, применяя свойства 1-5. Тема 12: «Теория игр» *

№ слайда 269

п.3 Свойства решений матричных игр Замечание. Отметим, что исключение доминируемых (не строго) стратегий может привести к потере некоторых решений. Если же исключаются только строго доминируемые стратегии, то множество решений игры не изменится. Тема 12: «Теория игр» *

№ слайда 270

п.3 Свойства решений матричных игр Пример 1. Пусть G = (X, Y, A), где Х = {1, 2, 3, 4}; Y = {1, 2, 3, 4}, а функция выигрыша А задана следующим образом: Тема 12: «Теория игр» *

№ слайда 271

п.3 Свойства решений матричных игр Решение. Прежде всего заметим, что по свойству 6 достаточно решить игру G1 = (X, Y, A), где В матричной форме игра G1 определяется матрицей выигрышей: Тема 12: «Теория игр» *

№ слайда 272

п.3 Свойства решений матричных игр Элементы 4-ой строки этой матрицы «≤» соответствующих элементов 3-й строки и поэтому 3-я стратегия игрока 1 доминирует над 4-ой. Кроме того, элементы 1-го столбца матрицы А1 «≥» соответствующих элементов 2-го столбца. Следовательно, 2-ая стратегия игрока 2 доминирует над его 1-ой стратегией. Далее, из свойства 5 следует, что всякое решение игры G2 = (X / {4}, Y / {1}, A1) является решением игры G1. Тема 12: «Теория игр» *

№ слайда 273

п.3 Свойства решений матричных игр В матричной форме игру G2 можно представить матрицей Очевидно, что элементы 2-ой строки «≤» полусуммы соответствующих элементов 1-ой и 3-ей строк. Кроме того, элементы 3-го столбца матрицы А2 «≥» соответствующих элементов 2-го столбца. Тема 12: «Теория игр» *

№ слайда 274

п.3 Свойства решений матричных игр Применяя свойство 5 получим, что всякое решение игры G3 = (X / {4, 2}, Y / {1, 4}, A2) является решением игры G2, а следовательно и игры G1. Игра G3 определяется матрицей Матрица А3 не имеет седловой точки, т.к. не выполнено равенство: Тема 12: «Теория игр» *

№ слайда 275

п.3 Свойства решений матричных игр А игра G3 не имеет решения в чистых стратегиях, т.е. оптимальные стратегии игроков являются смешанными. Эти стратегии (в данном случае) легко найти из анализа структуры матрицы А3, поскольку матрица А3 симметрична, можно предположить, что игроки в оптимальной стратегии используют свои чистые стратегии равными вероятностями. Тема 12: «Теория игр» *

№ слайда 276

п.3 Свойства решений матричных игр Действительно, если игрок 1 выбирает с равными вероятностями стратегии 1 и 3, то при применении любой из двух чистых стратегий игроком 2 математическое ожидание выигрыша игрока 1 будет равно либо , либо Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно 3 / 2. Тема 12: «Теория игр» *

№ слайда 277

п.3 Свойства решений матричных игр Следовательно, указанные стратегии являются оптимальными в игре G3, а величины 3 / 2 - значением игры G3. Из предыдущего следует, что эти стратегии оптимальны и в G1. Таким образом, стратегия Х = (½, 0, ½, 0) является оптимальной стратегией игрока 1, стратегия Y = (0, ½, ½, 0) - оптимальной стратегией игрока 2 в игре G1, а значение игры G1 равно 3 / 2. В силу свойства 4 решением игры G будет 3 (X, Y, 3C / 2). Тема 12: «Теория игр» *

№ слайда 278

п.4 Игры порядка 2 x 2 В общем случае игра 2 х 2 определяется матрицей Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Тема 12: «Теория игр» *

№ слайда 279

п.4 Игры порядка 2 x 2 Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Тема 12: «Теория игр» *

№ слайда 280

п.4 Игры порядка 2 x 2 Далее, по свойству 1 следует, что а11 = а12 = и матрица имеет вид: Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению. Тема 12: «Теория игр» *

№ слайда 281

п.4 Игры порядка 2 x 2 Пусть Х = (ξ , 1 – ξ) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7): Отсюда следует, что при υ  0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Тема 12: «Теория игр» *

№ слайда 282

п.4 Игры порядка 2 x 2 Если же коэффициент пропорциональности равен 1, то матрица А принимает вид и игрок 1 имеет чистую оптимальную стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению. Тема 12: «Теория игр» *

№ слайда 283

п.4 Игры порядка 2 x 2 Следовательно, если υ  0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы А отличен от нуля. Из этого следует, что последняя система уравнений имеет единственное решение. Решая её, находим Тема 12: «Теория игр» *

№ слайда 284

п.4 Игры порядка 2 x 2 Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 Y = ( , 1 – ) удовлетворяет системе уравнений откуда Тема 12: «Теория игр» *

№ слайда 285

п.5 Графический метод решения игр 2 x n и m x 2 Пример 2. Рассмотрим игру, заданную платёжной матрицей. Тема 12: «Теория игр» *

№ слайда 286

п.5 Графический метод решения игр 2 x n и m x 2 На плоскости XОY введём систему координат и на оси ОX отложим отрезок единичной длины A1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1 – х). В частности, точке A1(0; 0) отвечает стратегия A1, точке А2(1; 0) - стратегия А2 и т.д. Тема 12: «Теория игр» *

№ слайда 287

п.5 Графический метод решения игр 2 x n и m x 2 В точках A1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью ОY ) отложим выигрыш игрока 1 при стратегии A1, а на втором - при стратегии A2. Если игрок 1 применит стратегию A1, то выиграет при стратегии B1 второго игрока – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси OY соответствуют точки B1 , B2 , B3 . Тема 12: «Теория игр» *

№ слайда 288

x y A1 A2 2 5 7 2 3 11 B1 B2 B3 N M υ 0 1 п.5 Графический метод решения игр 2 x n и m x 2 Тема 12: «Теория игр» * B1′ B2′ B3′

№ слайда 289

п.5 Графический метод решения игр 2 x n и m x 2 Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии B1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки B1′, B2′, B3′ на перпендикуляре, восстановленном в точке А2. Соединяя между собой точки B1 и B1′, B2 и B2′, B3 и B3′ и получим три прямые, расстояние до которых от оси ОX определяет средний выигрыш при любом сочетании соответствующих стратегий. Тема 12: «Теория игр» *

№ слайда 290

п.5 Графический метод решения игр 2 x n и m x 2 Например, расстояние от любой точки отрезка B1B1′ до оси OX определяет средний выигрыш υ1 при любом сочетании стратегий A1A2 (с частотами х и 1 – х) и стратегией В1 игрока 2. Это расстояние равно: (Вспомните планиметрию и рассмотрите трапецию А1В1B1′А2 ). Тема 12: «Теория игр» *

№ слайда 291

п.5 Графический метод решения игр 2 x n и m x 2 Таким образом, ординаты точек, принадлежащих ломанной В1МNB3′ определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия X* = (х, 1 – х), а её ордината равна цене игры υ. Координаты точки N находим как точку пересечения прямых B2B2′ и B3B3′. Тема 12: «Теория игр» *

№ слайда 292

п.5 Графический метод решения игр 2 x n и m x 2 Соответствующие два уравнения имеют вид: Следовательно, при цене игры . Тема 12: «Теория игр» *

№ слайда 293

п.5 Графический метод решения игр 2 x n и m x 2 Таким образом, мы можем найти оптимальную стратегию при помощи матрицы: Оптимальные стратегии для игрока 2 можно найти из системы: Следовательно, Тема 12: «Теория игр» *

№ слайда 294

п.5 Графический метод решения игр 2 x n и m x 2 Пример 3. Найти решение игры, заданной матрицей: Тема 12: «Теория игр» *

№ слайда 295

п.5 Графический метод решения игр 2 x n и m x 2 Матрица имеет размерность 2 х 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная A1КА4′ соответствует верхней границе выигрыша игрока 1, а отрезок NК – цене игры. Тема 12: «Теория игр» *

№ слайда 296

5 7 6 8 А4′ А3′ А2′ А1′ п.5 Графический метод решения игр 2 x n и m x 2 y x B1 B2 1 2 6 A4 A3 A1 K υ 0 1 4 A2 Тема 12: «Теория игр» *

№ слайда 297

п.5 Графический метод решения игр 2 x n и m x 2 Решение игры таково Тема 12: «Теория игр» *

№ слайда 298

§3. Сведение матричной игры к задаче линейного программирования Предположим, что цена игры положительна ( > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются. Тема 12: «Теория игр» *

№ слайда 299

§3. Сведение матричной игры к задаче линейного программирования Итак, пусть дана матричная игра с матрицей А порядка т х п. Согласно свойству 7 оптимальные смешанные стратегии х = (x1, ..., хm), у = (y1, ..., уn) соответственно игроков 1 и 2 и цена игры  должны удовлетворять соотношениям: (2) (1) Тема 12: «Теория игр» *

№ слайда 300

§3. Сведение матричной игры к задаче линейного программирования Разделим все уравнения и неравенства в (1) и (2) на  (это можно сделать, т.к. по предположению  > 0) и введём обозначения: Тогда (1) и (2) перепишется в виде: Тема 12: «Теория игр» *

№ слайда 301

§3. Сведение матричной игры к задаче линейного программирования Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi , чтобы цена игры  была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений рi , при которых: (3) Тема 12: «Теория игр» *

№ слайда 302

§3. Сведение матричной игры к задаче линейного программирования Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj , чтобы цена игры  была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj , при которых: (4) Тема 12: «Теория игр» *

№ слайда 303

§3. Сведение матричной игры к задаче линейного программирования Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (Л.П.). Решив эти задачи, получим значения рi , qj и . Тогда смешанные стратегии, т.е. хi и уj , получаются по формулам: Тема 12: «Теория игр» *

№ слайда 304

§3. Сведение матричной игры к задаче линейного программирования Пример 4. Найти решение игры, определяемой матрицей: Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу: Тема 12: «Теория игр» *

№ слайда 305

§3. Сведение матричной игры к задаче линейного программирования Составим теперь пару взаимно-двойственных задач: Тема 12: «Теория игр» *

№ слайда 306

§3. Сведение матричной игры к задаче линейного программирования Решим вторую из них. Составим симплекс-таблицу №1 : Тема 12: «Теория игр» * св. баз. q1 q2 q3 вi q4 1 2 0 1 q5 1 0 1 1 q6 2 1 0 1 Z -1 -1 -1 0

№ слайда 307

§3. Сведение матричной игры к задаче линейного программирования Симплекс-таблица №2 Тема 12: «Теория игр» * св. баз. q1 q4 q3 вi q2 1 / 2 -1 / 2 0 1 / 2 q5 1 0 1 1 q6 1 -1 / 2 0 1 / 2 Z -1 / 2 1 / 2 -1 1 / 2

№ слайда 308

§3. Сведение матричной игры к задаче линейного программирования Симплекс-таблица №3 Тема 12: «Теория игр» * св. баз. q1 q4 q5 вi q2 1/2 -1/2 0 1/2 q3 1 0 1 1 q6 1 0 0 1/2 Z 1/2 1/2 1 3/2

№ слайда 309

§3. Сведение матричной игры к задаче линейного программирования Из оптимальной симплекс-таблицы следует: а из соотношений двойственности следует, что Следовательно, цена игры с платёжной матрицей A1 равна а игры с платёжной матрицей А: Тема 12: «Теория игр» *

№ слайда 310

§3. Сведение матричной игры к задаче линейного программирования При этом оптимальные стратегии игроков имеют вид: Тема 12: «Теория игр» *

№ слайда 311

Тема 13: «Теория графов» §2. Способы задания графов §1. Основные понятия и определения §3. Примеры решения заданий * © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД

№ слайда 312

§1. Основные понятия и определения Тема 13: «Теория графов» Графом G называется совокупность двух непустых множеств: вершин V и ребер R, между элементами которых определено отношение инцидентности; каждое ребро r R инцидентно равно двум вершинам, которые оно соединяет. *

№ слайда 313

§1. Основные понятия и определения Тема 13: «Теория графов» * При этом вершина А(В) и ребро r называются инцидентными друг другу, а вершины А и В, являющиеся для ребра r конечными точками, называются смежными. Часто вместо r R и A V пишут r R, A G.

№ слайда 314

§1. Основные понятия и определения При изображении графов на рисунках или схемах отрезки могут быть прямо- или криволинейными; длина отрезков и расположение точек – произвольные. Две фигуры на рисунке изображают один и тот же граф. Тема 13: «Теория графов» *

№ слайда 315

§1. Основные понятия и определения Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой; в этом случае оно называется направленным или ориентированным. Граф, содержащий направленные ребра, называется ориентированным (орграфом), а ненаправленные – неориентированным (неорграфом). Ребра, инцидентные одной и той же паре вершин, называются параллельными, или кратными. Граф, содержащий кратные ребра, называется мультиграфом. Ребро, концевые вершины которого совпадают, называется петлей. Тема 13: «Теория графов» *

№ слайда 316

§1. Основные понятия и определения Граф называется конечным, если множество его элементов (вершин и ребер) конечно, и пустым, если это множество пусто. Граф без петель и кратных ребер именуется полным, если каждая пара вершин соединена ребром. Дополнением графа G называется граф , имеющий те же вершины, что и граф G, и содержащий только те ребра, которые нужно добавить к графу G, чтобы получить полный граф. Тема 13: «Теория графов» *

№ слайда 317

§1. Основные понятия и определения Локальной степенью вершины A V n-графа G называется количество ребер r(A), инцидентных вершине А. В n-графе сумма степеней всех вершин равна удвоенному числу ребер m графа. Петля добавляет число 2 в степень вершины: Тема 13: «Теория графов» *

№ слайда 318

§1. Основные понятия и определения Для вершин орграфа определяется две локальные степени: r1(A) – число ребер, исходящих из вершины А; r2(A) – число ребер, входящих в вершину А. Петля добавляет число 1 в каждую из этих степеней. В орграфе суммы степеней r1(A) и r2(A) равны количеству т ребер графа, т.е. равны между собой: Тема 13: «Теория графов» *

№ слайда 319

§1. Основные понятия и определения Два графа равны между собой, если множество вершин и ребер, определяющие эти графы, равны соответственно между собой. Путь от A1 до An называется простым, если он не проходит ни через одну вершину графа более одного раза. Циклом называется путь, в котором совпадают его начальная и конечная вершины. Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза. Тема 13: «Теория графов» *

№ слайда 320

§1. Основные понятия и определения Длиной пути называется число ребер этого пути. Аналогично, длиной цикла называется число ребер в этом цикле. Деревом называется всякий связный граф, не имеющий циклов: Тема 13: «Теория графов» *

№ слайда 321

§1. Основные понятия и определения Для каждой пары вершин дерева существует единственный соединяющий их путь. Вершина дерева со степенью, равной 1, называется висячей вершиной. Лесом называется несвязный граф, представляющий объединение деревьев. Тема 13: «Теория графов» *

№ слайда 322

§2. Способы задания графов Граф G считается полностью заданным, если нумерация его вершин и ребер зафиксирована. Аналитический способ задания – в виде двух множеств вершин V и ребер R, когда каждое ребро r определено парой инцидентных ему вершин (V’ и V’’). Граф G полностью определен двумя множествами: V(A, B, C, D, E) или R( r1, r2, r3, r4 ) множеством ребер, представленных парой своих концевых вершин: R = {(AB), (BC), (CD), (DE)} Тема 13: «Теория графов» *

№ слайда 323

§2. Способы задания графов Графический способ A B C D E r1 r2 r3 r4 Тема 13: «Теория графов» *

№ слайда 324

§2. Способы задания графов Порядок указания вершин в n-графе при описании ребер безразличен. Рассмотрим другие способы, используемые в теории графов. Матричный способ – описывает множество вершин и ребер графа и отношение инцидентности. Матрица инцидентности U = (uij) размеренностью (m x n) – матрица, в которой по вертикали указываются вершины, по горизонтали – ребра, а на пересечении i-ой вершины и j-го ребра проставляется 1, если они инцидентны и 0 – в противном случае. (если G является n-графом) Тема 13: «Теория графов» *

№ слайда 325

§2. Способы задания графов Если же G – орграф, то , если вершина Vj – начало ребра ri ; , если вершина Vj – конец ребра ri ; (любое отличное от 1, -1, 0), если ri – петля, Vj – инцидентная ей вершина; , в остальных случаях. Тема 13: «Теория графов» *

№ слайда 326

§2. Способы задания графов Матрица смежности S = (sij) – квадратная матрица размерностью (n x n), в которой по вертикали и горизонтали перечисляются все вершины. На пересечении k-ой и р-ой вершин проставляется: в случае n-графа – число ребер, соединяющих эти вершины; в случае орграфа – число ребер с началом в k-ой вершине и концом в р-ой. Тема 13: «Теория графов» *

№ слайда 327

§2. Способы задания графов Свойства матриц U(uij) и S(sij): 1o) Если два графа равны, их матрицы совпадают. 2o) Вид матриц зависит от нумерации вершин и ребер графа. 3o) Графы, отличающиеся только нумерацией вершин, являются изоморфными. Тема 13: «Теория графов» *

№ слайда 328

§2. Способы задания графов Еще один способ – задание графа списком ребер. Это таблица, состоящая из двух столбцов. В левом перечисляются все ребра r R, а в правом – инцидентные им вершины Vj′, Vj′′. Для n-графа очередность вершин в строке любая; для орграфа – на первом месте стоит номер вершины – начало ребра. Тема 13: «Теория графов» *

№ слайда 329

g 1 2 3 4 g 1 2 3 4 §3. Примеры решения заданий Пример 1. Задать матрицами инцидентности, смежности, списком ребер графы G1 и G2 : a в с d e f a в с d e f Тема 13: «Теория графов» *

№ слайда 330

§3. Примеры решения заданий Матрицы инцидентности и смежности для G1: Тема 13: «Теория графов» *

№ слайда 331

§3. Примеры решения заданий Матрицы инцидентности и смежности для G2: Тема 13: «Теория графов» *

№ слайда 332

§3. Примеры решения заданий Список ребер G2: Список ребер n-графа G1 аналогичен списку ребер орграфа G2, только последовательность указания вершин здесь безразлична. Тема 13: «Теория графов» * Ребра Вершины a 1 2 в 2 1 c 1 3 d 2 3 e 2 4 f 3 4 g 4 4

№ слайда 333

§3. Примеры решения заданий Пример 2. Представлена сетевая модель некоторого производственного процесса. Задать сетевой граф различными способами. a в с d e f g 1 2 3 4 5 6 Тема 13: «Теория графов» *

№ слайда 334

§3. Примеры решения заданий Решение. Сетевая модель представляет собой орграф, в котором ребра – операции производственного процесса, а вершины – события, характеризующие завершение одних операций и начало других. Направленность стрелок отражает последовательность наступления этих событий. Тема 13: «Теория графов» *

№ слайда 335

§3. Примеры решения заданий Орграф может быть полностью задан следующими способами: графически (см. рис.) двумя множествами: V = {1, 2, 3, 4, 5, 6} и R{(1, 2); (1, 3); (2, 4); (2, 5); (3, 4); (4, 6); (5, 6)} матрицей инцидентности: Тема 13: «Теория графов» *

№ слайда 336

§3. Примеры решения заданий матрицей смежности: списком ребер: Тема 13: «Теория графов» * Ребра Вершины a 1 2 в 1 3 c 3 4 d 2 4 e 2 5 f 5 6 g 4 6

№ слайда 337

§3. Примеры решения заданий Пример 3. Передвигаться по схеме можно только в указанном направлении, в каждом пункте быть не более 1 раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого пути наименьшая (наибольшая) длина? Тема 13: «Теория графов» *

№ слайда 338

§3. Примеры решения заданий Решение. Решить поставленную задачу помогают деревья. Строим орграф (n = 9) – схему местности. Начиная с вершины 1 последовательно перестраиваем граф в дерево. Каждая вершина столько раз получит самостоятельное значение, сколько в нее входило путей в первоначальном графе. Тема 13: «Теория графов» *

№ слайда 339

§3. Примеры решения заданий 0 ярус 1 ярус 2 ярус 3 ярус 4 ярус 5 ярус 6 ярус 7 ярус 1 2 5 4 7 8 9 7 5 8 9 8 9 9 9 8 9 7 8 9 3 5 6 9 5 7 8 9 9 8 9 9 8 9 7 8 9 Тема 13: «Теория графов» *

№ слайда 340

§3. Примеры решения заданий Наикротчайший путь заканчивается в меньшем ярусе висячей вершины дерева, самый длинный – в наибольшем ярусе. Число путей равно числу висячих вершин дерева nП = 14 . Длина кратчайшего пути Lmin (1, 5, 9) = 2. Длина самого продолжительного пути: Lmax(1, 2, 3, 6, 5, 7, 8, 9) = 7 Тема 13: «Теория графов» *

№ слайда 341

§3. Примеры решения заданий Этот пример показывает, что понятие «длина пути» в теории графов не обязательно совпадает с понятием «длина пути» в геометрии или в географии. Рисунок дерева полезен не только тем, что позволяет подсчитать число всех возможных путей, отыскать среди них кратчайший и наиболее протяженный. Он позволяет еще одновременно «увидеть» все пути и сравнить их. Тема 13: «Теория графов» *

№ слайда 342

§3. Примеры решения заданий Задача 4. Может ли так случиться, что в одной компании из 6-ти человек каждый знаком с двумя и только с двумя другими? Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками – ребром. Тема 13: «Теория графов» *

№ слайда 343

§3. Примеры решения заданий Изобразим графы, которые могут соответствовать такой компании (рис 1 и 2). Итак, ситуация вполне возможна, но на рисунке 2 изображен граф, соответствующий не одной, а двум компаниям, и участники одной из них не знакомы с участниками другой. Т.е., граф на рисунке 1 – связный, на рисунке 2 – несвязный. Рис. 2 Рис. 1 Тема 13: «Теория графов» *

№ слайда 344

Тема 14: «Сетевое планирование» §2. Расчет и анализ сетевых моделей §1. Построение сетевых моделей * © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД

№ слайда 345

§1. Построение сетевых моделей Тема 14: «Сетевое планирование» Построение сетевой модели (структурное планирование) начинается с разбиения проекта на четко определенные работы, для которых определяется продолжительность. Работа – это некоторый процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющий протяженность во времени. *

№ слайда 346

§1. Построение сетевых моделей По количеству затрачиваемого времени, работа может быть: действительной, т.е. требующей затрат времени; фиктивной, т.е. формально не требующей затрат времени. Фиктивная работа может реально существовать, например, «передача документов от одного отдела к другому». Тема 14: «Сетевое планирование» *

№ слайда 347

§1. Построение сетевых моделей Если продолжительность такой работы несоизмеримо мала по сравнению с продолжительностью других работ проекта, то формально ее принимают равной 0. Существуют фиктивные работы, которым в реальности не соответствуют никакие действия. Такие фиктивные работы только представляют связь между другими работами сетевой модели. Тема 14: «Сетевое планирование» *

№ слайда 348

§1. Построение сетевых моделей Работы связаны друг с другом таким образом, что выполнение одних работ может быть начато только после завершения некоторых других. Событие - это момент времени, когда завершаются одни работы и начинаются другие. Событие представляет собой результат проведенных работ и, в отличие от работ, не имеет протяженности во времени. Тема 14: «Сетевое планирование» *

№ слайда 349

§1. Построение сетевых моделей Взаимосвязь работ и событий, необходимых для достижения конечной цели проекта, изображается с помощью сетевого графика (сетевой модели). Работы изображаются стрелками. Они соединяют вершины, изображающие события. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Тема 14: «Сетевое планирование» *

№ слайда 350

§1. Построение сетевых моделей Для указания конкретной работы используют код работы ( i, j ), состоящий из номеров начального i-го и конечного j-го событий. работа ( i, j ) начальное событие конечное событие i j Тема 14: «Сетевое планирование» *

№ слайда 351

§1. Построение сетевых моделей Любое событие может считаться наступившим только тогда, когда закончатся все входящие в него работы. Событие, которое не имеет последующих событий и отражает конечную цель проекта, называется завершающим. Тема 14: «Сетевое планирование» *

№ слайда 352

§1. Построение сетевых моделей При построении сетевого графика необходимо следовать следующим правилам: длина стрелки не зависит от времени выполнения работы; стрелка может не быть прямолинейным отрезком; для действительных работ используются сплошные, а для фиктивных - пунктирные стрелки; каждая операция должна быть представлена только одной стрелкой; Тема 14: «Сетевое планирование» *

№ слайда 353

§1. Построение сетевых моделей между одними и теми же событиями не должно быть параллельных работ, т.е. работ с одинаковыми кодами; следует избегать пересечения стрелок; не должно быть стрелок, направленных справа налево; номер начального события должен быть меньше номера конечного события; Тема 14: «Сетевое планирование» *

№ слайда 354

§1. Построение сетевых моделей не должно быть висячих событий (т.е. не имеющих предшествующих событий), кроме исходного; не должно быть тупиковых событий (т.е. не имеющих последующих событий), кроме завершающего; не должно быть циклов (см. ниже) Тема 14: «Сетевое планирование» *

№ слайда 355

§1. Построение сетевых моделей Исходные данные для построения сетевой модели могут задаваться различными способами, например: описанием предполагаемого проекта. В этом случае необходимо самостоятельно разбить его на отдельные работы и установить их взаимные связи; списком работ проекта. В этом случае необходимо проанализировать содержание работ и установить существующие между ними связи; Тема 14: «Сетевое планирование» *

№ слайда 356

§1. Построение сетевых моделей списком работ проекта с указанием их упорядочения. В этом случае необходимо только отобразить работы на сетевом графике. Построение сетевого графика необходимо начинать с выявления исходных работ модели. Если согласно условию некоторая работа может выполняться, не ожидая окончания каких-либо других работ, то такая работа является исходной в сетевой модели и ее начальным событием является исходное событие. Тема 14: «Сетевое планирование» *

№ слайда 357

§1. Построение сетевых моделей Если исходных работ несколько, то их стрелки выходят все из одного исходного события. Если, по условию, после окончания некоторой работы не должны выполняться никакие другие работы, то такая работа является завершающей работой сетевой модели и ее конечным событием является завершающее событие. Тема 14: «Сетевое планирование» *

№ слайда 358

§1. Построение сетевых моделей Если завершающих исходных работ несколько, то их стрелки заходят все в одно завершающее событие. Если, по условию, несколько работ имеют общее начальное и общее конечное события, то они являются параллельными, имеют одинаковый код, что недопустимо. Тема 14: «Сетевое планирование» *

№ слайда 359

§1. Построение сетевых моделей Для устранения параллельности работ вводят дополнительное событие и фиктивную работу (которой в реальности не соответствует никакое действие) таким образом, чтобы конечные события работ различались (см. ниже): Тема 14: «Сетевое планирование» *

№ слайда 360

§1. Построение сетевых моделей Задача 1. Постройте сетевую модель программы опроса общественного мнения, которая включает разработку (А; 1 день) и распечатку анкет (В; 0,5 дня), прием на работу (С; 2 дня) и обучение (D; 2 дня) персонала, выбор опрашиваемых лиц (Е; 2 дня), рассылку им анкет (F; 1 день) и анализ полученных данных (G; 5 дней). Тема 14: «Сетевое планирование» *

№ слайда 361

§1. Построение сетевых моделей Решение: Из условия задачи нам известно содержание работ, но явно не указаны взаимосвязи между работами. Поэтому для их установления необходимо проанализировать смысл каждой конкретной работы и выяснить, какие из остальных работ должны ей непосредственно предшествовать. Тема 14: «Сетевое планирование» *

№ слайда 362

§1. Построение сетевых моделей Исходной работой, начинающей сетевой график, в данном случае является «прием на работу» (С), поскольку все остальные работы должны выполняться уже принятыми на работу сотрудниками. Перед выполнением всех работ по опросу общественного мнения сотрудников необходимо обучить персонал (D). Тема 14: «Сетевое планирование» *

№ слайда 363

§1. Построение сетевых моделей Перед тем как разослать анкеты (F), их надо разработать (А), распечатать (В) и выбрать опрашиваемых лиц (Е), причем работу с анкетами и выбор лиц можно выполнять одновременно. Завершающей работой проекта является анализ полученных данных (G), который нельзя выполнить без предварительной рассылки анкет (F). Тема 14: «Сетевое планирование» *

№ слайда 364

A B G D C F E §1. Построение сетевых моделей В результате этих рассуждений построим сетевую модель и пронумеруем события модели: 1 2 3 4 5 6 7 Тема 14: «Сетевое планирование» *

№ слайда 365

§1. Построение сетевых моделей Задача 2. Постройте сетевую модель, включающую работы А, В, С, ..., L, которая отображает следующее упорядочение работ : 1) А, В и С - исходные операции проекта; 2) А и В предшествуют D; 3) В предшествует Е, F и Н; 4) F и С предшествует G; 5) Е и Н предшествуют I и J; 6) С, D, F и J предшествуют К; 7) К предшествует L. Тема 14: «Сетевое планирование» *

№ слайда 366

§1. Построение сетевых моделей Решение: В пункте (1) условия явно указано, что А, В и С являются исходными работами, поэтому изобразим их тремя стрелками, выходящими из исходного события 1. Пункт (2) условия означает, что стрелки работ А и В должны окончиться в одном событии, из которого выйдет стрелка работы D. Тема 14: «Сетевое планирование» *

№ слайда 367

§1. Построение сетевых моделей Но поскольку стрелки работ А и В также и начинаются в одном событии, то имеет место параллельность работ, которая недопустима правилами построения сетевых моделей. Для ее устранения введем дополнительное событие 2, в которое войдет работа В, после чего соединим события 2 и 3, в которые входят работы А и В пунктирной стрелкой фиктивной работы. Тема 14: «Сетевое планирование» *

№ слайда 368

A B §1. Построение сетевых моделей В данном случае фиктивная работа (2, 3) не соответствует никакой реальной работе, а лишь отображает логическую связь между работами В и D. C D 1 2 3 A B C D Тема 14: «Сетевое планирование» *

№ слайда 369

A B G D C F E H J I K L §1. Построение сетевых моделей Дальнейшее построение рассмотрим с помощью рисунка (см. ниже): 1 2 3 4 8 9 5 7 6 Тема 14: «Сетевое планирование» *

№ слайда 370

§1. Построение сетевых моделей Согласно пункту (3) условия задачи из события 2, выходят три стрелки работ Е, F и Н. Согласно пункту (4) условия задачи стрелки работ С и F должны войти в общее событие, из которого выйдет стрелка работы G. Проблема с параллельностью работ Е и Н (пункт (5) условия задачи) решается путем введения дополнительного события 5 и фиктивной работы (5, 6). Тема 14: «Сетевое планирование» *

№ слайда 371

§1. Построение сетевых моделей Для отображения в сетевой модели пункта (6) условия задачи введем стрелки работ D и J в событие 7, а связь работ F и С с работой К отобразим с помощью фиктивной работы (4, 7). Стрелки работ F и С нельзя было напрямую вводить в событие 7, потому что после них должна следовать работа G, которая с работами D и J никак не связана. Тема 14: «Сетевое планирование» *

№ слайда 372

§1. Построение сетевых моделей Стрелка работы L выходит из события 8, т.е. после окончания работы К в соответствии с пунктом (7) условия задачи. Поскольку в условии не указано, что работы L, I и G предшествуют каким-либо другим работам, то эти работы являются завершающими и их стрелки войдут в завершающее событие 9. Тема 14: «Сетевое планирование» *

№ слайда 373

§1. Построение сетевых моделей Нумерацию событий проводят после построения сетевого графика, следя за тем, чтобы номер начального события каждой работы был меньше номера ее конечного события. Тема 14: «Сетевое планирование» *

№ слайда 374

§2. Расчет и анализ сетевых моделей Календарное планирование предусматривает определение моментов начала и окончания каждой работы и других временных характеристик сетевого графика. Это позволяет проанализировать сетевую модель, выявить критические работы, непосредственно определяющие срок выполнения проекта, провести оптимизацию использования ресурсов (временных, финансовых, исполнителей). Тема 14: «Сетевое планирование» *

№ слайда 375

§2. Расчет и анализ сетевых моделей Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика: Tp(i ) - ранний срок наступления события i, минимально необходимый для выполнения всех работ, которые предшествуют событию i; Тема 14: «Сетевое планирование» *

№ слайда 376

§2. Расчет и анализ сетевых моделей Tп( i ) - поздний срок наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети; R( i ) = Tn( i ) – Tp( i ) - резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом. i Тр(i) Тп(i) R(i) Тема 14: «Сетевое планирование» *

№ слайда 377

§2. Расчет и анализ сетевых моделей Путь - это последовательность работ в сетевом графике (в частном случае это одна работа), в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы. Полный путь - это путь от исходного до завершающего события. Критический путь - максимальный по продолжительности полный путь. Тема 14: «Сетевое планирование» *

№ слайда 378

§2. Расчет и анализ сетевых моделей Работы, лежащие на критическом пути, называются критическими. Критические работы имеют нулевые свободные и полные резервы. Подкритический путь - полный путь, ближайший по длительности к критическому пути. Для проведения анализа временных параметров сетевой модели используют график привязки, который отображает взаимосвязь выполняемых работ во времени. Тема 14: «Сетевое планирование» *

№ слайда 379

§2. Расчет и анализ сетевых моделей По вертикальной оси графика привязки откладываются коды работ, по горизонтальной оси - отрезки, соответствующие длительностям работ (раннее начало и раннее окончание работ). График привязки можно построить на основе данных о продолжительности работ. При этом необходимо помнить, что работа (i, j) может выполняться только после того, как будут выполнены все предшествующие ей работы (k, i). Тема 14: «Сетевое планирование» *

№ слайда 380

§2. Расчет и анализ сетевых моделей Задача. Компания разрабатывает строительный проект. Исходные данные по основным операциям проекта представлены в таблице. Постройте сетевую модель проекта, определите критические пути модели и проанализируйте, как влияет на ход выполнения проекта задержка работы D на 4 недели. Тема 14: «Сетевое планирование» *

№ слайда 381

§2. Расчет и анализ сетевых моделей Тема 14: «Сетевое планирование» * Название Непосредственно предшествующие операции Длительность, недели А — 4 В — 6 С А, В 7 D В 3 Е С 4 F D 5 G E, F 3

№ слайда 382

§2. Расчет и анализ сетевых моделей Решение: Построим сетевую модель и рассчитаем временные параметры событий. При поиске критических путей на сетевом графике будем использовать следующие условия его критичности: необходимое условие - нулевые резервы событий, лежащих, на критическом пути; достаточное условие - нулевые полные резервы работ, лежащих на критическом пути. Тема 14: «Сетевое планирование» *

№ слайда 383

§2. Расчет и анализ сетевых моделей Согласно необходимому условию два полных пути сетевой модели L1 = 1, 2, 3, 4, 6, 7 и L2 = 1, 3, 4, 6, 7 могут быть критическими. Проверим достаточное условие критичности для работ (1, 2) и (1, 3): Rп(1, 2) = Тп(2) – Тр(1) – t(1, 2)= 6 – 0 – 6 = 0; Rn(1, 3) = Tn(3) – Tp(1) – t(1, 2) = 6 – 0 – 4 = 2. Тема 14: «Сетевое планирование» *

№ слайда 384

§2. Расчет и анализ сетевых моделей Путь L2, начинающийся с работы (1, 3) не является критическим, т.к. минимум одна из его работ (1, 3) не является критической. Работа (1, 3) имеет ненулевой полный резерв, а значит может быть задержана с выполнением, что недопустимо для критических работ. Тема 14: «Сетевое планирование» *

№ слайда 385

§2. Расчет и анализ сетевых моделей Таким образом, сетевая модель имеет единственный критический путь Lкр - 1, 2, 3, 4, 6, 7 длительностью Ткр = 20 недель. За выполнением работ этого пути необходим особый контроль, т.к. любое увеличение их длительности нарушит срок выполнения проекта в целом. Тема 14: «Сетевое планирование» *

№ слайда 386

§2. Расчет и анализ сетевых моделей Работа D или (2, 5) не является критической, ее полный резерв равен 3-м неделям. Это означает, что при задержке работы в пределах 3-х недель срок выполнения проекта не будет нарушен. Поэтому, если согласно условию работа D задержится на 4 недели, то весь проект закончится на 1 неделю позже. Тема 14: «Сетевое планирование» *

№ слайда 387

§2. Расчет и анализ сетевых моделей 1 0 0 0 2 0 6 6 3 0 6 6 5 3 9 12 4 0 13 13 6 0 17 17 7 0 20 20 Тема 14: «Сетевое планирование» *

№ слайда 388

§2. Расчет и анализ сетевых моделей Замечания: При поиске критических путей следует помнить, что признаком критической работы являются нулевые значения резервов времени. Это означает, что каждая последующая критическая работа будет начинаться строго в момент окончания предыдущей критической работы. Тема 14: «Сетевое планирование» *

№ слайда 389

§2. Расчет и анализ сетевых моделей Вследствие этого сдвиг любой из работ критического пути обязательно приведет к увеличению первоначальной длительности проекта (Ткр). Кроме того, следует учесть, что критический путь является полным, т.е. соединяет исходное и завершающее события сети. Тема 14: «Сетевое планирование» *

№ слайда 390

§2. Расчет и анализ сетевых моделей Поэтому на графике привязки первая из работ критического пути всегда начинается в исходном событии сети с нулевого (начального) момента времени, а последняя из работ критического пути всегда завершается позже всех остальных работ сети в завершающем событии. Тема 14: «Сетевое планирование» *

№ слайда 391

§2. Расчет и анализ сетевых моделей Таким образом, мы подошли к способу определения критического пути на графике привязки (все найденные работы выписываются последовательно справа налево). 1) найти на графике привязки и выписать работу (i, j ), которая заканчивается позже всех остальных. Это будет последняя работа критического пути (ее конечное событие иметь номер завершающего события сети); Тема 14: «Сетевое планирование» *

№ слайда 392

§2. Расчет и анализ сетевых моделей 2) из всех работ сети (k, i ), конечное событие которых i совпадает с начальным событием i работы (i, j ), (найденной в п.1), выбрать и выписать ту, которая на графике вплотную примыкает к работе (i, j ); Тема 14: «Сетевое планирование» *

№ слайда 393

§2. Расчет и анализ сетевых моделей 3) из всех работ сети (i, k), конечное событие которых совпадает с начальным событием k работы (k, i), (найденной в п.2), выбрать и выписать ту, которая на графике вплотную примыкает к работе (k, i); Тема 14: «Сетевое планирование» *

№ слайда 394

§2. Расчет и анализ сетевых моделей 4) продолжать п.3 до тех пор, пока не будет найдена исходная работа сети, т.е. начинающаяся в нулевой момент времени (ее начальное событие будет иметь номер исходного события сети, например, 1). Тема 14: «Сетевое планирование» *

№ слайда 395

§2. Расчет и анализ сетевых моделей Следует заметить, что если в сетевой модели несколько критических путей, то, выполняя вышеописанные действия, можно обнаружить несколько работ, удовлетворяющих сформулированным требованиям. В таком случае необходимо продолжать поиск по каждой из таких работ в отдельности. Тема 14: «Сетевое планирование» *

№ слайда 396

Тема 15: «Динамическое программирование» §2. Некоторые экономические задачи, решаемые методами динамического программирования §1. Постановка задачи П. 1. Оптимальная стратегия замены оборудования П. 2. Оптимальное распределение ресурсов П. 3. Распределение инвестиций для эффективного использования потенциала предприятия П. 4. Минимизация затрат на строительство и эксплуатацию предприятия * © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД

№ слайда 397

§1. Постановка задачи Тема 15: «Динамическое программирование» Динамическое программирование — один из разделов оптимального программирования, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги). Экономический процесс является управляемым, если можно влиять на ход его развития. Под управлением понимается совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса. Например, выпуск продукции предприятием — управляемый процесс. *

№ слайда 398

§1. Постановка задачи Совокупность решений, принимаемых в начале года (квартала и т.д.) по обеспечению предприятия сырьем, замене оборудования, финансированию и т.д., является управлением. Необходимо организовать выпуск продукции так, чтобы принятые решения на отдельных этапах способствовали получению максимально возможного объема продукции или прибыли. Тема 15: «Динамическое программирование» *

№ слайда 399

§1. Постановка задачи Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения. В отличие от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует. Тема 15: «Динамическое программирование» *

№ слайда 400

§1. Постановка задачи Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Беллманом. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Тема 15: «Динамическое программирование» *

№ слайда 401

§1. Постановка задачи Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом. В некоторых задачах, решаемых методом динамического программирования, процесс управления разбивается на шаги. При распределении на несколько лет ресурсов деятельности предприятия шагом целесообразно считать временной период; при распределении средств между предприятиями — номер очередного предприятия. Тема 15: «Динамическое программирование» *

№ слайда 402

§1. Постановка задачи В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на временные отрезки (шаги). Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений. Тема 15: «Динамическое программирование» *

№ слайда 403

§2. Некоторые экономические задачи, решаемые методами динамического программирования П.1. Оптимальная стратегия замены оборудования Одной из важных экономических проблем является определение оптимальной стратегии в замене старых станков, агрегатов, машин на новые. Тема 15: «Динамическое программирование» *

№ слайда 404

П.1. Оптимальная стратегия замены оборудования Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на его ремонт и обслуживание, снижаются производительность и ликвидная стоимость. Тема 15: «Динамическое программирование» *

№ слайда 405

П.1. Оптимальная стратегия замены оборудования Наступает время, когда старое оборудование выгоднее продать, заменить новым, чем эксплуатировать ценой больших затрат; причем его можно заменить новым оборудованием того же вида или новым, более совершенным. Оптимальная стратегия замены оборудования состоит в определении оптимальных сроков замены. Тема 15: «Динамическое программирование» *

№ слайда 406

П.1. Оптимальная стратегия замены оборудования Критерием оптимальности при этом может служить прибыль от эксплуатации оборудования, которую следует оптимизировать, или суммарные затраты на эксплуатацию в течение рассматриваемого промежутка времени, подлежащие минимизации. Тема 15: «Динамическое программирование» *

№ слайда 407

П.1. Оптимальная стратегия замены оборудования Введем обозначения: r(t) — стоимость продукции, производимой за один год на единице оборудования возраста t лет; u(t) — ежегодные затраты на обслуживание оборудования возраста t лет; s(t) — остаточная стоимость оборудования возраста t лет; Р — покупная цена оборудования. Тема 15: «Динамическое программирование» *

№ слайда 408

П.1. Оптимальная стратегия замены оборудования Рассмотрим период N лет, в пределах которого требуется определить оптимальный цикл замены оборудования. Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии. Возраст оборудования отсчитывается в направлении течения процесса. Так, t = 0 соответствует случаю использования нового оборудования. Тема 15: «Динамическое программирование» *

№ слайда 409

П.1. Оптимальная стратегия замены оборудования Временные же стадии процесса нумеруются в обратном направлении по отношению к ходу процесса. Так, N = 1 относится к одной временной стадии, остающейся до завершения процесса, а N = N — к началу процесса. На каждом этапе N-стадийного процесса должно быть принято решение о сохранении или замене оборудования. Выбранный вариант должен обеспечивать получение максимальной прибыли. Тема 15: «Динамическое программирование» *

№ слайда 410

П.1. Оптимальная стратегия замены оборудования начало конец стадии возраст оборудования 0 1 2 3 t N 0 1 N - 1 t - 1 Тема 15: «Динамическое программирование» *

№ слайда 411

П.1. Оптимальная стратегия замены оборудования Функциональные уравнения, основанные на принципе оптимальности, и имеют вид: (1) (2) - сохранение - замена - сохранение - замена Тема 15: «Динамическое программирование» *

№ слайда 412

П.1. Оптимальная стратегия замены оборудования Уравнение (1) описывает N-стадийный процесс, а (2) – одностадийный. Оба уравнения состоят из двух частей: верхняя строка определяет доход, получаемый при сохранении оборудования; нижняя – доход, получаемый при замене оборудования и продолжении процесса работы на новом оборудовании. Тема 15: «Динамическое программирование» *

№ слайда 413

П.1. Оптимальная стратегия замены оборудования В уравнении (1) функция r(t) – u(t) есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N-% стадии процесса. Функция fN-1(t + 1) характеризует суммарную прибыль от (N – 1) оставшихся стадий для оборудования, возраст которого в начале осуществления этих стадий составляет (t + 1) лет. Тема 15: «Динамическое программирование» *

№ слайда 414

П.1. Оптимальная стратегия замены оборудования Нижняя строка (1) характеризуется следующим образом: функция s(t) – P представляет чистые издержки по замене оборудования, возраст которого t лет. Функция r(0) выражает доход, получаемый от нового оборудования возраста 0 лет. Предполагается, что переход от работы на оборудовании возраста t лет к работе на новом оборудовании совершается мгновенно, т.е. период замены старого оборудования и переход на работу на новом оборудовании укладываются в одну и ту же стадию. Тема 15: «Динамическое программирование» *

№ слайда 415

П.1. Оптимальная стратегия замены оборудования Последняя функция fN-1 в (1) представляет собой доход от оставшихся N – 1 стадий, до начала осуществления которых возраст оборудования составляет один год. Аналогичная интерпретация может быть дана уравнению для одностадийного процесса. Здесь нет слагаемого вида f0(t + 1), так как N принимает значение 1, 2, ..., N. Равенство f0(t) = 0 следует из определения функции fN(t). Тема 15: «Динамическое программирование» *

№ слайда 416

П.1. Оптимальная стратегия замены оборудования Уравнения (1) и (2) являются рекуррентными соотношениями, которые позволяют определить величину fN(t) в зависимости от fN-1(t + 1). Структура этих уравнений показывает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t + 1) лет, а число оставшихся стадий уменьшается с N до (N – 1). Тема 15: «Динамическое программирование» *

№ слайда 417

П.1. Оптимальная стратегия замены оборудования Расчет начинают с использования уравнения (1). Уравнения (1) и (2) позволяют оценить варианты замены и сохранения оборудования, с тем чтобы принять тот из них, который предполагает больший доход. Эти соотношения дают возможность не только выбрать линию поведения при решении вопроса о сохранении или замене оборудования, но и определить прибыль, получаемую при принятии каждого из этих решений. Тема 15: «Динамическое программирование» *

№ слайда 418

П.1. Оптимальная стратегия замены оборудования Пример 1. Определить оптимальный цикл замены оборудования при следующих исходных данных: Р = 10, S(t) = 0, f(t) = r(t) – u(t), представленных в таблице 1. табл. 1 Тема 15: «Динамическое программирование» * N 0 1 2 3 4 5 6 7 8 9 10 11 12 F(t) 10 9 8 7 6 5 4 3 2 1 0 0 0

№ слайда 419

П.1. Оптимальная стратегия замены оборудования Решение. Уравнения (1) и (2) запишем в следующем виде: (3) Тема 15: «Динамическое программирование» *

№ слайда 420

П.1. Оптимальная стратегия замены оборудования Для N = 1 Тема 15: «Динамическое программирование» *

№ слайда 421

П.1. Оптимальная стратегия замены оборудования Для N = 2 Тема 15: «Динамическое программирование» *

№ слайда 422

П.1. Оптимальная стратегия замены оборудования Вычисления продолжаем до тех пор, пока не будет выполнено условие f1(1) > f2(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае использования старого. Результаты расчетов помещаем в таблицу, момент замены отмечаем звездочкой, после чего дальнейшие вычисления по строчке прекращаем (см. далее табл. 2). Тема 15: «Динамическое программирование» *

№ слайда 423

П.1. Оптимальная стратегия замены оборудования табл. 2 Тема 15: «Динамическое программирование» * FN(t) 0 1 2 3 4 5 6 7 8 9 10 11 12 N N-1 11 10 9 8 7 6 5 4 3 2 1 f1(t) 10 9 8 7 6 5 4 3 2 1 0 0 0 f2(t) 19 17 15 13 11 9 9* f3(t) 27 24 21 18 17 17* f4(t) 34 30 26 24 24* f5(t) 40 35 32 31 30 30* f6(t) 45 41 39 37 36 35 35* f7(t) 51 48 45 43 41 41* f8(t) 58 54 51 48 48* f9(t) 64 60 56 55 54 54* f10(t) 70 65 63 61 60 60* f11(t) 75 72 69 67 66 65 65* f12(t) 82 78 75 73 72 72*

№ слайда 424

П.1. Оптимальная стратегия замены оборудования Можно не решать каждый раз уравнение (3), а вычисления проводить в таблице. Например, вычислим f4(t): f4(0) = f1(0) + f3(1) = 10 + 24 = 34 > f3(1) = 24, f4(1) = f1(1) + f3(2) = 9 + 21 = 30 > f3(1), f4(2) = f1(2) + f3(3) = 8 + 18 = 26 > f3(1), f4(3) = f1(3) + f3(4) = 7 + 17 = 24 > f3(1), f4(4) = f1(4) + f3(5) = 6 + 17 = 23 < f3(1). Дальнейшие расчеты для f4(t) прекращаем, так как: f4(4) = 23 < f3(1) = 24. Тема 15: «Динамическое программирование» *

№ слайда 425

П.1. Оптимальная стратегия замены оборудования По результатам вычислений и по линии, разграничивающей области решений сохранения и замены оборудования, находим оптимальный цикл замены оборудования. Для данной задачи он составляет 4 года. Ответ. Для получения максимальной прибыли от использования оборудования в двенадцатиэтапном процессе оптимальный цикл состоит в замене оборудования через каждые 4 года. Тема 15: «Динамическое программирование» *

№ слайда 426

П.2. Оптимальное распределение ресурсов Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между n различными предприятиями, объектами, работами и т.д. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения. Тема 15: «Динамическое программирование» *

№ слайда 427

П.2. Оптимальное распределение ресурсов Введем обозначения: xi — количество ресурсов, выделенных i-му предприятию ( ); gi(xi) — функция полезности, в данном случае gi это величина дохода от использования ресурса xi, полученного i-м предприятием; fk(x) — наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий. Тема 15: «Динамическое программирование» *

№ слайда 428

П.2. Оптимальное распределение ресурсов Сформулированную задачу можно записать в математической форме: при ограничениях: Тема 15: «Динамическое программирование» *

№ слайда 429

П.2. Оптимальное распределение ресурсов Для решения задачи необходимо получить рекуррентное соотношение, связывающее fk(x) и fk-1(x). Обозначим через хk количество ресурса, используемого k-м способом (0 ≤ хk ≤ х), тогда для (k – 1) способов остается величина ресурсов, равная (х – хk). Наибольший доход, который получается при использовании ресурса (х – хk) от первых (k – 1) способов, составит fk-1(x – хk). Тема 15: «Динамическое программирование» *

№ слайда 430

П.2. Оптимальное распределение ресурсов Для максимизации суммарного дохода от k-го и первых (k – 1) способов необходимо выбрать хk таким образом, чтобы выполнялось соотношения: Рассмотрим конкретную задачу по распределению капиталовложений между предприятиями. Тема 15: «Динамическое программирование» *

№ слайда 431

П.3. Распределение инвестиций для эффективного использования потенциала предприятия Совет директоров фирмы рассматривает предложения по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме. Для расширения производства совет директоров выделяет средства в объеме 120 млн. р. с дискретностью 20 млн. р. Тема 15: «Динамическое программирование» *

№ слайда 432

Прирост выпуска продукции на предприятиях зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице 3 (см. далее). Найти распределение средств между предприятиями, обеспечивающее максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить не более одной инвестиции. П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 433

П.3. Распределение инвестиций для эффективного использования потенциала предприятия табл. 3 Тема 15: «Динамическое программирование» * Выделяемые средства, млн. р. Прирост выпуска продукции, млн. р. Предприятие №1 Предприятие №2 Предприятие №3 Предприятие №4 20 8 10 12 11 40 16 20 21 23 60 25 28 27 30 80 36 40 38 37 100 44 48 50 51 120 62 62 63 63

№ слайда 434

Решение. Разобьем решение задачи на четыре этапа по количеству предприятий, на которых предполагается осуществить инвестиции. Рекуррентные соотношения будут иметь вид: для предприятия №1: f1(x) = g1(x1) для всех остальных предприятий: fk(x) = mах{ gk(хk) + fk-1(x – хk) }, П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 435

Решение будем проводить согласно рекуррентным соотношениям в четыре этапа. 1-й этап. Инвестиции производим только первому предприятию. Тогда: f1(20) = 8, f1(40) = 16, f1(60) = 25, П.3. Распределение инвестиций для эффективного использования потенциала предприятия f1(80) = 36, f1(100) = 44, f1(120) = 62. Тема 15: «Динамическое программирование» *

№ слайда 436

2-й этап. Инвестиции выделяем первому и второму предприятиям. Рекуррентное соотношение для 2-го этапа имеет вид: f2(x) = max{ g2(x2) + f1(x – х2) } П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тогда при х = 20 f2(20) = max(8 + 0; 0 + 10) = max(8; 10) = 10, при х = 40 f2(40) = max(16; 8 + 10; 20) = max(16; 18; 20) = 20, Тема 15: «Динамическое программирование» *

№ слайда 437

при х = 60 f2(60) = max(25; 16 + 10; 8 + 20; 28) = = max(25; 26; 28; 28) = 28, при х = 80 f2(80) = max(36; 25 + 10; 16 + 20; 8 + 28; 40) = = max(36; 35; 36; 36; 40) = 40, при х = 100 f2(100) = max(44; 36+10; 25+20; 16+28; 8+40; 48) = = max(44; 46; 45; 44; 48; 48) = 48, при х = 120 f2(120) = max(62; 44+10; 36+20; 25+28; 16+40; 8+48; 62) = max(62; 54; 56; 53; 56; 56; 62) = 62. П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 438

3-й этап. Финансируем 2-й этап и третье предприятие. Расчеты проводим по формуле: f3(x)= max{ g3(x3) + f2(x – х3) } Тогда при х = 20 f3(20) = max(10; 12) = 12 при x = 40 f3(40) = max(20; 10+12; 21) = = max(20; 22; 21) = 22, П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 439

при х = 60 f3(60) = max(28; 20+12; 10+21; 27) = = max(28; 32; 31; 27) = 32, при х = 80 f3(80) = max(40; 28+12; 20+21; 10+27; 38) = = max(40; 40; 41; 37; 38) = 41, при х = 100 f3(100)= max(48; 40+12; 28+21; 20+27; 10+38; 50) = = max(48; 52; 49; 47; 48; 50) = 52, при х = 120 f3(120) = max(62; 48+12; 40+21; 28+27; 20+38; 10+50; 63) = max(62; 60; 61; 55; 58; 60; 63) = 63. П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 440

4-й этап. Инвестиции в объеме 120 млн.р. распределяем между 3-м этапом и четвертым предприятием. при х = 120 f4(120) = max(63; 52+11; 41+23; 32+30; 22+37; 12+51; 63) = max(63; 63; 64; 62; 59; 63; 63) = 64. Получены условия управления от 1-го до 4-го этапа. Вернемся от 4-го к 1-му этапу. П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 441

Максимальный прирост выпуска продукции в 64 млн.р. получен на 4-м этапе как 41 + 23, т.е. 23 млн.р. соответствуют выделению 40 млн. р. четвертому предприятию (см. табл. 3). Согласно 3-му этапу 41 млн.р. получен как 20 + 21, т.е. 21 млн.р. соответствует выделению 40 млн.р. третьему предприятию. Согласно 2 этапу 20 млн.р. получено при выделении 40 млн.р. второму предприятию. П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 442

Таким образом, инвестиции в объеме 120 млн.р. целесообразно выделить второму, третьему и четвертому предприятиям по 40 млн.р. каждому, при этом прирост продукции будет максимальным и составит 64 млн.р. П.3. Распределение инвестиций для эффективного использования потенциала предприятия Тема 15: «Динамическое программирование» *

№ слайда 443

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Задача по оптимальному размещению производственных предприятий может быть сведена к задаче распределения ресурсов согласно критерию минимизации с учетом условий целочисленности, накладываемых на переменные. Тема 15: «Динамическое программирование» *

№ слайда 444

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Пусть задана потребность в пользующемся спросом продукте на определенной территории. Известны пункты, в которых можно построить предприятия, выпускающие данный продукт. Подсчитаны затраты на строительство и эксплуатацию таких предприятий. Необходимо так разместить предприятия, чтобы затраты на их строительство и эксплуатацию были минимальные. Тема 15: «Динамическое программирование» *

№ слайда 445

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Введем обозначения: х — количество распределяемого ресурса, которое можно использовать n различными способами; xi — количество ресурса, используемого по i-му способу (i = 1, n); gi(xi) — функция расходов, равная, например, величине затрат на производство при использовании ресурса xi по i-му способу; φk(x) — наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами. Тема 15: «Динамическое программирование» *

№ слайда 446

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Необходимо минимизировать общую величину затрат при освоении ресурса х всеми способами: при ограничениях: Тема 15: «Динамическое программирование» *

№ слайда 447

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Экономический смысл переменных хi состоит в нахождении количества предприятий, рекомендуемого для строительства в i-м пункте. Для удобства расчетов будем считать, что планируется строительство предприятий одинаковой мощности. Рассмотрим конкретную задачу по размещению предприятий. Тема 15: «Динамическое программирование» *

№ слайда 448

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Пример. В трех районах города предприниматель планирует построить пять предприятий одинаковой мощности по выпуску хлебобулочных изделий, пользующихся спросом. Необходимо разместить предприятия таким образом, чтобы обеспечить минимальные суммарные затраты на их строительство и эксплуатацию. Тема 15: «Динамическое программирование» *

№ слайда 449

П.4. Минимизация затрат на строительство и эксплуатацию предприятия табл. 4 Значения функции затрат gi(x) приведены в табл. 4. Тема 15: «Динамическое программирование» * X 1 2 3 4 5 g1(x) 11 18 35 51 76 g2(x) 10 19 34 53 75 g3(x) 9 20 36 54 74

№ слайда 450

П.4. Минимизация затрат на строительство и эксплуатацию предприятия В данном примере: gi(x) — функция расходов в млн. р., характеризующая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i-м районе; φk(x) — наименьшая величина затрат в млн. р., которые нужно произвести при строительстве и эксплуатации предприятий в первых k районах. Тема 15: «Динамическое программирование» *

№ слайда 451

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Решение. Решение задачи проводим с использованием рекуррентных соотношений: для первого района φk(x)= min gi(xi) = g1(x), для остальных районов φk(x)= min{ gk(хk) + φk-1 – (х – хk) }, k = 2, n Задачу будем решать в три этапа. Тема 15: «Динамическое программирование» *

№ слайда 452

П.4. Минимизация затрат на строительство и эксплуатацию предприятия 1-й этап. Если все предприятия построить только в первом районе, то: φ1(1) = g1(1) = 11, φ1(2) = g1(2) = 18, φ1(3) = g1(3) = 35, φ1(4) = g1(4) = 51, φ1(5) = g1(5) = 76, минимально возможные затраты при х = 5 составляют 76 млн. р. Тема 15: «Динамическое программирование» *

№ слайда 453

П.4. Минимизация затрат на строительство и эксплуатацию предприятия 2-й этап. Определим оптимальную стратегию при размещении предприятий только в первых двух районах по формуле: Определим φ2(x): φ2(x) = min{ g2(х2) + φ1 – (х – хk) }, Найдем φ2(1): g2(1) + φ1(0) = 10 + 0 = 10, g2(0) + φ1(1) = 0 + 11 = 11, φ2(1) = min(10; 11) = 10. Тема 15: «Динамическое программирование» *

№ слайда 454

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Вычислим φ2(2): φ2(2) + φ1(0) = 19 + 0 = 19, φ2(1) + φ1(1) = 10 + 11 = 21, φ2(0) + φ1(2) = 0 + 18 = 18, φ2(2) = min(19; 21; 18) = 18. Найдем φ2(3): φ2(3) + φ1(0) = 34 + 0 = 34, φ2(2) + φ1(1) = 19 + 11 = 30, φ2(1) + φ1(2) = 10 + 18 = 28, φ2(0) + φ1(3) = 0 + 35 = 35, φ2(3) = min(34; 30; 28; 35) = 28. Тема 15: «Динамическое программирование» *

№ слайда 455

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Определим φ2(4): φ2(4) + φ1(0) = 53 + 0 = 53, φ2(3) + φ1(1) = 34 + 11 = 45, φ2(2) + φ1(2) = 19 + 18 = 37, φ2(1) + φ1(3) = 10 + 35 = 45, φ2(0) + φ1(4) = 0 + 51 = 51, φ2(4) = min(53; 45; 37; 45; 51) = 37. Тема 15: «Динамическое программирование» *

№ слайда 456

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Вычислим φ2(5): φ2(5) + φ1(0) = 75 + 0 = 75, φ2(4) + φ1(1) = 53 + 11 = 64, φ2(3) + φ1(2) = 34 + 18 = 52, φ2(2) + φ1(3) = 19 + 35 = 54, φ2(1) + φ1(4) = 10 + 51 = 61, φ2(0) + φ1(5) = 0 + 76 = 76, φ2(5) = min(75; 64; 52; 54; 61; 76) = 52. Тема 15: «Динамическое программирование» *

№ слайда 457

П.4. Минимизация затрат на строительство и эксплуатацию предприятия 3-й этап. Определим оптимальную стратегию при размещении пяти предприятий в трех районах по формуле: φ3(х) = min{ g3(х3) + g2(х – х3) }. Найдем φ3(5): φ3(5) + φ2(0) = 74 + 0 = 74, φ3(4) + φ2(1) = 54 + 10 = 64, φ3(3) + φ2(2) = 36 + 18 = 54, φ3(2) + φ2(3) = 20 + 28 = 48, φ3(1) + φ2(4) = 9 + 37 = 46, φ3(0) + φ2(5) = 0 + 52 = 52, φ3(5) = min(74; 64; 54; 48; 46; 52) = 46. Тема 15: «Динамическое программирование» *

№ слайда 458

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Минимально возможные затраты при х = 5 составляют 46 млн. р. Определены затраты на строительство предприятий от 1-го до 3-го этапа. Вернемся от 3-го к 1-му этапу. Минимальные затраты в 46 млн. р. на 3-м этапе получены как 9 + 37, т.е. 9 млн. р. соответствуют строительству одного предприятия в третьем районе (см. табл. 4). Согласно 2-му этапу 37 млн. р. получены как 19 + 18, т.е. 19 млн. р. соответствуют строительству двух предприятий во втором районе. Согласно 1-му 18 млн. р. соответствуют строительству двух предприятий в первом районе. Тема 15: «Динамическое программирование» *

№ слайда 459

П.4. Минимизация затрат на строительство и эксплуатацию предприятия Ответ. Оптимальная стратегия состоит в строительстве одного предприятия в третьем районе, по два предприятия во втором и первом районах, при этом минимальная стоимость строительства и эксплуатации составит 46 млн. р. Тема 15: «Динамическое программирование» *

№ слайда 460

Тема 16: «Теория массового обслуживания» §2. Системы массового обслуживания с отказами §1. Введение §3. Системы массового обслуживания с ожиданием §4. Замкнутые системы массового обслуживания * © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД © Компьютерное оформление: Головко Р.С. студент СтГАУ факультет ФБД

№ слайда 461

§1. Введение Тема 16: «Теория массового обслуживания» Теория массового обслуживания (ТМО) помогает решать задачи, связанные с оптимизацией процессов обслуживания на железнодорожном транспорте, и является основой проектирования и анализа систем массового обслуживания (СМО). К таким СМО относятся: вагонные депо; кассы продажи пассажирских билетов; железнодорожные станции; информационные системы и т.д. *

№ слайда 462

§1. Введение Системы, в которых, с одной стороны, возникают массовые запросы (требования) на выполнение каких-либо видов услуг, а с другой стороны, происходит удовлетворение этих запросов, называются системами массового обслуживания. Система массового обслуживания включает следующие элементы: источник требований, входящий поток требований, очередь, обслуживающее устройство (обслуживающий аппарат, канал обслуживания), выходящий поток требований. Тема 16: «Теория массового обслуживания» *

№ слайда 463

§1. Введение Системы массового обслуживания классифицируют по разным признакам. Одним из признаков является ожидание требования начала обслуживания. В соответствии с этим признаком системы подразделяются на следующие виды: 1) системы массового обслуживания с потерями (отказами); 2) системы массового обслуживания с ожиданием; 3) системы массового обслуживания с ограниченной длиной очереди; 4) системы массового обслуживания с ограниченным временем ожидания. Тема 16: «Теория массового обслуживания» *

№ слайда 464

§1. Введение Системы массового обслуживания, у которых требования, поступающие в момент, когда все приборы обслуживания заняты, получают отказ и теряются, называются системами с потерями или отказами. Системы массового обслуживания, у которых возможно появление как угодно длинной очереди требований к обслуживающему устройству, называются системами с ожиданием. Тема 16: «Теория массового обслуживания» *

№ слайда 465

§1. Введение Системы массового обслуживания, допускающие очередь, но с ограниченным числом мест в ней, называются системами с ограниченной длиной очереди. Системы массового обслуживания, допускающие очередь, но с ограниченным сроком пребывания каждого требования в ней, называются системами с ограниченным временем ожидания. Тема 16: «Теория массового обслуживания» *

№ слайда 466

§1. Введение По числу каналов обслуживания СМО делятся на одноканальные и многоканальные. По месту нахождения источника требований СМО делятся на разомкнутые, когда источник находится вне системы, и замкнутые, когда источник находится в самой системе. К последнему виду относится, например, станочный участок, в котором станки являются источником неисправностей, а, следовательно, и требований на их обслуживание. Тема 16: «Теория массового обслуживания» *

№ слайда 467

§1. Введение Одной из форм классификации систем массового обслуживания является кодовая (символьная) классификация Д. Кендалла. При этой классификации характеристику системы записывают в виде трех, четырех или пяти символов, например, А|B|S, где А – тип распределения входящего потока требований, В – тип распределения времени обслуживания, S – число каналов обслуживания. Тема 16: «Теория массового обслуживания» *

№ слайда 468

§1. Введение Для экспоненциального распределения принимают символ М, для любого (произвольного) распределения - символ G. Запись М|М|3 означает, что входящий поток требований пуассоновский (простейший), время обслуживания распределено по экспоненциальному закону, в системе имеется три канала обслуживания. Четвертый символ указывает допустимую длину очереди, а пятый — порядок отбора (приоритета) требований. Тема 16: «Теория массового обслуживания» *

№ слайда 469

§2. Системы массового обслуживания с отказами СМО с отказами является такая система, в которой приходящие для обслуживания требования, в случае занятости всех каналов обслуживания, сразу ее покидают. Тема 16: «Теория массового обслуживания» *

№ слайда 470

§2. Системы массового обслуживания с отказами Вероятности состояний системы определяются из выражения: где k = 1, 2, …, N; N – общее число каналов; – нагрузка;  - интенсивность входящего потока требований; µ - интенсивность (производительность) одного канала (прибора) обслуживания; Тема 16: «Теория массового обслуживания» *

№ слайда 471

§2. Системы массового обслуживания с отказами А вероятность отсутствия требований P0 определяется из выражения: Тема 16: «Теория массового обслуживания» *

№ слайда 472

§2. Системы массового обслуживания с отказами К основным характеристикам качества обслуживания рассматриваемой СМО относятся: вероятность отказа среднее число занятых узлов обслуживания среднее число свободных узлов обслуживания Тема 16: «Теория массового обслуживания» *

№ слайда 473

§2. Системы массового обслуживания с отказами В системах с отказами события отказа и обслуживания составляют полную группу событий, отсюда: Относительная пропускная способность определяется по формуле: Тема 16: «Теория массового обслуживания» *

№ слайда 474

§2. Системы массового обслуживания с отказами Абсолютная пропускная способность СМО с отказами равняется: Коэффициент занятости узлов обслуживания определяется отношением средним числом занятых каналов к общему числу каналов: Тема 16: «Теория массового обслуживания» *

№ слайда 475

§3. Системы массового обслуживания с ожиданием СМО с ожиданием аналогична системе массового обслуживания с ограниченной длиной очереди при условии, что граница очереди отодвигается в бесконечность. Тема 16: «Теория массового обслуживания» *

№ слайда 476

§3. Системы массового обслуживания с ожиданием Вероятность состояний СМО с ожиданием находят по формулам: для k = 1, 2, …, N для k = N + 1, …, N + k, …, N + ∞ Тема 16: «Теория массового обслуживания» *

№ слайда 477

§3. Системы массового обслуживания с ожиданием При ρ / N > 1 наблюдается явление «взрыва» – неограниченный рост средней длины очереди, поэтому для определения P0 должно выполняться ограничивающее условие ρ / N > 1, и с учетом его запишем выражение: Тема 16: «Теория массового обслуживания» *

№ слайда 478

§3. Системы массового обслуживания с ожиданием К основным характеристикам качества обслуживания СМО с ожиданием относят: Вероятность наличия очереди Pоч , т.е. вероятность того, что число требований в системе больше числа узлов: Тема 16: «Теория массового обслуживания» *

№ слайда 479

§3. Системы массового обслуживания с ожиданием Вероятность занятости всех узлов системы Pзан : Среднее число требований в системе МТР : Тема 16: «Теория массового обслуживания» *

№ слайда 480

§3. Системы массового обслуживания с ожиданием Средняя длина очереди Mоч : Среднее число свободных каналов обслуживания Мсв : Тема 16: «Теория массового обслуживания» *

№ слайда 481

§3. Системы массового обслуживания с ожиданием Среднее число занятых каналов обслуживания Мзан : Коэффициент простоя K0 и коэффициент загрузки Kз каналов обслуживания системы: Тема 16: «Теория массового обслуживания» *

№ слайда 482

§3. Системы массового обслуживания с ожиданием Среднее время ожидания начала обслуживания Тож для требования, поступившего в систему: Тема 16: «Теория массового обслуживания» *

№ слайда 483

§3. Системы массового обслуживания с ожиданием Общее время, которое проводят в очереди все требования, поступившие в систему за единицу времени Тоож : Тема 16: «Теория массового обслуживания» *

№ слайда 484

§3. Системы массового обслуживания с ожиданием Среднее время Ттр , которое требование проводит в системе обслуживания: Суммарное время, которое в среднем проводят в системе все требования, поступившие за единицу времени Тстр : Тема 16: «Теория массового обслуживания» *

№ слайда 485

§3. Системы массового обслуживания с ожиданием Задача 1. В порту имеется два причала для разгрузки грузовых судов. Интенсивность потока судов равна 0,8 судов в сутки. Среднее время разгрузки одного судна составляет 2 суток. Предполагается, что очередь ожидающих разгрузки судов может быть неограниченной длины. Найти среднее время пребывания судна в порту. Тема 16: «Теория массового обслуживания» *

№ слайда 486

§3. Системы массового обслуживания с ожиданием Решение: Имеем: m = 2, λ = 0,8 сут-1, , , Находим: Тема 16: «Теория массового обслуживания» *

№ слайда 487

§3. Системы массового обслуживания с ожиданием Итак, Тема 16: «Теория массового обслуживания» *

№ слайда 488

§4. Замкнутые системы массового обслуживания В замкнутых системах массового обслуживания источник требований находится внутри системы, и интенсивность потока требований зависит от состояния самой системы. Чаще всего потоком требований в такой системе является поток неисправностей от некоторой группы работающих устройств. Тема 16: «Теория массового обслуживания» *

№ слайда 489

§4. Замкнутые системы массового обслуживания Пусть имеется m работающих устройств, которые могут выходить из строя за счет неисправностей. Имеется также N приборов (каналов) обслуживания этих требований. В качестве таких каналов могут выступать и люди. Обычно предполагают, что N < m. Тема 16: «Теория массового обслуживания» *

№ слайда 490

§4. Замкнутые системы массового обслуживания Обозначим через S0 состояние, при котором все устройства работают, а приборы обслуживания не заняты; S1 - состояние, при котором одно устройство вышло из строя и обслуживается одним прибором обслуживания; SN – N устройств не работают, и все приборы заняты обслуживанием; Sm - все устройства не работают, из них N обслуживаются и (m – N ) ждут обслуживания. Тема 16: «Теория массового обслуживания» *