- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
10. Геометрия задач лп, базисные решения, вырожденность.
Геометрические представления позволяют лучше уяснить рассмотренные свойства задач ЛП.
Размерность пространства задачи k равна разности числа переменных и числа ограничений-равенств. Поэтому для модели в стандартной форме k= , а для канонической модели k= - m. Как отмечалось раньше, значение k не зависит от формы записи модели и является фиксированным для конкретной задачи.
Очевидно, что геометрические построения возможны для k 3. Сначала мы рассмотрим задачи на плоскости (k= 2), а затем сделаем обобщение на многомерное пространство.
В качестве первого примера решим графически задачу оптимального планирования из разд. 4.2.2:
-
Исходная модель
L=7x1+5x2→max,
1) 2x1+3x219,
2) 2x1+x213,
3) 3x212,
4) 3x117,
5) x10,
6) x20.
Каноническая модель
L=7x1+5x2→max,
2x1+3x2+x3=19,
2x1+x2+ x4=13,
3x2+x5=12,
3x1+x6=17,
xj0.
Чтобы решить задачу, надо сначала построить допустимое множество, а затем по целевой функции найти на нем точку или множество с максимальным значением критерия.
Допустимое множество задачи находится как пересечение допустимых множеств, построенных по отдельным условиям задачи. В нашем примере таких множеств 6.
Построение множества начинается с определения его границы. Возьмем условия неотрицательности переменных:
x10, следовательно, уравнение границы x1 =0 (ось х2) и допустимое множество – правая полуплскость (включая границу); х20, уравнение границы х2=0 (ось x1), допустимое множество – верхняя полуплоскость. Таким образом, при неотрицательности всех переменых допустимое множество задачи ЛП всегда лежит в первом квадранте.
Теперь перейдем к построению допустимых множеств по функциональным условиям. Граница по 1-му условию 2х1+3х2=19 (из канонической модели имеем альтернативное уравнение x3=0) представляет собой прямую, для построения которой достаточно нанести любые 2 точки. Например, положив х1=0, из уравнения получим х2=19/3 (точка на оси х2); вторую точку возьмем на оси х1: х2=0 и тогда х1=19/2. Чтобы определить, с какой стороны прямой выполняется условие, достаточно проверить одну точку вне границы. В качестве такой точки проще всего брать начало коодинат, в котором левая часть условия всегда равна нулю.. Наше условие 1) выполняется в этой точке, следовательно, допустимое множество – юго-западная полуплоскость. В противном случае получили бы северо-восточную полуплоскость.
Аналогично записываем уравнения границ и проводим соответствующие прямые по условию 2): из исходной модели 2х1+х2=13 и канонческой модели х4=0; по условию 3): 3х2=12 и х5=0; по условию 4): 3х1=17 и х6=0. Нетрудно убедиться, что каждое из этих условий выполняется с той стороны своей границы, с которой находится начало коодинат.
Н аходя пересечение шести построенных допустимых множеств, получаем выпуклый шестиугольник (рис. 4.2) – частный случай выпуклого многогранника.
Из бесконечного множества допустимых решений, принадлежащих этому многоугольнику, необходимо найти то, которое дает максимум критерия. Для этого нам нужно знать “поведение“ критерия на допустимом множестве. С этой целью построим линии уровня критерия L=Const.. Так как критерий линейный, то линии уровня – это множество параллельных прямых с постоянным градиентом (направлением возрастания значений критерия). Поэтому для определения этого направления достаточно иметь 2 линии уровня. Конкретные значения L можно брать любые, но так, чтобы соответствующие прямые оказались в области уже выполненных построений.
П
L*
Рис. 10
2 x*1+3 x*2=19,
2 x*1+ x*2=13.
Отсюда имеем: х*1=5, х*2=3. Значения остальных переменных вычисляются однозначно из канонической модели после подстановки в ее уравнения х*1 и х*2. В результате получаем оптимальное решение задачи: х*1 =5, х*2 =3, х*3 =х*4 =0, х*5 =3, х*6 =2 и , следовательно, L*= 50.
Таким образом, чтобы добиться максимальной прибыли в 50 единиц, необходимо производить 5 изделий первого типа и 3 изделия второго типа. При этом будут полностью использованы ресусы 1-го и 2 -го вида (х*3=х*4=0), а по ресурсам 3-го и 4-го вида образуются остатки в количестве 3 и 2 соответственно (х*5=3, х*6=2). Задача имеет единственное оптимальное решение, так как линия уровня L= 50 соприкасается с допустимым множеством только в одной точке.▲
Очевидно, что при данном допустимом множестве задача всегда будет иметь решение независимо от коэффициентов целевой функции, потому что в любом случае будет существовать предельное положение линии уровня критерия. Однако оптимальное решение может быть и не единственным.
Пусть в нашем примере при тех же ограничениях изменились коэффициенты критерия:
L1=4x1+6x2→max.
Так как условия не изменились, то допустимое множество остается прежним. Если повторить построение линий уровня, то они будут параллельны стороне BC (коэффициеты при перемен-ных в критерии и 1-м ограничении пропорциональ-ны). Поэтому в предельном положении линия уровня критерия совпадает с границей по 1-му ограничению (рис. 4.3). В таком случае получим множество (бесконечное) оптимальных решений, лежащее на стороне BC, каждому из которых соответствует одно и то же максимальное значение критерия L1.
П риведенные построения подтверждают высказанное ранее утверждение о том, что на ограниченном допустимом множестве (выпуклом многограннике) задача всегда разрешима.
Теперь выясним, что будет, если допустимое множество неограниченно. Не конкретезируя модель, рассмотрим поведение двух целевых функций на одном неограниченном множестве (рис. 4.4). Направление улучшения критериев показано стрелками. Здесь мы видим разное поведение критериев, приводящее к различным результатам.
а) Значение критерия L1 улучшается в направлении неограничености множества и, следовательно, критерий неограничен на допустимом множестве, то есть он может улучшаться до бесконечности – допустимые решения есть, а оптимального нет.
б) Улучшение критерия L2 ограничено на допустмом множестве, следовательно, решение существует (в этом примере оно единственное, но, очевидно, возможны и множественные решения на неограниченном множестве).
Р ассмотрим другой случай (рис. 4.5). Пересечение допустимых множеств, порождаемых тремя функциональными ограничениями задачи и условиями неотрица-тельности переменных, оказывается пустым. Следовательно, допустимых решений нет и задача неразрешима.
Результаты геометрического анализа задачи ЛП в двумерном простанстве легко обобщаются на многомерное пространство. Вместо прямых границами множеств будут гиперплоскости, а непустым допустимым множством задачи – выпуклый многогранник или выпуклое многогранное множество. Для нахождения решения мысленно перемещаем гиперплоскость уровня критерия в направлении его улучшения пока имеютя общие точки с допустимым множеством. Если достигается предельное положение, то задача разрешима. При этом гиперплоскость может касаться только одной вершины множества – задача имеет единственное решение,ребра или грани допустимого множества – существует множество решений соответственно на ребре или грани, которые полностью определяются своими крайними точками (вершинами). При отсутствии предельного положения критерий неограниченно улучшается и задача неразрешима.
Таким образом, если задача ЛП разрешима, то оптимальное решение обязательно достигается в вершине допустимого множества. Поэтому оптимальное решение следует искать не на всей границе, а только в вершинах допустимого множества.