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

Вопрос 18

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

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 – Проверять построчно равенство суммы и преобр. суммы.

Вопрос 19

МП – Задача о кротчайших расстояниях (постановка алгоритма)

1 – фиксируем точку Pi, до которой необходимо рассчитать кротчайшее расстояние от всех остальных, и в кружке, обозначающем эту точку, записываем 0, т.к. расстояние от точки Pi до нее самой равно 0. Это число, которое для других точек отлично от 0 называем характеристикой точки. 2 – Определяем соседние точки по отношению к фиксированной точке. В кружках обозначающих эти точки записываем их характеристики. Cij = 0 + Lij, и на связях ставим стрелки направленные в сторону точки Pi. 3 – отмечаем Pi символом V, обозначающим, что операция над ней закончена. 4 – переходим к соседней с Pi точке, для которой характеристика уже найдена. Пусть эта точка Pj. Определяем соседние с ней точки и рассчитываем для них характеристики как сумму Cij + Lij ’ = Cij ’. 5 – В точку Pj ’ отмечаем знаком V и переходим к номеру 4. 6 – При определении Cij ‘ для соседних точек с Pj ‘ может оказаться, что для некоторых из них Cij уже рассмотрено. В этом случае Cij ‘ сравниваем с Cij, Если Cij ‘ >= Cij для всех таких точек, то Cij остается без изменений; Точку Pj ’ отмечаем знаком V и переходим к номеру 4. Если для некоторой точки Cij ‘ > Cij то Cij заменяем на Cij ‘, cсоответственно изменяем связь, через которую проходит кротчайшее расстояние. Точку Pj ‘ отмечаем знаком V. Только в том случае, если точка, у которой изменилась характеристика, не была ранее отмечена. 7 – если изменилась характеристика отмеченной точки, то пересчитываем характеристику точек, соседних с ней, а затем отмечаем точку Pj ‘ и переходим к номеру 4. 8 – Процесс продолжается до тех пор пока не будут отмечены все точки. После этого выписываем кротчайшее расстояние и маршруты, по которым они проходят. На этом первый этап заканчивается. 9 – Переходим к следующему этапу начиная с пункта 1 алгоритма, и расчеты продолжаем до тех пор, пока не будут определены кротчайшие расстояние от всех точек до каждой из них.