2015-01-21
373
Шаг 1.Составляют транспортную таблицу.
Шаг 2.Выбирают клетку таблицы, которой соответствует минимальное значение тарифа, и переходят на шаг 3.
Шаг 3.В выбранную клетку помещают максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос. После этого, если предложение производителя исчерпано, вычеркивают соответствующую строку; если спрос удовлетворен, вычеркивают соответствующий столбец.
Если все клетки заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учета заполненных и вычеркнутых клеток.
Построение цепи (цикла) перемещения по правилам:
• Цепочку можно строить по горизонтали или вертикали, по ходу часовой стрелки или против хода часовой стрелки.
• Цепочка должна закончиться в клетке с оценкой dij*.
• Цепочка перемещений строится из свободной клетки с оценкой dij* до одной из занятых клеток, где делается поворот на 90 градусов. После этого снова осуществляется перемещение до занятой клетки и делается поворот на 90 градусов и так далее. Нужно вернуться в клетку, из которой начали перемещение, за наименьшее число поворотов (наиболее короткий путь).
|
|
|
Экономический смысл: приращение оценки единицы продукта при его перевозке по коммуникации AjBj не должно превышать транспортные расходы)
63. Симплексный М-метод линейного программирования. Симплекс-таблица. Правило прямоугольника.
М-метод заключается в применении правил симплекс- метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной ЗЛП таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М — достаточно большое положительное число.
При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные xn+1, xn+2,..., xn+m.
Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b1, b2,..., bm. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении (
). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты aij при переменных системы ограничений.
