- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
Задача, модель которой содержит только линейные функции искомых переменных, называется задачей линейного программирования (ЛП).
В общем случае модель задачи лп имеет вид
(4.1)
при ограничениях:
(4.2)
(4.3)
где L – критерий (целевая функция), называемый также линейной формой;
n - количество переменных;
Ci – параметры (коэффициенты) критерия, не все Ci =0;
(4.2) - функциональные условия (ограничения);
– параметры условий (могут быть любыми действительными числами, но одновременно все не могут равняться нулю при i=const). Во многих случаях они имеют смысл удельных величин (расхода или затрат на единицу переменной, содержания в единице переменной и т. п.).
bi – параметры (свободные члены), отражающие возможности по ресурсам, допустимые или требуемые значения показателей и т.п. (могут быть любыми действительными числами).
На часть или все переменные накладывается условие неотрицательности (4.3).
Задача состоит в определении таких значений переменных, удовлетворяющих условиям (4.2) и (4.3), которые доставляют в зависимости от контекста максимум или минимум линейной форме.
Сбалансированная транспортная задача
Транспортная задача - это модель ситуации, в которой требуется найти оптимальный план перевозки некоторого груза из конечного числа пунктов поставки (отправления) с заданными объемами производства в конечное число пунктов потребления (назначения) с требуемыми объемами потребностей при известных затратах на перевозку единицы груза между каждой парой пунктов поставки и потребления. Предполагается, что удельные затраты не зависят от количества перевозимого груза. Здесь под оптимальным понимается план, минимизирующий суммарные затраты на перевозки.
В качестве примера рассмотрим задачу с двумя пунктами отправления и тремя пунктами назначения, схема которой показана на рис.4.1. Здесь а1 и а2 – количество груза, которым располагают пункты отправления, b1, b2, b3 – потребности в грузе пунктов назначения.
Задача является сбалансированной, если суммарная потребность равна суммарной возможности. В нашем примере это значит, что
Рис. 4.1.
Если ввести обозначения:
xij - количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения;
Сij – затраты на перевозку единицы груза из i-го пункта отправления в j-й пункт назначения,
то исходные данные вместе с переменными можно представить в одной таблице (табл. 4.3):
Таблица 4.3
Пункты |
B1 |
B2 |
B3 |
Количество груза |
A1 |
С11 Х11 |
С12 Х12 |
С13 Х13 |
a1 |
A2 |
С21 Х21 |
С22 Х22 |
С23 Х23 |
a2 |
Потребность в грузе |
b1 |
b2 |
b3 |
|
Так как необходимо минимизировать суммарные затраты по перевозке, то целевая функция запишется в виде
L=C11x11 + C12x12 + C23x23→min.
Каждый пункт назначения должен получить требуемое количество груза. Отсюда следуют равенства, соответствующие этим пунктам
B1: x11+x21=b1;
B2: x12+x22=b2;
B3: x13+x23=b3.
Поскольку задача сбалансированная, весь груз из пунктов отправления должен быть вывезен. Это требование отражается в модели двумя равенствами:
А1: х11+х12+х13=а1;
А2: х21+х22+х23=а2.
Наконец, физический смысл переменных накладывает на них ограничение неотрицательности
xij0.
В результате мы получили модель транспортной задачи, содержащей только линейные функции. Очевидно, что характер модели не изменится при увеличении числа пунктов.
Игра двух лиц с нулевой суммой как задача линейного программирования
Рассмотрим платежную матрицу игры двух лиц, не имеющую седловых точек,
|
B1 |
B2 |
… |
Bn |
A1 |
U11 |
U12 |
… |
U1n |
A2 |
U21 |
U22 |
… |
U2n |
… |
… |
… |
… |
… |
Am |
Um1 |
Um2 |
… |
Umn |
где платежи Uij имеют смысл выигрышей игрока A.
Как известно, такая игра имеет решение в области смешанных стратегий. Пусть X=(x1,x2,…,xm) – распределение вероятностей на стратегиях игрока A. Тогда согласно принципу гарантированного результата этот игрок будет выбирать такое поведение (распределение X *), которое максимизирует наименьший ожидаемый выигрыш
.
Обозначим через минимальный ожидаемый выигрыш
.
Отсюда очевидно, что не больше каждого ожидаемого выигрыша, и так как цель – максимальный выигрыш, то приходим к следующей эквивалентной задаче
L=→max
при ограничениях
,
хi0.
Это обычная линейная задача, оптимальное значение критерия которой L*=* есть цена игры. Ее решение определяет оптимальное поведение игрока А.
Для игрока B линейная модель строится аналогично, но тот же критерий минимизируется, так как уже имеет смысл максимального проигрыша, а ограничения на вероятности yj соответствуют строкам платежной матрицы и записываются как неравенства “меньше или равно”.