Транспортная задача

Размещено на http://www.allbest.ru/

Содержание

1. Составление опорного плана методом северо-западного угла

2. Решение транспортной задачи средствами Microsoft Exel

3. Решение транспортной задачи с помощью Mathcad

Список используемых источников

1. Составление опорного плана методом северо-западного угла

Заполнение таблицы 1 начинаем с левого верхнего угла.

Сумма поставок по строке равна запасу соответствующего пункта отправления, а сумма поставок по столбцу - заявке соответствующего пункта назначения; значит, все заявки удовлетворены, все запасы исчерпаны (сумма запасов равна сумме заявок и выражается числом 1220, стоящим в правом нижнем углу таблицы).

Таблица 1 - Решение транспортной задачи методом потенциалов

Во всех транспортных таблицах проставляем только отличные от нуля поставки, а клетки, соответствующие нулевым поставкам, оставляем пустыми.

Далее, проверяем, является ли план, приведенный в таблице 1, опорным. Так как число занятых клеток с нулевыми поставками составляет m + n - 1 = 5 + 5 - 1 = 9, то план - опорный.

Получившийся план поставок отвечает одному из условий - вся мощность поставщиков полностью распределена, весь спрос потребителей полностью удовлетворен.

Стоимость транспортных работ L составляет:

4*200 + 2*150 + 1*70 + 4*200 + 1*200 + 9*10 + 7*190 + 3*10 + 7*190 = 4950 тыс. руб.

Далее решаем транспортную задачу методом потенциалов, который основан на выборе некоторого исходного варианта прикрепления поставщиков к потребителям и последующем его преобразовании вплоть до получения оптимального варианта.

транспортный поставка microsoft mathcad

Таблица 2 - Решение транспортной задачи методом потенциалов (шаг 1)

При распределении поставок составляем цепи, для которых характерны следующие особенности:

цепь является замкнутым многоугольником;

вершинами цепи являются клетки таблицы, причем одна из вершин - свободная клетка, а все остальные - базисные;

все углы цепи прямые, и каждый отрезок цепи, ограниченный двумя вершинами, целиком принадлежит одному столбцу или одной строке таблицы;

число вершин в цепи - четное;

отрезки цепи могут проходить через базисные клетки, не являющиеся вершинами данной цепи.

Вершины, в которых поставка при распределении увеличивается, отмечаем знаком «+» и называем положительными, а вершины, в которых поставка уменьшается, отмечаем знаком « - » и называем отрицательными.

Суть метода потенциалов заключается в том, что для проверки допустимого плана на оптимальность определяют числа, называемые потенциалами, при помощи которых вычисляют характеристики свободных клеток цепи. Единственное требование к потенциалам: каждый показатель критерия оптимальности базисной клетки должен быть равен алгебраической сумме потенциалов своих строки и столбца.

Обозначив потенциалы строк , потенциалы столбцов - и показатели критерия оптимальности - .

Характеристики свободных клеток цепи обозначим, тогда, зная потенциалы строки и столбца, ее можно вычислить по формуле:

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

Для всех базисных клеток характеристики равны нулю.

Характеристики свободных клеток укажем в нижней части клеток поставок.

Наибольшая по абсолютной величине - отрицательная характеристика клетки . Перераспределим поставки по цепи к этой клетке. Составим цепь с вершинами, отмеченными в таблице 2 стрелками. Положительные вершины в этой цепи обозначены знаком «плюс», отрицательные - знаком «минус». Наименьшая по величине поставка в отрицательных вершинах цепи равна 10 тыс. к поставкам в положительных вершинах и вычтем по 10 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 3 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 3- Решение транспортной задачи методом потенциалов (шаг 2)

Значение целевой функции при новом плане поставок будет равен L=4800 тыс. руб.

Наибольшая по абсолютной величине - отрицательная характеристика клетки . Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 3 стрелками. Положительные вершины в этой цепи обозначены знаком «плюс», отрицательные - знаком «минус». Наименьшая по величине поставка в отрицательных вершинах цепи равна 180 тыс. к поставкам в положительных вершинах и вычтем по 180 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 4 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 4 - Решение транспортной задачи методом потенциалов (шаг 3)

Значение целевой функции при новом плане поставок будет равен: L=2820 тыс. руб

Наибольшая по абсолютной величине - отрицательная характеристика клетки . Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 4 стрелками. Положительные вершины в этой цепи обозначены знаком «плюс», отрицательные - знаком «минус». Наибольшая по величине поставка в отрицательных вершинах цепи равна 10 тыс. к поставкам в положительных вершинах и вычтем по 10 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 5 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 5 - Решение транспортной задачи методом потенциалов (шаг 4)

Значение целевой функции при новом плане поставок будет равен: L=2780 тыс. руб.

Наибольшая по абсолютной величине - отрицательная характеристика клетки . Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 4 стрелками. Положительные вершины в этой цепи обозначены знаком «плюс», отрицательные - знаком «минус». Наибольшая по величине поставка в отрицательных вершинах цепи равна 200 тыс. к поставкам в положительных вершинах и вычтем по 200 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 6 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 6 - Решение транспортной задачи методом потенциалов (шаг 5)

Значение целевой функции при новом плане поставок будет равен: L=2180тыс. руб.

Наибольшая по абсолютной величине - отрицательная характеристика клетки . Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 4 стрелками. Положительные вершины в этой цепи обозначены знаком «плюс», отрицательные - знаком «минус». Наибольшая по величине поставка в отрицательных вершинах цепи равна 140 тыс. к поставкам в положительных вершинах и вычтем по 140 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 7 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 7 - Решение транспортной задачи методом потенциалов (шаг 6)

Значение целевой функции при новом плане поставок будет равен: L=2040 тыс. руб.

В приведенном плане поставок нет ни одной отрицательной характеристики. Отсутствие отрицательных характеристик свидетельствует о том, что нельзя построить цепи, перемещение поставок по которым уменьшило бы значение целевой функции.

Следовательно, найденный план распределение поставок - оптимальный.

2. Решение транспортной задачи средствами Microsoft Exel

Многие задачи экономико-математического моделирования являются оптимизационными, т. е. в них требуется найти максимальное (минимальное или равное определенному числу) значений некоторой функции, называемой целевой. Реальные задачи имеют много условий, поэтому поиск оптимального решения требует большого объема вычислений. Использование ЭВМ позволяет производить сложные расчеты за короткий срок.

Составим план перевозок с минимальными затратами используя программу Microsoft Excel.

1) Составим на рабочем листе Excel две таблицы. В таблице «Тарифы» записываются исходные числовые данные, в таблицы «План перевозок» продублированы столбец «запасы» и строка «Потребность» для удобства работы с таблицей добавлены столбец «Использовано» и строка «Удовлетворено» (рисунок 1).

Рисунок 1 - Заполнение таблицы «Тарифы»

2) Заполним формулами, необходимыми для создания ограничений на запасы, ячейки G12:G16 столбца «Использовано». В ячейку G12 вводим формулу суммы (=СУММ(B12:F12)). Аналогичные операции производим для каждого поставщика (рисунок 2 и 3).

Рисунок 2 - Заполнение формулой ячейки «Использовано» для поставщика А1

Рисунок 3 - Заполнение формулами столбца «Использовано»

3) Заполним формулами, необходимыми для создания ограничений на потребности, ячейки B17:E17 строки «Удовлетворено». В ячейку B17 вводим формулу суммы (=СУММ(B12:B16)). Аналогичные образом производим заполнение последующих столбцов (рисунок 4).

Рисунок 4 - Заполнение формулой ячейки «Удовлетворено» для первого потребителя

4) Запишем общие суммы по столбцам и строкам: в ячейку H17 - по столбцу «Запасы» (=СУММ(H12:H16)) (рисунок 5); в ячейку G17 - по строке «Использовано» (=СУММ(G12:G16)) (рисунок 6); в ячейку G18 - по строке «Потребность» (=СУММ(B18:F18)) (рисунок 7).

Рисунок 5 - Общая сумма по столбцу «Запасы»

Рисунок 6 - Общая сумма по столбцу «Использовано»

Рисунок 7 - Общая сумма по строке «Потребность»

5) Запишем формулу для целевой функции, для этого выделим ячейку G19, на значке fx на панели инструментов, в категории «Математические» выбираем функцию «СУММПРОИЗВ». В появившемся диалоговом окне выбираем «массив1», проводим указателем мыши по диапазону ячеек B3:F7, затем выбрав «массив2» выделим диапазон ячеек B12:F16. В строке формулы появится функция с выбранными ссылками на ячейке. В самой ячейке G19 пока запишется нулевое значение. Полученная формула дает сумму из 25 попарных произведений указанных ячеек двух таблиц, которая и является для нас целевой функцией (рисунок 8).

Рисунок 8 - Заполнение формулой ячейки «Целевая функция»

6) Укажем необходимые ссылки на ячейки и ограничения для целевой функции, для этого выполним команду «Сервис», «Поиск решения». В появившемся диалоговом окне в поле «Установить целевую» функцию ссылаемся на ячейку G19. Установим в поле «Равной» значение, соответствующее по «минимальному значению». В поле «Изменяя ячейки» указываем диапазон ячеек $B$12:$F$16.

В поле «Ограничения» создаем список всех ограничений для нашей задачи, представленный в таблице19.

Таблица 19 - Список ограничений

После ввода параметров щелчок на кнопке «Выполнить» запускает поиск оптимального решения. Появляется диалоговое окно «Результаты поиска решения» с сообщением об успехе поиска.

В изменяемые ячейки B12:F16 записываются значения оптимального плана перевозок, ячейку G19 - значение целевой функции, а в ячейки столбца «Использовано» и строки «Удовлетворено» записываются значения, равные значениям соответствующих ячеек столбца «Запасы» и строки «Потребность».

Результаты выполненных расчетов представлены в таблицах 20 и 21.

Таблица 20 - Тарифы транспортной задачи

Таблица 21 - Оптимальный план перевозок

3. Решение транспортной задачи с помощью Mathcad

Задаем начальное значение х

Задаем количество пунктов отправления и пунктов потребления :

Неизвестные параметры транспортной задачи обозначим: (i=1,2,..,k, j=1,2,..,n) -- объемы перевозок от каждого i-го поставщика каждому j-му потребителю:

На основе данного пункта можем задать матрицу стоимости перевозок , а также матрицы запасов отправителя и потребителя продукции: a и b соответственно:

Т.к. произведение определяет затраты на перевозку груза от i - го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны

По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция (функция, связывающая цель с управляемыми переменными в задаче оптимизации) имеет вид:

х - матрица перевозок

Список используемых источников

1. Коровкин Р.Л. Транспорт леса: Методические указания к выполнению контрольных работ. - Архангельск: Изд-во АГТУ, 2003. - 37 с.

2. Электронный ресурс - http://www.moluch.ru/archive/64/10247/

3. Электронный ресурс - http://edu.dvgups.ru/METDOC/EKMEN/ETR/EK_MATM_M/METOD/U_P_PR/WEBUMK/frame/2.htm

Размещено на Allbest.ru