МП – Общие принципы построения математической модели, страница 2

МП – Элементы теории игр.

Можно свести к симплекс-методу. Решает конфликтные ситуации, когда участники имеют противоположные интересы. Различают: парные игры, игры с нулевой суммой, не парные

Алгоритм симплекс метода.

I – составить математическую модель и привести ее к симплексной модели. Ввод дополнительных неизвестных. II – Составить симплексную таблицу: количество строк по количеству уравнений, количество столбцов по количеству неизвестных. 1 – коэффициенты при неизвестных в целевой функции. 2 – Номера неизвестных. 3 – номера неизвестных вошедших в базис. В исходной таблице – номера дополнительных неизвестных. 4 – коэффициенты при неизвестных не целевой функции из первой строки, вошедшие в базис. 5 – А₀ - итоговый столбец в исходной таблице – свободные члены из системы ограничений. 6 – Основание матрицы – коэффициент при неизвестных в системе ограничений. 7 – Значения целевой функции на каждой итерации – сумма произведений Сb на А₀. 8 – целевая строка – показатель оптимальности решения, вычисляется как сумма произведений первого столбца и i-ого. Когда все числа в целевой строке положительные, при решении на max – задача оптимальна, и наоборот – на min. 9 – сумма элементов по строке. 10 – альфа – дополнительный столбец для нахождения ключевой строки.  Так как в целевой строке все числа отрицательные, при решении на max, следовательно план не оптимален, и его необходимо улучшить, для этого к следующей итерации: 1 – в целевой строке берем наименьший элемент и этот столбец делаем ключевым. 2 – делим элементы итогового столбца А₀ на ключевой (получаем альфа). Выбираем среди альфа min положительный элемент и эту строку делаем ключевой, а элемент на пересечении – ключевым элементом. 3 – Ключевая строка получается делением всех элементов на ключевой элемент. 4 – все остальные преобразуются по следующему правилу: новое значение = старое значение – (проекция на ключевую строку * проекция на ключевой столбец) / ключевой элемент.  ПРОВЕРКИ: 1 – значение целевой функции должно увеличиваться или оставаться неизменным при решении на max и, наоборот – на min. 2 – А₀ не может быть отрицательным. 3 – Проверять построчно равенство суммы и преобр. суммы.

Вопрос 9

МП - Построение опорного плана транспортной задачи (Метод двойного предпочтения)

В каждом столбце выбираем min Cij и смотрим, является ли он min и в строке. Если да, заносим туда поставку и в зависимости от распределенной мощности или удовлетворения спроса вычеркиваем или строку или столбец, после чего переходим к следующему столбцу.

Вопрос 10

МП – Графический метод расчета параметров СПУ.

1 – Событие делится на 4 сектора: 1.1 – номер текущего события. 1.2 –  номер предыдущего события. 1.3 – раннее выполнение данной работы для ост. Tpj = Tpi + Tij где Tij – продолжительность данной работы – причем если к данному событию подходит несколько работ, то выбирается max. 1.4 – заполняется с конца, для завершающего события Tn3 = Tn3 для остальных Tni = Tnj – Tij. Причем если от события отходит несколько работ, то выбирается min значение. 2 – Определяем резервы времени событий как разность между 4-ым и 3-им секторами, Rc = Tni –Tpi. Резерв времени событий – такое время, на которое мы можем отодвинуть совершение данного события. События, у которых резервы времени  = нулю – лежат на критическом пути.

Вопрос 11

МП – Метод потенциалов

Для проверки допустимого плана на оптимальность особым образом определяем числа (потенциалы), с их помощью определяем характеристику клеток без кружков. Когда все характеристики будут положительны – план оптимален, в противном случае делаем перераспределение поставок путем итераций и доводим план до оптимального. Алгоритм: 1 – Определяем потенциалы: Cij = Ui + Vj