Транспортная задача линейного программирования, ее сущность и основные задачи. Порядок постановки и математическая модель. Процесс нахождения первоначального распределения. Метод северо-западного угла и аппроксимации Фогеля. Тестирование программы.
Аннотация к работе
Они обусловлены удаленностью источников сырья от пунктов производства, пунктов производства от пунктов потребления и другими объективными факторами. Затраты на перевозки всех видов грузов всеми видами транспорта в целом по стране составляют более 20 млрд. руб. Столь большой объем затрат дает основание полагать, что при правильном решении вопросов, связанных с использованием транспорта, особенно учитывая, с одной стороны, разнообразие его видов, богатство природных условии, сложность схем перевозок, дальность расстояний, а с другой - дефицитность транспортных средств и их загруженность, можно ожидать существенного сокращения этих затрат. Такое предположение подтверждается и значительным уже опытом применения математических методов планирования на транспорте. Один из основных показателей работы транспорта - грузооборот - измеряется в тонно-километрах.Речь будет идти о рациональной перевозке некоторого однородного (одного и того же назначения и качества) продукта от производителей к потребителям. В этом случае каждому потребителю безразлично, откуда, из каких пунктов производства будет поступать этот продукт, лишь бы он поступал в нужном объеме. В связи с этим, естественно, возникает вопрос о наиболее рациональном прикреплении производителей к потребителям (и наоборот), о правильном направлении перевозок груза, при котором потребности удовлетворяются, а затраты на транспортировку минимальны. Будем предполагать, что производство и потребление сбалансированы - сумма объемов производства равна сумме объемов потребления, т. е. Используя терминологию и особенности транспортной задачи, этот критерий можно сформулировать таким образом: допустимый план перевозок тогда и только тогда является оптимальным, когда каждому пункту производства и потребления можно сопоставить величину, характеризующую уровень оценки продукции в нем так, что множество этих потенциалов удовлетворяет следующим условиям: (1) разность оценок пунктов потребления и производства, между которыми запланированы перевозки, равна затратам по транспортировке единицы продукта между этими пунктами;Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аі(0) = аі, bj(0) = bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: xij=min{ ai(q), bj(q).)}.В методе северо-западного угла на каждом шаге потребности первого из оставшихся пунктов назначения удовлетворялись за счет запасов первого из оставшихся пунктов назначения. Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на планы перевозок, а именно: на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбрать любую из них), и рассмотреть пункты отправления и назначения, соответствующие выбранной клетке. Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом. Следует отметить, что этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем стоимость перевозок при плане, найденном для данной задачи с помощью метода северо-западного угла. Просматриваются тарифы транспортной таблицы, и в первую очередь заполняется клетка с минимальным значением тарифа.При определении оптимального плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.В предыдущих случаях мы рассматривали только такую задачу о перевозках, в которой сумма запасов ровна сумме заявок: (где i=1,...,m; j=1,...,n) (4) Сумма запасов в пунктах отправления превышает сумму поданных заявок (где i=1,...,m ; j=1,...
План
Содержание
Введение
1. Транспортная задача: постановка и математическая модель