Экономико-математические методы и модели в логистики

ВВЕДЕНИЕ

Курсовая работа состоит  в выполнении двух задач.

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

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

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

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

ЗАДАЧА 1

УСЛОВИЕ ЗАДАЧИ (Вариант 6)

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

Табл. 1. Цены перевозок

Поставщики  готовы отгружать следующее количество сырья:

Табл. 2. Запасы продукции

Недельные потребности  заводов составляют:

Табл. 3. Заказы клиентов

Составить план снабжения  заводов на неделю, исходя из минимума издержек.

Задания:

1. Составление транспортной таблицы.
2. Построение математической модели задачи.
3. Выполнение расчета модели, используя для получения допустимого решения метод северо-западного угла или наименьшей стоимости, а для получения оптимального решения метод потенциалов.

4.   Выполнение расчета модели в Excel, используя надстройку Поиск решения. Проверка ручного расчета модели и расчета модели, выполненном в Excel.

5.    Нахождение разницы между наилучшим и наихудшим планом перевозок.

Затем необходимо ответить на вопросы, подтверждая ответы расчетами, выполненными с помощью надстройки Поиск решения:

а) Возможны ли альтернативные решения?

б) После составления плана перевозок выяснилось, что, возможно, Поставщик 2 сможет отгружать на 8 машин сырья больше, чем планировал. Каким будет тогда план перевозок?

с) Выяснилось, что Поставщик 2 не сможет отгружать продукции больше, чем планировал, к тому же Поставщик 3 сможет поставлять на 6 машин сырья меньше, чем собирался. Каким будет тогда план перевозок? Какой завод недополучит продукцию?

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

 На основании исходных  таблиц составим транспортную таблицу (табл.4).

Табл. 4

Для наглядности и простоты вычислений «вручную», стоимости перевозок, представленные в залитых цветом клетках таблицы, уменьшим в 100 раз, таким образом, они будут иметь  единицу измерения, равную 100 у.е. (табл. 4-а).

Табл. 4-а

Пусть x_ij- количество продукции, отправляемой от поставщика i к клиенту j, i=, j=, а c_ij – стоимость перевозки единицы груза (x_ij≥0, c_ij≥0),

Тогда общая стоимость  перевозки равна

Z=*    (1)

             В силу ограничений на возможность поставок продукции со склада и спрос на него клиентов должны выполняться следующие условия (ограничения) (2):

• на количество продукции, которое нужно вывести с каждого склада:

x₁₁+ x₁₂+ x₁₃+ x₁₄=65

x₂₁+ x₂₂+ x₂₃+ x₂₄=60

x₃₁+ x₃₂+ x₃₃+ x₃₄=70

• на количество продукции, которое надо доставить клиентам (заводам):

x₁₁+ x₂₁+ x₃₁=50

x₁₂+ x₂₂+ x₃₂=40

x₁₃+ x₂₃+ x₃₃=45

x₁₄+ x₂₄+ x₃₄=60

Суммарное количество продукции  на складах:

Cуммарное количество продукции, заказанное клиентами (заводами):

Так как имеет место  равенство:

Транспортная задача является закрытой (с балансом). 

Решим задачу методом наименьшего  элемента:

Задача формулируется  следующим образом: определить такие  неотрицательные значения переменных , i=1,m, j=1,n, которые удовлетворяют ограничениям (2) и обращают в минимум целевую функцию (1).

РЕШЕНИЕ ЗАДАЧИ

Решение транспортной задачи состоит из двух этапов:

1. Определение допустимого решения (базисного решения).
2. Определение оптимального решения путем последовательного улучшения допустимого решения методом потенциалов.

Определение допустимого  решения методом наименьшей стоимости

На основе транспортной таблицы (табл. 4) построим вспомогательную таблицу (табл. 5), в верхнем правом углу каждой клетки которой будем записывать стоимости перевозки. Введем в таблицу  вспомогательную строку и столбец для записи остатков.

Определим клетку таблицы (табл. 5), которой соответствует наименьшая стоимость перевозки. Такая клетка одна: =6, поэтому, выбрав её, запишем:=min()=min(70,40)=40

Рассуждаем так: в S₃ имеется 70 единиц товара, в К₃ требуется 40. Организуем перевозку из S₃ в К₂, т.е. запишем в клетку значение х₃₂ = 40 (табл. 6). В S₃ осталось 70-40 = 30 ед. товара, спрос К₂ полностью удовлетворен. Остатки по строке и столбцу запишем в соответствующие клетки столбца и строки остатков: в S3 - 30, а в К₂ — О.Так как в столбце К₂ остаток равен нулю, этот столбец закрывается и далее не рассматривается (табл. 6).

Табл. 5

Табл. 6

В табл. 6 ищем клетку, в которой  записана наименьшая стоимость перевозки (за исключением клеток закрытого столбца К₂). Это клетка С₃₃. В нее запишем значение Х₃₃ = min (30, 45) = 30. Определим остатки для строки S₃ и столбца К₃. Остаток по строке S₃ равен 30-30 = 0, остаток по столбцу К₃ 45-30 = 15

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

Табл. 7

Среди оставшихся клеток, не принадлежащих закрытой строке или  закрытому столбцу (см. табл. 7), наименьшую стоимость перевозки имеет клетка С₁₄. Запишем в нее значение Х₁₄ = min (65,60) = 40. Остаток для строки S₁ =65-60=5, а для столбца К₄ = 60-60 = 0. Запишем их в соответствующие клетки. Четвертый столбец становится закрытым (табл. 8).

Табл. 8

Из оставшихся незакрытых клеток (табл. 8) С₁₃=10- клетка с наименьшей стоимостью перевозки, следовательно, в клетку соответствующую С₁₃ записывается значение х₁₃ = min (15,5) = 5. В клетки S₁ и К₃ записываются остатки: остаток в первой строке - (5-5 = 0), в третьем столбце - (15-5=10). Первая строчка становится закрытой (табл. 9).

Табл. 9

Незакрытыми остаются первая строка и вторая с двумя столбцами (см. табл. 9). Остаются ячейки ячейка С₂₁=11 и С₂₃=13. В клетки, соответствующие С₂₁ и С₂₃, записываются значения х₂₁ = min (60,50) = 50 и х₂₃ = min (10,10) = 10 соответственно. В клетки с остатками S₂ , К₁  и К₃ записываются остатки: остаток во второй строке - (60-50-10 = 0), в первом  столбце - (50-50 = 0), в третьем столбце - (30-5-10 = 0). (Первый столбец, третий столбец и вторая строка закрываются) (табл. 10).

Табл. 10

Все строки и столбцы становятся закрытыми, следовательно, исходный базисный план найден. Этому плану соответствует  стоимость перевозки:

Z= 5*10 + 60*9 + 50*11 + 10*13 + 40*6 + 30*8 = 1750.

Последовательное  улучшение допустимого решения  методом потенциалов

Выберем вспомогательные  коэффициенты U_i и V_j (i=, j=), обращающие в нули коэффициенты при базисных переменных, то есть

С_ij- U_i- V_j=0

Такие переменные называются потенциалами. Введем в табл. 10 для  записи потенциалов вспомогательную строку и столбец (табл. 11).

Метод потенциалов заключается  в выполнении следующих шагов:

1. Для всех Ху > 0 (т.е. всех занятых клеток) составляются потенциальные уравнения по формуле (16). Для определения т + п потенциалов необходимо, чтобы было т + п - 1 уравнений (где т - число строк, п - число столбцов). Тогда одному из потенциалов можно присвоить значение, равное нулю, а значения других потенциалов получить, решая систему уравнений (17). Для данной задачи т + п -1 = 6, и число занятых клеток равно 6 (см. табл. 10). Следовательно, решение невырожденное.

Табл.11

Составим потенциальные  уравнения для заполненных клеток (3):

           2. Решим систему уравнений (3), присвоив значение, равное нулю, наиболее часто встречающемуся  неизвестному потенциалу: U₁ = 0, тогда

U₁  = 0

V₁ = 8

U₂  = 3

V₂ = 8

U₃ = -2  

V₃ = 10 

V₄ = 9

Данные потенциалы занесем  в столбцы Ui и Vj  табл. 12.

Табл. 12

3. Для всех небазисных переменных, т.е. для  = 0 (для пустых клеток), определим невязки:

G_ij = C_ij - S_ij, где S_ij = U_i + V_j

(C_ij - стоимость перевозки единицы товара, S_ij— косвенная стоимость). Получим (4)

Так как имеются отрицательные  невязки: G₂₂= -3 и G₂₄= -2,5, найденный план не оптимален.

4. Найдем новое базисное решение (табл. 13).

Табл. 13

Для этого введем переменную Хij (назначим перевозку) в ту клетку табл. 13, которой соответствует отрицательная невязка, например, в клетку (2,2). Отметим ее знаком (+) (см. табл. 15). Знак (+) означает, что в эту клетку следует ввести перевозку. Вводя новую переменную (перевозку), в какую-нибудь клетку, необходимо изменить значения других переменных по меньшей мере в трех заполненных клетках, чтобы не нарушились итоговые значения в строках Si и столбцах Kj. Для этого построим четырехугольник (или многоугольник) вершинами которого будут отмеченные знаками клетки, причем отрезки, соединяющие их, должны располагаться по вертикали или горизонтали. Например, если в клетку (2,2) поставили (+), то в клетку (2,3) надо поставить (-), в клетку (3,3) - (+), в клетку (3,2) - (-). В пустые клетки знак (-) ставить нельзя. В свободную клетку должно быть перенесено меньшее из чисел, (обозначающих перевозку), стоящих в клетках со знаком (-). Значения перевозок в остальных, отмеченных знаками клетках, должны быть изменены на это же число: если в клетке стоит знак (+) - увеличены, если стоит знак (-) - уменьшены.

В табл. 13 числа, находящиеся  в клетках со знаком (-), равны = 10 и = 40 , min (10,40) = 10, поэтому во всех клетках, помеченных знаком (+), значения перевозок увеличим на 10, а во всех клетках, помеченных знаком (-) - уменьшим на 10. В результате = 0 и исключается из базиса,  = 25 и оно остается в базиса. Получим план перевозок, представленный в табл. 14, для которого значение целевой функции равно:

Z =10*5 + 9*60 + 11*50 + 8*10 + 6*30 + 8*40 = 1720тыс. у.е.

Табл.14

Перейдем к повторению выполнения действий, описанных в  пунктах 1- 4.

1. Для всех x_ij >0 (т.е. для всех занятых клеток) составим потенциальные уравнения. Как уже говорилось, должно быть т + п -1 = 6. (табл. 15).

Табл. 15

Получим потенциальные уравнения (5):