Распределительный метод решения транспортной задачи
Прежде
всего заметим, что система ограничений
состоит из n
+
m
уравнений.
Причем при условии
эти
уравнения линейно зависимы. Действительно,
сложив все уравнения получим:
Правые части уравнений равны друг другу по условию , а левые, являющиеся суммами всевозможных переменных xij также совпадают. Вычитая из (2’) (3’) получим верное тождество 0 =0 , следовательно, уравнения системы ограничений линейно зависимы, и ранг этой системы не больше, чем n + m -1. Можно доказать, что ранг системы ограничений не меньше, чем n + m -1 Итак, ранг системы ограничений транспортной задачи при условии равен n+m -1. Следовательно, число базисных переменных в системе ограничений также равно n+ m-1, а число свободных — ( nm -n - m +1). Распределение поставок, соответствующее базисному решению будем называть базисным распределением, клетку, соответствующую базисной переменной будем считать заполненной, а соответствующую свободной переменной — свободной или пустой. Заметим, что в случае вырожденного решения клетку, соответствующую нулевой базисной переменной , также считают «заполненной». По аналогии с симплексным методом в распределительном методе, выбрав начальное базисное решение будем переходить от одного базисного распределения поставок к другому, уменьшая значение целевой функции вплоть до оптимального решения. Для начала такого процесса необходимо исходное базисное распределение поставок (базисное решение) — так называемый опорный план.
Билет 3=Билет 15.
1. Типовые классы оптимизационных задач. Выбор типа модели. Проверка и корректировка модели.
В настоящее время все этапы оптимизации принято делить на следующие классы:1) задачи управления классами 2) задачи распределения ресурсов 3) задачи ремонта и замены оборудования 4) задачи массового обслуживания 5) задачи упорядочивания 6) задачи сетевого планирования и управления 7) задачи выбора маршрутов 8) комбинированные методы
Типы моделей. Математическая модель – одно или система уравнений, отражающих количественную связь между входящими в модель параметрами. Целью составления модели является исследование взаимозависимости между ними, а также исследование управления процессами, которые описываются данными моделями. По количеству независимых параметров модели подразделяют на следующие типы:- одномерная модель отражает положение точки на числовой оси,(например, х=а );
- двумерная модель отражает положение точки на плоскости,(например, ах1 +bх2 =с);
- трехмерная модель отражает положение точки на какой-то поверхности,(например, ах1 + bх2 + сх3 =d );
- многомерная модель имеет количество независимых параметров более трех (например, ах1 + bх2 + сх3 + dх4 =е).
Очевидно, что мы можем представить в виде геометрических образов только одно- , двух- или трехмерную модели. При количестве независимых параметров более трех говорят, что такая модель описывает гиперповерхность, которая является частью гиперпространства. Проверка и корректировка моделей. В сложных системах к которым относятся системы организационного типа, модель лишь частично отражает реальный процесс, поэтому всегда требуется проверка степени соответствия адекватности модели реального процесса. Эту проверку производят методом сравнения предсказанного теоретически поведения при заданном изменении неуправляемых переменных у. Проверку и корректировку моделей можно производить по логической схеме. Корректировка модели может потребовать многошаговые процедуры. Все эти этапы повторяют до тех пор пока не будет получено допустимое отклонение между выходом объекта и модели.