1)что такое достижимое множество и численный пример достижимого множества

Множество точек Y = {y=(f₁(x),…, f_N(x))/Ax=b, x≥0} называется достижимым множеством канонической ЗЛП (F(x)→max; Ax=b; x≥0), где каждому плану x D можно поставить в соответствие значение векторной функции y=F(x)=(f₁(x),…, f_N(x)), y R_N

2)Определение целочисленной задачи и пример задачи с неделимостями

Экстремальная задача линейного программирования, в которой на решение налагается целочисленность компонент, является задачей целочисленного программирования и называется целочисленной задачей.

Классический пример задачи о неделимостях – задача о ранце.

Имеется n предметов, объёмом V_i i=1,m

C_i – ценность i-го предмета

V – объем рюкзака V>V_i , т.е. все предметы имеют объём, превосходящий объём рюкзака.

Требуется загрузить рюкзак предметами с максимальной ценностью

3)Структурные ограничения транспортной задачи и их экономический смысл

- условие того, что весь груз от i-го поставщика вывезен потребителям

- Условие полного удовлетворения потребностей j-го пункта потребителей за счёт поставок i-тых поставщиков

4)Что такое доминирующая стратегия, и какие действия выполняет с ней лпр

Стратегия (альтернатива) А_i называется доминирующей (превосходящей), если не существеут другой альтернативы A_k

(k=1,m k≠i) со значением a_kj≥a_ij ( ) и a_kj>a_ij

Если в матрице игры имеется доминирующая альтернатива, она и выбирается в качестве решения.

5)Основные действия в сетевом планировании, типа алгоритма (основные этапы сетевого планирования)

1. Определяется полный перечень работ, которые необходимо выполнить для осуществления проекта

2. Определяются взаимосвязи и порядок выполнения работ, т.е. строится сетевая модель проекта или топология сети

3. Устанавливается длительность выполнения работ и потребляемое кол-во ресурсов. Ресурсы определяются дифференцировано

Если неизвестна длительность выполнения работ, то можно:

Предположить, что для каждой работы есть 3 оценки продолжительности её выполнения:

• Наиболее вероятное время выполнения m

• Оптимистическая оценка времени a

• Пессимистичная оценка времени b

Наиболее вероятное время определяется как время выполнения работ при нормальных условиях.

Ожидаемая средняя продолжительность работы:

r = 1/6(a+4m+b)

Дисперсия продолжительности работ:

Ожидаемая (средняя) продолжительность проекта = сумме всех средних продолжительностей работ, находящихся на критическом пути, а дисперсия продолжительности проекта = сумме дисперсий продолжительности работ, находящихся на критическом пути

4. Расчёт временных параметров сетевого графика

5. Анализ полученных результатов. Оценивается величина критического пути и других показателей, важных для ЛПР. Если результат положительный, переходим к пункту 7, иначе, к пункту 6

6. Пересмотр сетевой модели: перераспределение ресурсов, изменение длительностей работ и т.п. Получается обновлённая сетевая модель, переходим к пункту 4

7. Наложение временных характеристик на календарь, с учётом выходных дней. Формирования планов конкретным исполнителям и управление проектом в процессе выполнения работ, свершении или не свершении событий. Особое внимание уделяется работам, лежащим на критическом пути.

6)задача, надо было решить матричную игру

1.Теорема оптимальности бдп (признак оптимальности бдп транспортной задачи в сетевой постановке)

Для того, чтобы БДП был оптимальным, необходимо и достаточно, чтобы существовали такие числа u_j v_i, для которых выполнялись бы условия:

1. 

2. 

2. что-то про венгерский метод

Пусть нули редуцированной матрицы не находятся в общем положении. Опишите следующий шаг венгерского метода.

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

Суть венгерского метода:

Если из элементов исходной матрицы затрат С вычитать некоторые константы строк и столбцов, то полученные новые элементы преобразованной матрицы не приводят и к изменению оптимального плана.

3. рисунок дерева вариантов

4. формулы Т раннее окончание работы и Т позднее допустимое начало (поздние допустимые сроки)

Ранние сроки:

Поздние допустимые сроки:

1. напишите с помощью БДП транспортную задачу с 3 поставщиками и 4 потребителями

2. дана функция и по ней нарисовать достижимое множество

3. эк смысл потенциалов в транспортной задаче

Потенциал v_i –стоимость единицы груза у поставщика, u_j – стоимость единицы груза в j-ом пункте потребления

• , т.е. сумма груза у потребителя j равна сумме его стоимости в пункте отправления i и затрат на перевозку

• , если стоимость у потребителя не превосходит сумму , то не имеетсмысла перевозить груз от поставщика i к потребителю j. В этом случае перевозка невыполнима, следовательно, = 0