Общая математическая формулировка открытой транспортной задачи, её опорное решение. Вербальная постановка транспортной задачи и её решение распределительным методом. Интерпретация результатов проученных расчетов и выработка управленческого мероприятия.
Аннотация к работе
КУРСОВАЯ РАБОТА на тему: «Решение открытой транспортной задачи»Нам приходится в жизни считать, мы постоянно используем знания о величинах, характеризующих протяженности, площади, объемы, промежутки времени, скорости и многое другое. Все это пришло к нам на уроках арифметики и геометрии и пригодилось для ориентации в окружающем мире. Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, что связаны с естественными науками, техникой и экономикой. Математика является языком естествознания и техники и потому профессия естествоиспытателя и инженера требует серьезного овладения многими профессиональными сведениями, основанными на математике. Одной из задач линейного программирования является транспортная задача-задача составления оптимального плана перевозок, позволяющего минимизировать суммарный километраж.Задача о размещении (транспортная задача) - это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Транспортная задача делится на два вида: - транспортная задача по критерию стоимости - определение плана перевозок, при котором стоимость груза была бы минимальна; Особенности экономико-математической модели транспортной задачи: - система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме); Транспортная задача, в которой суммарные запасы и потребности совпадают, т. е. выполняется условие , называется закрытой моделью; в противном случае - открытой.Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости, и исключается из рассмотрения только одна строка(поставщик) или один столбец (потребитель).Если допустимое решение (i=1,2,…,m; j=1,2,…n ) транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков (i=1,2,…,m )и потребителей (j=1,2,…,n). Алгоритм решения транспортных задач методом потенциалов: а) проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок. b) построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания). c) построить систему потенциалов, соответствующих опорному решению. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным. e) перейти к опорному решению, на котором значение целевой функции будет меньше.На складах трех поставщиков А1, А2, А3 хранится 300, 250 и 200 единиц одного и того же груза. Этот груз требуется доставить четырем потребителям B1, В2, B3 и B4, заказы которых составляют 220, 150, 250 и 180 единиц груза соответственно. Стоимости перевозок ij c единицы груза с i-го склада j-му потребителю указаны в правых верхних углах соответствующих клеток транспортной таблицы, приведенной ниже. Составить такой план перевозок груза, при котором общая стоимость всех перевозок была бы минимальной. Направляем груз в клетку (3,2) и получаем следующую таблицу.От поставщика А1 будем доставлять потребителю В1 220 единиц груза, а потребителю В3 80 единиц груза. От поставщика А2 будем направлять потребителю В2 80 единиц груза, а потребителю В3 170 единиц груза. От поставщика А3 будем направлять потребителю В2 70 единиц груза и фиктивному потребителю 130 единиц груза. Отчет по результатам включает исходные и конечные значения целевой функции и изменяемых ячеек, а также формул ограничений и дополнительных сведений о наложенных ограничениях (см.рис.5 и рис.6).
План
Содержание
Введение
Глава 1. Теоретические основы транспортной задачи: 1.1 Общая математическая формулировка открытой транспортной задачи
1.2 Методы решения транспортной задачи
1.2.1 Опорное решение транспортной задачи
1.2.2 Метод потенциалов
Глава 2. Построение и решение транспортной задачи: 2.1 Вербальная постановка транспортной задачи
2.2 Решение поставленной задачи распределительным методом «вручную»
2.3 Решение поставленной задачи с помощью средств EXCEL
2.4 Интерпретация результатов расчетов и выработка управленческого решения