Автор работы: Пользователь скрыл имя, 28 Ноября 2013 в 04:43, курсовая работа
Актуальность данной курсовой работы связана с важностью и ценностью использования методов линейного программирования для принятия управленческих решений. Применение методов линейного программирования актуально в сегодняшнее время, так как использование математических моделей является важным направлением совершенствования планирования и анализа деятельности. Представление данных в виде математической модели позволяет конкретизировать информацию, создавать и моделировать варианты, выбирать оптимальные решения.
Введение……………………………………………………………………………...3
Часть 1. Транспортная модель закрытого типа………………………………..4
1.1. Условие задачи………………………………………………….……….……...4
1.2. Построение опорных планов транспортной модели…………….……………5
1.2.1. Построение опорного плана методом северо-западного угла……….5
1.2.2. Построение опорного плана методом минимальной стоимости……8
1.2.3. Построение опорного плана методом Фогеля……………..………..12
1.3. Оптимизация транспортной модели закрытого типа…………….…….…....17
1.3.1. Метод потенциала на основе опорного плана,
построенного методом северо-западного угла …………………………17
1.3.2. Метод потенциала на основе опорного плана,
построенного методом минимальной стоимости……………………….33
1.3.3. Метод потенциала на основе опорного плана,
построенного методом Фогеля…………………………………………...41
Часть 2. Транспортная модель открытого типа…………………………...….…..44
2.1. Условие задачи………………………………………………….………..……44
2.2. Построение опорных планов транспортной модели…………….…….…….45
2.2.1. Построение опорного плана методом северо-западного угла ……..45
2.2.2. Построение опорного плана методом минимальной стоимости…..46
2.2.3. Построение опорного плана методом Фогеля ...................................47
2.3. Оптимизация транспортной модели открытого типа ………………………49
2.3.1. Метод потенциала на основе опорного плана,
построенного методом северо-западного угла…………………..49
2.3.2. Метод потенциала на основе опорного плана,
построенного методом минимальной стоимости ……………….65
2.3.3. Метод потенциала на основе опорного плана,
построенного методом Фогеля …………………………………...67
Заключение………………………………………………………………………….70
Используемая литература………………………………………………………….71
Запасы поставщика 2 составляют 230 единиц продукции.
Потребность потребителя 4 составляет 90 единиц продукции.
От поставщика 2 к потребителю 4 будем доставлять 90 единиц продукции.
Разместим в ячейку (2:4) значение равное 90.
Мы полностью удовлетворили потребность потребителя 4. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения
5)Минимальный элемент матрицы тарифов находится в ячейке (3:1) и равен 3, то есть из незадействованных маршрутов, маршрут доставки продукции от поставщика 3 к потребителю 1 наиболее рентабельный.
Запасы поставщика 3 составляют 45 единиц продукции.
Потребность потребителя 1 составляет 70 единиц продукции.
От поставщика 3 к потребителю 1 будем доставлять 45 единиц продукции.
Разместим в ячейку (3:1) значение равное 45.
Мы полностью израсходовали запасы поставщика 3. Вычеркиваем строку 3 таблицы, то есть исключаем ее из дальнейшего рассмотрения.
6)Минимальный элемент матрицы тарифов находится в ячейке (2:1) и равен 4, то есть из незадействованных маршрутов, маршрут доставки продукции от поставщика 2 к потребителю 1 наиболее рентабельный.
Запасы поставщика 2 составляют 140 единиц продукции.
Потребность потребителя 1 составляет 25 единиц продукции.
От поставщика 2 к потребителю 1 будем доставлять 25 единиц продукции.
Разместим в ячейку (2:1) значение равное 25.
Мы полностью удовлетворили потребность потребителя 1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
7)Минимальный элемент матрицы тарифов находится в ячейке (2:5) и равен 5,то есть из незадействованных маршрутов, маршрут доставки продукции от поставщика 2 к потребителю 5 наиболее рентабельный.
Запасы поставщика 2 составляют 115 единиц продукции.
Потребность потребителя 5 составляет 105 единиц продукции.
От поставщика 2 к потребителю 5 будем доставлять 105 единиц продукции.
Разместим в ячейку (2:5) значение равное 105.
Мы полностью
удовлетворили потребность
8)Минимальный элемент матрицы тарифов находится в ячейке( 2:2) и равен 8, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика 2 к потребителю 2 наиболее рентабельный.
Запасы поставщика 2 составляют 10 единиц продукции.
Потребность потребителя 2 составляет 10 единиц продукции.
От поставщика 2 к потребителю 2 будем доставлять 10 единиц продукции.
Разместим в ячейку (2:2) значение равное 10.
Мы полностью израсходoвали запасы поставщика 2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Таблица 4
Номер поставщика
|
Предложение поставщика |
Потребители и их спрос | ||||
1 |
2 |
3 |
4 |
5 | ||
|
70 |
90 |
140 |
90 |
105 | ||
|
1 |
80 |
4 |
1 80 |
5 |
1 |
7 |
2 |
230 |
4 25 |
8 10 |
3
|
3 90 |
5 105 |
|
3 |
185 |
3 45 |
3 |
1 140 |
6 |
3 |
Мы нашли начальное решение, то есть израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
Подсчитаем общие затраты на доставку всей продукции.
Общие затраты на доставку всей продукции, для начального решения, составляют 1330 ден. ед.
Опорный план методом Фогеля
Что мы будем делать?
Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Таблица 5
Номер поставщика
|
Предложение поставщика |
Потребители и их спрос | ||||||||||||
1 |
2 |
3 |
4 |
5 |
||||||||||
|
70 |
90 |
140 |
90 |
105 |
D1 |
D2 |
D3 |
D4 |
D5 | |||||
1 |
80 |
4 |
1
|
5 |
1 |
7 |
0 |
- |
- |
- |
- | |||
2 |
230 |
4 70 |
8
|
3 |
3 90 |
5 70 |
0 |
1 |
1 |
1 |
1 | |||
|
3 |
185 |
3 |
3 10 |
1 140 |
6 |
3 35 |
2 |
2 |
2 |
2 |
0 | |||
D1 |
1 |
2 |
2 |
2 |
2 | |||||||||
D2 |
1 |
5 |
2 |
3 |
2 | |||||||||
D3 |
1 |
- |
2 |
3 |
2 | |||||||||
D4 |
1 |
- |
2 |
- |
2 | |||||||||
D5 |
1 |
- |
- |
- |
2 | |||||||||
1)На примере столбца и строки , соответственно:
В каждой строке, найдем разность между двумя ячейками с наименьшими тарифами.
Таблица 6
Номер поставщика
|
Предложение поставщика |
Потребители и их спрос |
| ||||
1 |
2 |
3 |
4 |
5 | |||
|
70 |
90 |
140 |
90 |
105 | |||
|
1 |
80 |
4 |
1 |
5 |
1 |
7 |
0 |
2 |
230 |
4 |
8
|
3 |
3 |
5 |
0 |
|
3 |
185 |
3 |
3 |
1 |
6 |
3 |
2 |
В каждом столбце, найдем разность между двумя ячейками с наименьшими тарифами.
Таблица 7
Номер поставщика
|
Предложение поставщика |
Потребители и их спрос | ||||
1 |
2 |
3 |
4 |
5 | ||
|
70 |
90 |
140 |
90 |
105 | ||
|
1 |
80 |
4 |
1 |
5 |
1 |
7 |
2 |
230 |
4 |
8
|
3 |
3 |
5 |
|
3 |
185 |
3 |
3 |
1 |
6 |
3 |
|
1 |
2 |
2 |
2 |
2 | |
2)Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 2. В данном столбце выберем ячейку (1:2) обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика 1 к потребителю 2, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю 2.
Запасы поставщика 1 составляют 80 единиц продукции.
Потребность потребителя 2 составляет 90 единиц продукции.
От поставщика 1 к потребителю 2 будем доставлять 80 единиц продукции.
Разместим в ячейку (1:2) значение равное 80.
Мы полностью израсходовали запасы поставщика 1.
Вычеркиваем строку 1 таблицы, то есть исключаем ее из дальнейшего рассмотрения.
Таблица 8
Номер поставщика
|
Предложение поставщика |
Потребители и их спрос | ||||
1 |
2 |
3 |
4 |
5 | ||
|
70 |
90 |
140 |
90 |
105 | ||
|
1 |
80 |
4 |
1 80 |
5 |
1 |
7 |
2 |
230 |
4 |
8
|
3 |
3 |
5 |
|
3 |
185 |
3 |
3 |
1 |
6 |
3 |
3) Повторяем предыдущий шаг.
Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 2.В данном столбце выберем ячейку (3:2) как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика 3 к потребителю 2, как минимум, на 5 ден.ед. меньше чем от остальных поставщиков к потребителю 2.
Запасы поставщика 3 составляют 185 единиц продукции. Потребность потребителя 2 составляет 10 единиц продукции.
От поставщика 3 к потребителю 2 будем доставлять 10 единиц продукции.
Разместим в ячейку (3:2) значение равное 10.
Мы полностью удовлетворили потребность потребителя 2. Вычеркиваем столбец 2 таблицы, то есть исключаем его из дальнейшего рассмотрения.
4)Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 4.
В данном столбце выберем ячейку (2:4), как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика 2 к потребителю 4, как минимум, на 3 ден.ед. меньше чем от остальных поставщиков к потребителю 4.
Запасы поставщика 2 составляют 230 единиц продукции.
Потребность потребителя 4 составляет 90 единиц продукции.
От поставщика 2 к потребителю 4 будем доставлять 90 единиц продукции.
Разместим в ячейку (2:4) значение равное 90.
Мы полностью удовлетворили потребность потребителя 4. Вычеркиваем столбец 4 таблицы, то есть исключаем его из дальнейшего рассмотрения.
5)Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку (3:3), как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика 3 к потребителю 3, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю 3.
Запасы поставщика 3 составляют 175 единиц продукции. Потребность потребителя 3 составляет 140 единиц продукции.
От поставщика 3 к потребителю 3 будем доставлять 140 единиц продукции.
Разместим в ячейку (3:3) значение равное 140.
Мы полностью удовлетворили потребность потребителя 3. Вычеркиваем столбец 3 таблицы, то есть исключаем его из дальнейшего рассмотрения.
6)Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 5. В данном столбце выберем ячейку (3:5), как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика 3 к потребителю 5, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю 5.
Запасы поставщика 3 составляют 35 единиц продукции. Потребность потребителя 5 составляет 105 единиц продукции.
От поставщика 3 к потребителю 5 будем доставлять 35 единиц продукции.
Разместим в ячейку (3:5) значение равное 35.
Мы полностью израсходoвали запасы поставщика 3. Вычеркиваем строку 3 таблицы, то есть исключаем ее из дальнейшего рассмотрения.
7)Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает строка 2. В данной строке выберем ячейку (2:1), как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика 2 к потребителю 1, как минимум, на 1 ден.ед. меньше чем к другим потребителям.
Запасы поставщика 2 составляют 140 единиц продукции. Потребность потребителя 1 составляет 70 единиц продукции.