|
Математическое программирование
Здесь (1) называется
системой ограничений , ее матрица имеет ранг r ) системы (1) называется допустимым решением (планом)
ЗЛП. Допустимое решение называется оптимальным, если оно обращает целевую
функцию (2) в min или max (оптимум). Симплексная форма ЗЛП. Для решения ЗЛП
симплекс - методом необходимо ее привести к определенной (симплексной)
форме: s Здесь считаем r < n (система имеет бесчисленное множество решений),
случай r = n неинтересен: в этом случае система имеет единственное решение и
если оно допустимое, то автоматически становится оптимальным. называются
базисными (каждое из них входит в одно и только одно уравнение с коэффициентом
+1), остальные х - свободными. Допустимое
решение (1`) называется базисным (опорным планом), если все свободные
неизвестные равны 0, а соответствующее ему значение целевой функции
f(x В силу важности особенностей симплексной формы выразим их
и словами: все свободные члены неотрицательны, т.е. b б) целевая
функция (2`) удовлетворяет условиям : обязательна минимизация (случай max сводится к min по формуле
max f = - min(-f)). Заметим, что каждому базису (системе
базисных неизвестных ) соответствует своя симплекс - матрица , базисное решение
х = (b 2 Критерий
оптимальности плана . , то соответствующий
этой матрице план оптимален, 1 Если в симплекс-матрице имеется столбец (S-й), в
котором последний элемент с > 0,
a Если в симплекс-матрице не выполняются оба
критерия, то в поисках оптимума надо переходить к следующей матрице с помощью
некоторого элемента a + все остальные элементы матрицы преобразуем по правилу
прямоугольника, что схематично показано на фрагменте матрицы и дано в
формулах: a is a . Элемент
a называется разрешающим, если преобразование матрицы с
его помощью обеспечивает уменьшение (невозрастание) значения, целевой
функции; Критерий выбора разрешающего
элемента. is0
- номер выбранного
разрешающего столбца, то он является разрешающим. систему ограничений и целевую функцию ЗЛП приводим к
симплексной форме; проверка матрицы на выполнение критерия
оптимальности; при
невыполнении критерия оптимальности проверяем выполнение критерия отсутствия
оптимальности; в случае невыполнения обоих критериев находим разрешающий
элемент для перехода к следующей матрице, для чего : б)
выбираем разрешающую строку по критерию выбора разрешающего элемента; c помощью разрешающего элемента
и симплекс-преобразований переходим к следующей матрице; Через
конечное число шагов,как правило получаем оптимальный план ЗЛП или его
отсутствие Если в разрешающей строке (столбце) имеется
нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения
при симплекс-преобразованиях. если при этом окажется, что выполняется
критерий оптимальности, то можно ограничиться вычислением элементов последнего
столбца. появление отрицательного члена
сигнализирует о допущенной ошибке в предыдущих
вычислениях. правильность полученного ответа - оптимального плана -
проверяется путем подстановки значений базисных неизвестных в целевую
функцию; 5. Геометрическая
интерпретация ЗЛП и графический метод решения (при двух неизвестных) Система ограничений ЗЛП геометрически представляет собой
многоугольник или многоугольную область как пересечение полуплоскостей -
геометрических образов неравенств системы. Целевая функция f =
c геометрически изображает
семейство параллельных прямых, перпендикулярных вектору n
(с При перемещении прямой целевой функции направлении
вектора n значения целевой функции возрастают, в противоположном направлении -
убывают. графического метода решения ЗЛП. В
системе координат построить прямые по уравнениям, соответствующим каждому
неравенству системы ограничений; найти многоугольник
(многоугольную область) решений системы ограничений как пересечение
полуплоскостей; ) по коэффициентам целевой функции f =
c в семействе
параллельных прямых целевой функции выделить одну, например, через начало
координат; перемещать прямую целевой функции параллельно самой себе
по области решения, достигая max f при движении вектора n и min f при движении в
противоположном направлении. Приведем экономическую формулировку транспортной задачи по
критерию стоимости: соответственно в
количествах а единиц, требуется
доставить в каждый из n пунктов назначения (потребления) В n известна для всех маршрутов
A (i=1,m; j=1,n). Требуется
составить такой план перевозок, при котором весь груз из пунктов отправления
вывозиться и запросы всех пунктов потребления удовлетворяются (закрытая модель),
а суммарные транспортные расходы минимальны. в
B Математическая модель транспортной задачи. Из предыдущей
таблицы легко усматривается и составляется математическая модель транспортной
задачи для закрытой модели Число r
= m + n - 1, равное рангу системы (1), называется рангом транспортной задачи.
Если число заполненных клеток (X 0) в таблице равно
r, то план называется невырожденным, а если это число меньше r, то план
вырожденный - в этом случае в некоторые клетки вписывается столько нулей
(условно заполненные клетки), чтобы общее число заполненных клеток было равно
r. c потребностью
b c запасом
a ; при этом
тарифы фиктивных участников принимаются равными 0. (диагональный).
Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя
клетка (северо-западная) оставшейся части таблицы, причем максимально возможным
числом: либо полностью вывозиться груз из А . Процедура продолжается до тех пор,
пока на каком-то шаге не исчерпаются запасы a . В заключение проверяют, что найденные компоненты
плана X Сущность способа в том, что на каждом шаге заполняется та клетка
оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия
нескольких таких равных тарифов заполняется любая из них. В остальном действуют
аналогично предыдущему способу. потенциалами решения называются числа
i Соотношения (*) определяют систему из m+n-1 линейных
уравнений с m+n неизвестными, имеющую бесчисленное множество решений; для ее
определенности одному неизвестному придают любое число (обычно
Если известны потенциалы решения
X + Если план не оптимален, то необходимо перейти к следующему плану (таблице)
так, чтобы транспортные расходы не увеличились. любые
две соседние клетки находятся в одной строке или в одном
столбце; Пустой клетке присваивают знак " + ", остальным -
поочередно знаки " - " и " + ". Для перераспределения плана перевозок с
помощью цикла перерасчета сначала находят незаполненную клетку (r, s), в которой
, и строят
соответствующий цикл; затем в минусовых клетках находят число
X=min{X в плюсовые клетки добавляем X; ); оно снова
проверяется на оптимальность через конечное число шагов обязательно найдем
оптимальный план транспортной задачи, ибо он всегда
существует. проверяем тип модели транспортной задачи и в случае
открытой модели сводим ее к закрытой; находим опорный план перевозок
путем составления 1-й таблицы одним из способов - северо-западного угла или
наименьшего тарифа; проверяем план (таблицу) на удовлетворение
системе уравнений и на не вырожденность; в случае вырождения плана добавляем
условно заполненные клетки с помощью " 0 "; а) составляем систему уравнений потенциалов
по заполненным клеткам; в) находим
суммы г) сравниваем косвенные
тарифы с истинными: если косвенные тарифы не превосходят соответствующих
истинных(C ) во всех пустых
клетках, то план оптимален (критерий оптимальности). Решение закончено: ответ
дается в виде плана перевозок последней таблицы и значения min f. Для перехода к следующей таблице (плану): = б) составляем цикл пересчета для этой клетки и
расставляем знаки " + ", " - " в вершинах цикла путем их чередования, приписывая
пустой клетке " + "; - числа в заполненных клетках со
знаком " - "; См. п. 3 и
т.д. Через конечное число шагов (циклов) обязательно приходим к
ответу, ибо транспортная задача всегда имеет решение.
| |
