Автор работы: Пользователь скрыл имя, 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
Оценка свободной ячейки (3:3) отрицательная, следовательно решение не является оптимальным.
Построим цикл для выбранной ячейки ( 3:3):
Ячейки образующие цикл для свободной ячейки (3:3) :
(3:3), (3:2) ,( 1:2) , (1:4) , (2:4) , (2:3).
Среди ячеек цикла (3:2) , (1:4) , (2:3) , номера которых четные, найдем ячейку, обладающую наименьшим значением равным 0.
В данном случае, это ячейка (1:4).
От ячеек цикла с четными номерами отнимает 0. К ячейкам с нечетными номерами прибавляем 0.
Таблица 18
Поставщик |
Потребитель |
Запас | |||||
1 |
2 |
3 |
4 |
5 | |||
1 |
4 |
1 |
5 |
1 |
7
|
80 | |
2 |
4 |
8 |
3 |
3 90+0 |
5
|
230 | |
3 |
3 70 |
3 |
1 -2 +0 |
6 |
3 105 |
185 | |
|
Потребность |
70 |
90 |
140 |
90 |
105 |
| |
Фактически, не произошло никаких изменений, но формально - мы получили другое решение, которое позволит нам найти более оптимальное решение.
Общие затраты на доставку всей продукции, по-прежнему, составляют 1325 ден. ед.
Произведем оценку полученного решения.
Примем
,
Найдем оценки свободных ячеек следующим образом
Таблица 19
Поставщик |
Потребитель |
| ||||||||
1 |
2 |
3 |
4 |
5 |
||||||
1 |
4 3 |
1 80 |
5 6 |
1 2 |
7 6 |
|||||
|
2 |
4 -1 |
8 3 |
3 140 |
3 90 |
5 0 |
|||||
|
3 |
3 70 |
3 10 |
1 0 |
6 5 |
3 105 |
|||||
|
|
|
|
|
|
| |||||
Оценка свободной ячейки (2:1) отрицательная, следовательно решение не является оптимальным.
Построим цикл для выбранной ячейки (2:1):
Ячейки образующие цикл для свободной ячейки (2:1) :
(2:1) , (2:3) , (3:3) , (3:1).
Среди ячеек цикла (2:3) , (3:1) , номера которых четные, найдем ячейку, обладающую наименьшим значением равным 70.
Таблица 20
Поставщик |
Потребитель |
Запас | ||||||||||
1 |
2 |
3 |
4 |
5 | ||||||||
1 |
4 |
1 80 |
5 |
1 |
7
|
80 | ||||||
2 |
4 -1+70 |
8 |
3 140-70 |
3 90 |
5
|
230 | ||||||
3 |
3 70-70 |
3 10 |
1 0+70 |
6 |
3 105 |
185 | ||||||
|
Потребность |
70 |
90 |
140 |
90 |
105 |
| ||||||
Общие затраты на доставку всей продукции, для данного решения, составляют:
Произведем оценку полученного решения.
Примем
,
Найдем оценки свободных ячеек следующим образом
Таблица 21
Поставщик |
Потребитель |
| ||||
1 |
2 |
3 |
4 |
5 | ||
1 |
4 4 |
1 80 |
5 6 |
1 2 |
7 6 |
|
|
2 |
4 70 |
8 3 |
3 70 |
3 90 |
5 0 |
|
|
3 |
3 1 |
3 10 |
1 70 |
6 5 |
3 105 |
|
|
|
|
|
|
|
| |
Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное решение.
1.3.2. Метод потенциала на основе опорного плана,
построенного методом минимальной стоимости
Таблица 22
Номер поставщика
|
Предложение поставщика |
Потребители и их спрос | ||||
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 |
Находим потенциалы поставщиков и потребителей для имеющегося решения.
Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.
Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.
Находим новое решение, как минимум, не хуже предыдущего.
Вычисляем общую стоимость доставки всей продукции для нового решения.
Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем
,
Найдем оценки
свободных ячеек следующим
Таблица 23
Поставщик |
Потребитель |
| ||||
|
1 |
2 |
3 |
4 |
5 |
||
1 |
4 7 |
1 80 |
5 10 |
1 5 |
7 9 |
|
|
2 |
4 25 |
8 10 |
3
|
3 90 |
5 105 |
|
|
3 |
3 45 |
3 -4 |
1 140 |
6 4 |
3 -1 |
|
|
|
|
|
|
| ||
Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.
Из свободных ячеек имеющих отрицательные оценки, остановим свой выбор на ячейке (3:5).
Построим цикл для выбранной ячейки:
Ячейки образующие цикл для свободной ячейки (3:5) :
(3:5) , (3:1) , (2:1) , (2:5).
Среди ячеек цикла , номера которых четные, найдем ячейку, обладающую найменьшим значением равную 45.
От ячеек цикла с четными номерами отнимает 45. К ячейкам с нечетными номерами прибавляем 45.
Таблица 24
Поставщик |
Потребитель |
Запас | ||||||||||
1 |
2 |
3 |
4 |
5 | ||||||||
1 |
4 |
1 80 |
5 |
1 |
7
|
80 | ||||||
2 |
4 25+45 |
8 10 |
3 |
3 90 |
5 105-45 |
230 | ||||||
3 |
3 45-45 |
3
|
1 140 |
6 |
3 -1+45 |
185 | ||||||
|
Потребность |
70 |
90 |
140 |
90 |
105 |
| ||||||
Общие затраты на доставку всей продукции, для данного решения, составляют:
Произведем оценку полученного решения.
Примем
,
Найдем оценки
свободных ячеек следующим
Таблица 25
Поставщик |
Потребитель |
| ||||
1 |
2 |
3 |
4 |
5 | ||
1 |
4 7 |
1 80 |
5 9 |
1 5 |
7 9 |
|
2 |
4 70 |
8 10 |
3
|
3 90 |
5 60 |
|
3 |
3 1 |
3 -3 |
1 140 |
6 5 |
3 45 |
|
|
|
|
|
|
| |
Оценка свободной ячейки (3:2) отрицательная, следовательно решение не является оптимальным.
Построим цикл для выбранной ячейки (3:2)
Ячейки образующие цикл для свободной ячейки (3:2) :
(3:2) , (3:5) , (2:5) , (2:2).
Среди ячеек цикла, номера которых четны, найдем ячейку, обладающую наименьшим значением равным 10.
От ячеек цикла с четными номерами отнимает 10. К ячейкам с нечетными номерами прибавляем 10.
Таблица 26
Поставщик |
Потребитель |
Запас | ||||||||||
1 |
2 |
3 |
4 |
5 | ||||||||
1 |
4 |
1 80 |
5 |
1 |
7
|
80 | ||||||
2 |
4 70 |
8 |
3 |
3 90 |
5 |
230 | ||||||
3 |
3 |
3 -3 |
1 140 |
6 |
3 45-10 |
185 | ||||||
|
Потребность |
70 |
90 |
140 |
90 |
105 |
| ||||||