Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Матричная форма задачиТаблица 3.1
При решении задач симплексным или распределительным методом вначале составляют вариант распределения, удовлетворяющий всем ограни чениям, но не оптимальный. Затем его поэтапно улучшают до оптимального. Пример решения транспортной задачи распределительным методом. Распределительный метод, основан на принципе принятия начального варианта плана с последующим его улучшением вплоть до получения оптимальной программы. При решении транспортной задачи распределительным методом следует составить матрицу, и дальнейший процесс вычислений проводится в следующей последовательности: 1. Предварительно распределяются ресурсы, перевозки и др. При этом наиболее приемлемо «правило северо-западного угла», согласно которому максимально допустимое количество ставится верхнюю левую клетку модели. Затем заполняются следующие клетки (вправо и вниз), заполняются и другие клетки до окончательного распределения всего груза. При этом количество заполненных клеток должно составить т+п — 1, где п — количество потребителей, т — количество поставщиков. Если для клетки нет числовых значений, то в нее проставляется нуль. Этот план называется вырожденным. 2. Для каждой свободной клетки составляется многоугольник с вершинами, лежащими в загруженных клетках. В вершинах многоугольника проставляются критерии оптимальности (расстояние, затраты и пр.) с чередующимися знаками, начиная с положительного для свободной клетки. Алгебраическая сумма этих показателей выражает потенциальную возможность данной клетки, а отрицательный итог— гарантию улучшения плана. Таким образом, в итоге второго этапа устанавливается, может ли быть улучшен исходный вариант и в каком направлении следует вести его улучшение. 3. После определения наиболее перспективной из свободных клеток переходят к новому варианту плана. Для этого грузы перемещают в пределах клеток, связанных многоугольником с данной свободной клеткой. 4. Вновь полученный вариант плана проверяют на оптимальность. Для этого снова составляют многоугольники и вычисляют характеристики для каждой свободной клетки. Если среди характеристик есть отрицательные, то необходимо дальнейшее улучшение плана. Если характеристики положительны, значит план оптимален. Для начального распределения поставок, помимо «правила северо-западного угла», применяют и другие, например: минимум матрицы, метод аппроксимации, минимум по строке, минимум по столбцу. Последние являются разновидностями метода минимума Пример конкретной постановки и решения транспортной задачи линейного программирования распределительным методом применительно к строительству мостов. Стоимость возведения моста можно снизить при организации оптимальной схемы перевозок железобетонных мостовых конструкций, т. е. при рациональном прикреплении заводов и полигонов железобетонных мостовых конструкций к объектам строительства мостов. Допустим, что имеются три завода железобетонных конструкций – поставщики и три участка строящихся мостов — потребители. Известны: мощность каждого завода и потребность конструкции для каждого моста. Считаем, что всего с заводов ежедневно отправляется 200 т конструкций, в частности, первый поставщик отсылает 100, второй — 50, третий — 50 т. На строительство первого моста должно быть доставлено 75, второго — 60, третьего — 65 т конструкций. Кроме того, определены затраты на производство 1 м3 железобетона на каждом заводе. Необходимо закрепить поставщиков за потребителями таким образом, чтобы спрос каждого потребителя полностью удовлетворялся, а общие затраты на производство и транспортировку были минимальными. Таким образом, критерием оптимальности искомого решения является минимум затрат на изготовление и перевозку сборных мостовых железобетонных конструкций. Составляется исходная матрица (таблица 1). Математически данная задача формулируется следующим образом. Требуется минимизировать общий пробег груза, т/км. 5Х11 + 4Х12 + Х13 +2Х21+6X22 +ЗX23 + 10X31 + 7Х32 + 2X33 ® min Ограничения в данной задаче обусловлены тем, что каждый поставщик отправляет потребителям определенное количество груза. Например, поставщик А может отправить груз трем потребителям, но общее его количество должно составлять 100 т. Математически это условие может быть выражено уравнением: Х11 + Х12 +Х13 =100. Для поставщиков Б и В имеем уравнения: Х21 + Х22 +Х23 =50 Х31 + Х32 +Х33 =50 К первому потребителю может поступать также груз от трех различных поставщиков, но только с общим количеством 75 т. Следовательно, должно выполняться условие: Х11 + Х21 +Х31 =75 Соответственно для второго и третьего потребителей имеем уравнения: Х12 + Х22 +Х32 =60 Х13 + Х23 +Х33 =65 Шесть приведенных уравнений выражают ограничивающее условие данной транспортной задачи. Для составления исходного плана перевозок пользуемся «правилом северо-западного угла». Запишем матрицу задачи с заполнением верхней левой клетки (табл. 2). В первой клетке указывают количество груза, перевозимого от поставщика А к потребителю 1. В ней может находиться только число 75 (т), удовлетворяющее полностью потребителя 1. Но поставщик А имеет 100 т груза, т. е. 25 т он может передать потребителю 2. Значит, во второй клетке может находиться не более 25 т. Заполнив две клетки, мы использовали полностью возможности поставщика А. При этом потребителю 2 доставлено 25 т груза при потребности 60 т. Недостающие 35 т могут быть доставлены от поставщика Б. внесем в клетку на пересечении строки Б и столбца 2 недостающий груз 35 т, а оставшиеся у поставщика Б 15 т — в соседнюю клетку второй строки. Таким образом, возможности поставщика 2 исчерпаны. В клетку на пересечении строки В столбца 3 внесем цифру 50. Составление первоначальной программы перевозок закончено. Этот вариант не является оптимальным, но он удовлетворяет всем ограничениям задачи.
Таблица 2
В клетках таблицы расположены девять неизвестных величин задачи хij, которые обозначают объем перевозок от i-го поставщика j-му потребителю. В тех же клетках в первом верхнем углу показано расстояние перевозки между пунктами, км. По этому варианту общий пробег груза составит 5 км·75 т+4 км·25 т+ +6 км ·35 т+3 км ·15 т+2 км·50 т= =830 т· км. На втором этапе расчетов определяют оптимальность плана. С целью уменьшения суммарного пробега груза улучшают первоначальную программу. В исходном варианте заполнены пять клеток (m+n—1=3+3-1==5), а четыре не заполнены. Оптимизация плана заключается в использовании незанятых клеток. Требуется проверить целесообразность включения каждой свободной клетки в программу перевозок. Чтобы нарушить итоговые величины в строках и столбцах таблицы при заполнении одной свободной клетки одновременно нужно изменять цифры в трех соседних заполненных клетках, т. е. свободная клетка рассматривается не изолированно, а в совокупности с несколькими занятыми клетками; С этой целью для каждой клетки, в которую не внесены поставки, строятся многоугольники (цепи), определяющие связь свободной клетки с заполненными. Многоугольник строится таким образом, чтобы одна его вершина находилась в свободной, а остальные — в заполненных клетках. Каждой свободной клетке соответствует один многоугольник. Возьмем свободную клетку АЗ в первой строке. Для сохранения равновесия всей программы изменяют цифры в трех примыкающих к ней заполненных клетках. Таким образом, четыре клетки (одна незаполненная, а три заполненные) образуют своеобразный квадрат, одна из вершин которого приходится на свободную клетку, а три — на занятые.
-4 +1 - 6 +3
А3 В2
-5 +4 -5 +4 Б1 В1 -6 +3 Рис.3.2
На рис. 3.2 показано построение квадратов для первого варианта проверки оптимальности перевозок. В вершинах квадрата поставлены расстояния перевозок, внесенные в клетки, причем цифре для свободной клетки присваивается знак плюс, следующей — знак минус и т. д. Алгебраическая сумма величин, стоящих в вершинах первого прямоугольника, — 3+6- 4+1 = 0. Для незанятой клетки на пересечении строки Б и столбца 1 строится второй аналогичный квадрат, алгебраическая сумма которого +4- 5+2- 6= -5. Свободной клетке В1 соответствует более сложный многоугольник с вершинами, лежащими в шести клетках (В1, А1, А2, Б2, БЗ, ВЗ). Алгебраическая сумма величин у вершины этого многоугольника +10—5+4-6+3-2 = +4. Для четвертой свободной клетки В2 построен аналогичный квадрат с алгебраической суммой у вершины +3- 2+7- 6 = +2. Положительная сумма значений вершин квадратов говорит о том, что включение такой свободной клетки в программу увеличит общую величину пробега на полученную положительную сумму. Отрицательная сумма указывает, на сколько пробег уменьшится. Согласно алгебраическим суммам (0; —5; +4; +2), улучшать программу перевозок следует в направлении клетки с отрицательным результатом —5, т. е. наличие отрицательной алгебраической суммы в одной из клеток говорит о том, что программа не является оптимальной и ее нужно улучшать. Третий этап расчетов заключается в улучшении программы. При этом в свободную клетку, как правило, переносится меньшее из чисел, стоящих в клетках с отрицательными знаками (в нашем примере число 35 в клетке Б2). Для соблюдения равновесия всей программы нужно одновременно прибавить число 35 к числу, стоящему в другой клетке с положительным знаком, и вычесть из обеих клеток с отрицательными знаками. После этих преобразований матрица принимает такой вид (табл. 3.3).
Таблица 3.3
Суммарный пробег груза после такого распределения составит 5 км·40 т+4 км·60 т+2 км ·35 т+3 км·15 т+2 км·50 т=655 т·км, т. е. будет на 175 т·км меньше, чем при исходном варианте. Затем проверяют на оптимальность второй вариант перевозок. С этой целью аналогично предыдущему строим многоугольники для клеток АЗ; Б2; В1; В2. И т.д. до тех пор, пока распределение не будет оптимальным.
Дата добавления: 2014-08-09; просмотров: 452; Нарушение авторских прав Мы поможем в написании ваших работ! |