Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования

НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»

Кафедра информатики и компьютерных технологий

Курсовая работа по дисциплине

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

Факультет: заочный

Специальность: 080506.65

Группа: ЛГСз-09-02

Студентка 4-го курса: Молева О.А.

Проверил: Петухова Н.М. /___________/

Санкт-Петербург

2012 г.

ВВЕДЕНИЕ

В соответствии с учебным планом по дисциплине «Экономико­математические методы и модели в логистике» студенты должны выполнить кур­совую работу. Курсовая работа состоит в выполнении двух задач.

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

Вторая задача - задача выбора оптимального плана перевозки груза от од­ного поставщика к нескольким потребителям. Такого типа задачи легко решаются методами теории графов. В данном случае задача сводится к задаче определения кратчайшего пути на графе. Для ее решения предлагается использовать метод Дейкстры. После выполнения расчета модели «вручную», студентам предлагается решить задачу, используя математический пакет Maple.

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

ЗАДАЧА 1

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

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

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

	Завод 1	Завод 2	Завод 3	Завод 4
Поставщик 1	1600	1400	1100	1250
Поставщик 2	1300	1350	1500	1200
Поставщик 3	1000	1250	900	1400

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

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

	Поставщик 1	Поставщик 2	Поставщик 3
Мах отгрузка, маш./нед.	50	55	60

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

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

	Завод 1	Завод 2	Завод 3	Завод 4
Потребность, маш./нед.	50	30	45	40

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

Задания:

1. Составьте транспортную таблицу.

2. Постройте математическую модель задачи.

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

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

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

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

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

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

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

Построение математической модели

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

Табл. 4

Max отгрузка маш/нед.		Недельные потребности завода
		Завод 1	Завод 2	Завод 3	Завод 4
		50	30	45	40
		Стоимости перевозки ед груза
Поставщик 1	50	1600	1400	1100	1250
Поставщик 2	55	1300	1350	1500	1200
Поставщик 3	60	1000	1250	900	1400

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

Табл. 4-а

Max отгрузка маш/нед.			Недельные потребности завода
			Завод 1		Завод 2	Завод 3	Завод 4
			50		30	45	40
			Стоимости перевозки ед груза
Поставщик 1	50	16		14		11	12,5
Поставщик 2	55	13		13,5		15	12
Поставщик 3	60	10		12,5		9	14

Пусть Xij - количество продукции, отправляемой со склада i к клиенту j, i

= L,т , j =1,n, а Cij- стоимость перевозки единицы продукции. Отрицательные значения xij и Cij не имеют смысла, поэтому xij ≥ 0 и cij ≥ 0.

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

(1)

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

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

(2)

- на количество продукции, которую надо доставить клиентам:

(3)

Суммарное количество продукции у поставщиков: (4)

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

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

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

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

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

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

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

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

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

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

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

=min( )=min(60,45)=45

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

Табл. 5

Остатки	Ki
	Поставщики	Заводы
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
	S2 = 55	13	13,5	15	12
	S3 = 60	10	12,5	9	14

Табл. 6

Остатки	Ki			0
	Поставщик	Завод
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
	S2 = 55	13	13,5	15	12
15	S3 = 60	10	12,5	9 45	14

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

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

Табл. 7

Остатки	Ki	35		0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
	S2 = 55	13	13,5	15	12
0	S3 = 60	10 15	12,5	9 45	14

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

Табл. 8

Остатки	Ki	35		0	0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
15	S2 = 55	13	13,5	15	12 40
0	S3 = 60	10 15	12,5	9 45	14

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

Табл. 9

Остатки	Ki	20		0	0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
0	S2 = 55	13 15	13,5	15	12 40
0	S3 = 60	10 15	12,5	9 45	14

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

Табл. 10

Остатки	Ki	0	0	0	0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
0	S1= 50	16 20	14 30	11	12,5
0	S2 = 55	13 15	13,5	15	12 40
0	S3 = 60	10 15	12,5	9 45	14

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

Z= 20*16 + 30*14 + 15*13 + 40*12 + 15*10 + 45*9 = 1970.