 |
Решение задач о кратчайших расстояниях.
|
|
|
|
Практическая работа №2
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Графический метод основан на геометрической интерпретации задач линейного программирования и применяется, в основном, при решении задач двухмерного пространства и иногда - трехмерного.
Алгоритм решения:
Областью решения является общее значение всех полуплоскостей. Для нахождения оптимального решения строим вектор с координатами значений целевой функции. Проводим вектор и перпендикулярно ему двигаемся, пока последняя точка области решения не коснется этого перпендикуляра.
Практическая работа №3
РЕШЕНИЕ МАТЕМАТИЧЕСКИХ ЗАДАЧ СИМПЛЕКСНЫМ МЕТОДОМ.
Постановка задачи:
Есть 3 вида станков А1, А2, А3. На этих станках последовательно обрабатываются детали 4-х видов В1, В2, В3, В4. Все данные известны. Требуется найти оптимальный план работы станков. Сколько деталей и каких видов нужно выпустить чтобы получить максимальную прибыль.
Алгоритм:
1. Приводим неравенства к равенствам введением дополнительных неизвестных. Переписываем уравнения со всеми неизвестными. (Такая система называется симплексной, т.е. задачу приводим к стандартной симплексной модели).
2. Составляем симплекс таблицу по следующим правилам:
· Коэффициенты при неизвестных из целевой функции,
· Номера неизвестных,
· Коэффициенты при неизвестных в системе ограничений,
· Номера неизвестных входящих в текущий план, первоначальные номера дополнительных неизвестных,
· Коэффициенты целевой функции входящие в текущий план,
· Значение целевой функции входящие в текущий план (сумма произведений первого и третьего столбца),
· Целевая строка (вычитается сумма произведений первого столбца на i, минус первая строка),
|
|
|
· Сумма всех элементов (от третьего столбца до последнего неизвестного),
· Дополнительный столбец α (делением третьего столбца на ключевой столбец).
3. Задача считается решенной, когда в целевой строке все значения положительные (на максимум), все значения отрицательные (на минимум). Если план не оптимален, то его необходимо улучшить путем итерации. Для этого составляем еще одну таблицу.
4.
 |
В целевой строке выбираем минимальное значение (при решении на максимум) и, наоборот (на минимум) и этот столбец называем ключевым. Делим итоговый столбец на ключевой, выбираем минимальное значение (не отрицательное и не равное нулю), и эту строку делаем ключевой. Элемент на пересечении ключевого столбца и ключевой строки – ключевым элементом.
Новое значение каждого элемента, кроме ключевой строки, преобразуется по следующему правилу:
Ключевая строка преобразуется делением всех элементов на ключевой элемент.
Решение на каждом этапе 1-й, 2-й, 3-й столбец.
Проверка:
· Сумма по строкам равняется преобразованной сумме,
· Итоговый столбец (3-й) не может быть отрицательным, если он все же получается отрицательным, значит неправильно выбрана ключевая строка,
· Функция от итерации к итерации монотонно возрастает или остается без изменений и, наоборот, на минимум.
Практическая работа №4
РЕШЕНИЕ МАТЕМАТИЧЕСКИХ ЗАДАЧ СИМПЛЕКСНЫМ МЕТОДОМ С ИСКУССТВЕННЫМ БАЗИСОМ.
Приводим неравенства к равенствам, введением дополнительных неизвестных (со знаком «–»).
Так как в базисное решение входят элементы положительной единичной матрицы, вводим искусственные переменные (положительные, отсчет от последней отрицательной), а в целевую функцию дополнительные неизвестные всегда с нулем, а искусственные с М, где М неограниченно большое число при решении на минимум и, наоборот, на максимум.
|
|
|
Составляем симплексную таблицу. В опорный план всегда входят коэффициенты единичной матрицы. Далее решаем по алгоритму симплекс метода.
Практическая работа №5
РЕШЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ.
Каждой задаче линейного программирования соответствует ей двойственная или сопряженная задача, которая преобразуется следующим образом: если прямая на максимум, то двойственная на минимум. Коэффициенты целевой функции прямой являются свободными членами двойственной и наоборот. Знаки меняются на противоположные. Матрица транспонируется.
Количество неизвестных прямой это количество неравенств сопряженной и наоборот. Численно Fmin и Fmax равны.
Практическая работа №6
ПОСТРОЕНИЕ ОПОРНЫХ ПЛАНОВ 6-ю МЕТОДАМИ.
1. Способ северо-западного угла.
Если Ai > Bj, то заносим поставку и далее идем по столбцу, в противном случае по стоке. С левого верхнего угла идо правого нижнего.
2. Минимальный элемент в строке.
Берём min Cij в стоке и заносим туда поставку. Если Aij распределена, то переходим к следующей стоке, в противном случае ищем новое.
3. Минимальный элемент в столбце.
Ищем минимальный элемент в столбце Cij и заносим поставку, если спрос удовлетворен, то к следующему столбцу иначе дальше пока не распределен.
4. Наименьший элемент в матрице.
Ищем min Cij по всей матрице и заносим поставку, и в зависимости от распределения мощности или спроса из дальнейшего рассмотрения выбрасываем или строку или столбец.
5. Двойное предпочтение.
Берем i столбец, ищем min Cij и смотрим, является ли Cij одновременно min в строке, если да, то заносим поставку, вычеркивая или строку или столбец, если нет, то следующий столбец.
6. Метод Фогеля.
В каждой строке и в каждом столбце вычитываем разность между min Cij =/ друг другу. Вычитываем их за таблицу. Среди этих разностей выбираем max и по этой строке (столбцу) ищем min Cij и заносим туда поставку.
После построения опорного плана и выбрав план с наименьшим функционалом, проверяем его на оптимальность.
Практическая работа №7
ПРОВЕРКА ОПОРНОГО ПЛАНА НА ОПТИМАЛЬНОСТЬ МЕТОДОМ ПОТЕНЦИАЛОВ.
Для этого:
1. Определяем потенциалы строк и столбцов для загруженных клеток по следующему правилу
|
|
|
Cij = Uij + Vj
Ui = Cij – Vj
Vj = Cij – Ui
Первый любой потенциал берется произвольно.
2. Определяем характеристику незагруженных клеток по формуле
Eij = Cij – (Ui + Vj)
(Eij для загруженных клеток = 0 по построению)
Если все характеристики положительны, то план оптимален и задача решена. В противном случае план надо улучшить, т.е. перейти к следующей итерации. Для этого выбираем клетку с наименьшим значением Eij и к этой клетке будем строить цепь перераспределения поставок по следующему правилу:
· Каждый отрезок цепи принадлежит только или строке или столбцу
· Все углы прямые
· Одна вершина не загруженная, все остальные загруженные
· Отрезки могут проходить, как загруженные, так и незагруженные клетки
· Конфигурация цепи произвольная, но количество вершин всегда четное
· Начиная с незагруженной вершины по часовой стрелке, помечаем вершины знаком «+» и «-»
· Берем минимальное значение в отрицательной вершине и на это значение увеличиваем положительные и уменьшаем отрицательные.
· Чертим новую таблицу, заносим перераспределенные поставки и определяем заново потенциалы.
· Количество загруженных клеток не должно превышать (m+n)-1, где m и n количество строк и столбцов.
Практическая работа №8
ПРОВЕРКА ОПТИМАЛЬНОГО ПЛАНА МЕТОДОМ ДИФФЕРЕНЦИАЛЬНЫХ РЕНТ.
Алгоритм:
1. В каждом столбце матрицы ищется min Cij и обводится кружком. Затем, начиная с первого столбца в клетке с кружками, заносятся подставки максимально возможные. Ели при распределении в клетке с кружком не осталось ни мощности, ни спроса, то заносят 0-ю поставку.
2. По окончанию распределения проверяется, исчерпана ли мощность и удовлетворен ли спрос. Если да, то задача решена. Если нет, то устанавливаем небалансы и знаки строк. Если вся мощность распределена, а спрос неудовлетворен в кружках связанных с этой строкой, то строка считается отрицательной, поставщик недостаточным. В последнем столбце ставятся знак «–» и количество недостающего спроса. Если спрос удовлетворен, а мощность по этой строке осталась, то поставщик избыточный, а строка положительная. Суммарный неудовлетворенный спрос = суммарной нераспределенной мощности и называется нераспределенным остатком.
|
|
|
3. В каждом столбце определена разность между min Cij в положительной строке и Cij в кружке и пишем в последнюю строку. Берем минимальную разность и называем ее промежуточной рентой.
4. Чертим новую таблицу, в которой Cij в положительных строках записываем без изменения, а к отрицательным Cij прибавляем промежуточную ренту.
5. В положительной строке ищем Cij = кружку и обводим ее.
Далее:
- на каждой итерации добавляем 1 и только 1 кружок за исключением, если в столбце имеются 2 кружка на равных друг другу, то кружок из предыдущей итерации убирается.
- небалансы от итерации к итерации монотонно убывают до 0. Нулевой небаланс говорит о том, что план допустимый и задача решена.
- при нулевом небалансе строки, ноль будет положительным, если строка связана с положительной строкой и отрицательным если с отрицательной.
Практическая работа №9
РЕШЕНИЕ ЗАДАЧ О КРАТЧАЙШИХ РАССТОЯНИЯХ.
Алгоритм:
1. Фиксируем точку Pi, до которой необходимо рассчитать кратчайшее расстояние от всех остальных. Записываем около нее 0, как расстояние до самой себя и назовем это характеристикой точки.
2. Определяем характеристики соседних точек по формуле Cij = 0 + Lij и на связях ставим стрелки по направлению к фиксированной.
3. Отмечаем точку Pi галочкой (√), т.е. операции над ней закончены.
4. Переходим к любой следующей, для которой характеристика определена, предположим, что это Pj′ и определяем характеристики соседних с ней точках по формуле Cij = Cij'+Lij'.
5. Точку Pj отмечаем галочкой и переходим к 4-му пункту алгоритма.
6. При определении характеристик для соседних точек может оказаться, что для них характеристики уже рассчитаны, тогда их сравниваем. Выбираем меньшую, соответственно изменяем связь, через которую проходит кратчайшее расстояние, и если от нее были зависимы соседние точки, то тогда пересчитываем их характеристики. После этого переходим к 4-му пункту.
7. Процесс продолжается до тех пор, пока не будут отмечены все точки, и строим маршрут для кратчайших расстояний всех точек.
8. Переходим к следующему этапу, начиная с первого этапа, пока не будут определены кратчайшие расстояния для всех точек.
Практическая работа №10
СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ.
Правила построения сетевого графика.
При выполнении каждой следующей работы она может начинаться только после выполнения всех предшествующих работ. Если предшествующие работы не влияют на последующие, то лучше их выделить в отдельное звено. Две работы не могут иметь одинаковые коды, т.е. быть параллельными.
|
|
|
Ошибки в сетевых графиках и их исправление.
1. В каждом сетевом графике может быть только одно исходное и одно завершающее событие, не имеющее предшествующих работ. Исправление: или добавить забытую связь (работу), или убирается с графика, как нелогичная связь.
2. На каждом графике может быть только одно завершающее событие. Исправление: см. пункт 1.
3. В сети не должно быть замкнутых контуров. Исправление: вернуть связь в обратную сторону.
4. Нужно стараться, как можно меньше иметь пересечений, т.к. это затемняет чертеж.
5. Параллельные работы исправляются введением дополнительного события и фиктивной работы.
6. Каждое событие нумеруется, поэтому, каждая работа имеет код ij, причем, i обязательно меньше j (i<j).
Для этого существует алгоритм (для проверки нумерации) метода вычеркивания дуг. Алгоритм:
Берется исходное событие, ему присваивается ранг 0; затем из этого события вычеркиваются все исходящие из него работы. В результате одно или несколько событий окажутся без входных работ, ому присваивается следующий ранг. Операция повторяется до завершающего события.
После установки нумерации по рангам, нумеруем внутри ранга, начиная с исходного события внутри ранга произвольно.
Практическая работа №11
|
|
|
