Решение транспортной задачи в Excel - Курсовая работа

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.Пусть имеется несколько поставщиков однородной продукции (каждый с определенным запасом) и несколько потребителей этой продукции (с известными потребностями у каждого). Таким образом, требуется составить план перевозок продукции от поставщиков к потребителям так, чтобы потребности потребителей были бы удовлетворены за счет вывоза запаса от поставщиков. Транспортные задачи бывают: 1) открытые m ? n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.) 2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.) Открытую ТЗ сводят к закрытой ТЗ путем прибавления к суммарному запасу продукции или суммарной потребности продукции недостающих единиц до равенства суммарного запаса продукции и суммарной потребности продукции.Итак, алгоритм метода потенциалов для решения ТЗ состоит из следующих шагов: ШАГ 1. Опишем алгоритм по шагам, иллюстрируя каждый шаг Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид: Клетка (i , j ) таблицы соответствует коммуникации, связывающей i-го поставщика cj-м потребителем. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). В случае одновременного исчерпания запасов потребностей (ai =bj = 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти).Иногда возникает ситуация, когда в условиях (ТЗ) необходимо минимизировать не стоимость перевозок, а время их выполнения (Срочные грузы, перевозки скоропортящихся продуктов, работа «скорой помощи» и т.д.) Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. · В ячейки B8:F9 - матрицу транспортных расходов, задающую расходы на перевозку из I-го склада в J-й магазин единицы продукции. · В ячейки B13:F14 - план перевозок - матрицу, задающую количество товара, перевезенного из I-го склада в J-й магазин. · В ячейки D17:H17 записал ограничения, задающие требование о точном выполнении заявки каждого магазина.

Содержание

Введение

§1. Постановка Транспортной задачи (ТЗ) для n переменных

§2. Пример решения Транспортной задачи

§3. Транспортные задачи по различным критериям

§4. Решение транспортной задачи в Excel

Список литературы

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.

Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.

В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.