Исследование Операций - ответы на экзамен. Задача лп не имеет решения в том случае, если множество допустимых решений не является выпуклым или же если в разрешающем столбце симплексной таблицы нет положительных элементов

Название	Задача лп не имеет решения в том случае, если множество допустимых решений не является выпуклым или же если в разрешающем столбце симплексной таблицы нет положительных элементов
Анкор	Исследование Операций - ответы на экзамен
Дата	18.01.2022
Размер	18 Kb.
Формат файла
Имя файла	IO.docx
Тип	Задача #335193

Ы
Имеются некоторые переменные X=(x1, x2, x3 …) и линейная функция этих переменных, называемая целевой функцией. Также имеются ограничения, вектор свободных членов.
1. Допустимое решение – это одно из множеств решений, которое удовлетворяет системе ограничений задачи и условиям не отрицательности.
2. Оптимальное решение – это частный случай допустимого решения, при котором целевая функция имеет экстремальное значение.
3. ОДР – это множество всех допустимых решений.
4. Выпуклое множество – это множество, которое удовлетворяет данному условию: если внутри множества поставить 2 точки и провести между ними прямую, то данная прямая не будет выходить за пределы множества.
Задача ЛП не имеет решения в том случае, если множество допустимых решений не является выпуклым или же если в разрешающем столбце симплексной таблицы нет положительных элементов.
Оптимальное решение в ОДР достигается в точке экстремума. Причём точка экстремума находится на одной из вершин многоугольника ОДР.
1. Угловая точка – это вершина некоторой n-мерной фигуры, которая является множеством ОДР.
2. Базис - это n векторов, которые являются столбцами матрицы коэффициентов системы при базисных переменных. То есть базис – это векторы условий при базисных переменных.
3. Симплекс — геометрическая фигура, являющаяся n-мерным обобщением треугольника / ОДР
4. Линейно-независимый вектор: вектора a1, ..., an называются линейно независимыми, если не существует нетривиальной комбинации этих векторов равной нулевому вектору
Дополнительная переменная вводится в том случае, если в системе ограничений задачи имеются неравенства.
Теорема о числе базисных переменных. При решении задачи линейного программирования в канонической форме, в любом опорном плане имеется r базисных переменных. Отсюда следует, что в опорном плане как минимум n переменных равны нулю. Здесь n – число переменных; r – ранг матрицы системы ограничений, из которой определяются значения базисных переменны.
1. МПУ – вектор X оптимальный в том случае, если в двойственной задаче он является допустимым решением.
2. Симплекс-метод – если в нулевой строке отсутствуют отрицательные компоненты, то текущее решение является оптимальным.
Если в условии задачи даны произвольные переменные, то при составлении двойственной задачи – ограничения, соотвествующие этим переменным образуют равенство, в то время, как все остальные образуют неравенство https://youtu.be/0Ru5YsHVbv8?t=2364
gk берутся больше нуля, так как в противном случае не будет достигнута оптимальность, так как целевая функция не будет ограничена сверху.
Эпсилон - это минимум из отношений xk к gk, где k - это положительные коэффиценты.

С помощью эпсилон можно определить номер вектора, который необходимо удалить.

1. Антагонистической игрой называется некооперативная игра, в которой участвуют два или более игроков, выигрыши которых противоположны.
2. Общее значение выигрыша одного игрока и проигрыша другого в седловой точке игры, иными словами — значение выигрыша, соответствующего решению игры.
3. Чистая стратегия – определенная реакция игрока на возможные варианты поведения других игроков.
4. Смешанная стратегия – вероятностная (не определенная точно) реакция игрока на поведение других игроков.
5. Седловая точка: если верхняя и нижняя цена игры (максимина и минимакса) одинаковая, то считается, что матричная игра имеет седловую точку
Если игра не имеет седловой точки, то применение чистой стратегии не даёт оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередую чистые стратегии.
Рациональной стратегией первого игрока называется та, в которой он получит максимальный из минимальных возможных выигрышей. (max min aij)

Рациональной стратегией второго игрока называется та, в которой он получит минимальный из максимальных возможным проигрышей. (min max aij)

Берём оптимальные стратегии игроков p(p1, p2 … pn) и q (q1, q2 … qm) и цена игры V. Составляем систему из среднего выигрыша первого игрока по формуле Фон-Нейману, должна получиться система неравенств, каждое из которого больше или равно V. Далее делим обе части неравенств на V и заменяем дроби (pi (вероятности) / V) на xi. Целевая функция будет иметь вид: f(x) = x1 + x2 + … + xm -> min.
Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения, то задача называется закрытой. Иначе открытой.
Необходимо сделать одну незанятую клетку – занятой, сдвинув одну из занятых клеток и итеративно проходить по прямоугольнику из клеток в нахождении оптимального решения.

https://youtu.be/m82gOU7UlEo?t=4024

1. Проект – некоторое множество взаимосвязанных работ, которые должны быть выполнены за минимальный промежуток времени.
2. Критический путь - это самый продолжительный путь сетевого графика от начального до конечного события.
3. Резерв времени – это разница между наибольшим временем работы над проектом и наименьшим.
4. Критическое событие – это событие, резерв времени которого равен нулю.
5. Сетевой график – это графы, в роли которых выступают некоторые события, а в роли дуг – время, которое необходимо на выполнение данных событий, которые отражают некоторый процесс работы над чем-либо.
6. Напряженная дуга – это дуга, работы которой не имеют резерва времени и она должна уложиться в тот срок, который дан в исходной постановке задачи.
Решаем, чтобы сократить количество переборы при выборе способов раскроя