Методы пр.р. 3

Министерство образования и науки РФ
ФГАОУ Национальный исследовательский технологический университет
«МИСиС»
Институт экономики и управления промышленными предприятиями
Кафедра Бизнес-информатики и систем управления предприятиями








МАТЕМАТИЧЕСКИЕ МЕТОДЫ МОДЕЛИРОВАНИЯ, ОПТИМИЗАЦИИ И ПРИНЯТИЯ РЕШЕНИЙ
ПРАКТИЧЕСКАЯ РАБОТА №3.
ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ СКЛАДОВ С ИСПОЛЬЗОВАНИЕМ ТРАНСПОРТНОЙ ЗАДАЧИ ЛП





Выполнил:
Ст. Куксов А.Б.
Гр. МЭ-11-4/Э-2-11-2
Вариант №9


Принял:
Литвяк В. С.







Москва 2013 г.
Содержание:
Постановка задачи...3
Краткое описание метода4
Решение задачи....5
Краткий вывод.15
1. Постановка задачи

Торговый дом имеет четыре супермаркета, расположенные в четырех районах P, Q, R, S. Поставки продукции в эти супермаркеты осуществляются с двух, всегда полностью заполненных, складов А и В, площади которых вмещают по 40 контейнеров.
Прогнозирование спроса, выполненное службой маркетинга, показывает, что потребность супермаркетов в продукции в скором времени составит 50, 25, 30 и 35 контейнеров в день, соответственно.
Поэтому, планируется построить третий склад, который также всегда будет полностью заполнен и площадь которого вместит 60 контейнеров.
В таблице 1 приведены транспортные затраты (в руб.), соответствующие перевозкам одного контейнера со складов А и В и нового склада в каждый из супермаркетов. При этом рассматриваются два варианта размещения нового склада.
Менеджеру торгового дома требуется выбрать и обосновать оптимальный вариант размещения нового склада. Указать соответствующие оптимальные затраты. Результаты представить в графической форме.
Проверить результаты решением в среде EXCEL.
Табл.1
Склад
P
Q
R
S

A
70
94
46
120

B
101
90
75
119

С (вариант 1)
115
106
70
90

D (вариант 2)
135
95
80
84


2. Краткое описание метода.

Традиционная постановка транспортной задачи такова:
Имеются m поставщиков и n потребителей. У поставщиков сосредоточен однородный груз в количестве a1, a2,..am. Спрос потребителей на груз: в1, в2,.вn. Известны стоимости (тарифы) с ij на перевозку единицы груза от i-го поставщика к j- му потребителю. Требуется составить оптимальный план перевозок грузов такой, чтобы:
1. вывести весь груз поставщиков
2. удовлетворить весь спрос потребителей
3. минимизировать суммарные затраты.
Транспортная задача, как задача ЛП может быть решена симплексным методом. Но существуют более простые методы решения которые являются модификацией симплексного метода. Наиболее известным из них является метод потенциалов. В нем применяется тот же прием последовательного улучшения плана, состоящий из трех этапов:
- находится исходное опорное решение;
- оценка решения на оптимальность;
- переход к другому лучшему опорному решению путем однократного замещения одной базовой переменной на свободную.
При этом первоначальное опорное решение ищется с помощью метода «северо-западного угла» или «минимального элемента»
Транспортную задачу ЛП можно также решить в среде Microsoft Excel, меню Сервис-Поиск решения.
3. Решение задачи.

Вариант С.
Потр.
Пост.
P
Q
R
S
Запасы

A
70

94

46

120

40

B
101

90

75
119

40

C
115

106

70

90

60

Спрос
50
25
30
35



Распределим запасы в соответствии со спросом, удовлетворяя в первую очередь спрос тех, чей тариф минимален. Получаем:
Потр.
Пост.
P
Q
R
S
Запасы

A
70
10
94
0
46
30
120
0
0

B
101
15
90
25
75
0
119
0
0

C
115
25
106
0
70
0
90
35
0

Спрос
0
0
0
0



Проверка M+N-1=6.
F=70*10+46*30+101*15+90*25+115*25+90*35=11870
Проверим план на оптимальность с помощью потенциалов:
U1+V1=70 V1=70 U1+V2
·94
U1+V3=46 V3=46 U1+V4
·120
U2+V1=101 U2=31 U2+V3
·75 U2+V3=77
U2+V2=90 V2=59 U2+V4
·119
U3+V1=115 U3=45 U3+V2
·106
U3+V4=90 V4=45 U3+V3
·70 U3+V3 =91
U1=0 U1=0
Условие оптимальности не выполнено для клеток (3;3) и (2;3). Выбираем клетку (3;3), т.к. условие оптимальности в ней нарушено в наибольшей степени.
Потр.
Пост.
P
Q
R
S
Ui

A
+ 70
10
94
0
- 46
30
120
0
0

B
101
15
90
25
75
0
119
0
31

C
115
25 -
106
0
70
0 +
90
35
45

Vj
70
59
46
45




·=25


Потр.
Пост.
P
Q
R
S
Ui

A
+ 70
35
94
0
- 46
5
120
0
0

B
101
15 -
90
25
75
0 +
119
0
31

C
115
0
106
0
70
25
90
35
24

Vj
70
59
46
66



Снова проверяем условия оптимальности:
U1+V1=70 V1=70 U1+V2
·94
U1+V3=46 V3=46 U1+V4
·120
U2+V1=101 U2=31 U2+V3
·75 U2+V3=77
U2+V2=90 V2=59 U2+V4
·119
U3+V3=70 U3=24 U3+V1
·115
U3+V4=90 V4=66 U3+V2
·106
U1=0 U1=0
Условие оптимальности нарушено в клетке (2;3).






Потр.
Пост.
P
Q
R
S
Ui

A
70
40
94
0
46
0
120
0
0

B
101
10
90
25
75
5
119
0
31

C
115
0
106
0
70
25
90
35
26

Vj
70
59
44
64



Проверяем условие оптимальности:
U1+V1=70 V1=70 U1+V2
·94
U2+V1=46 V3=44 U1+V3
·16
U2+V2=101 U2=31 U1+V4
·120
U2+V3=90 V2=59 U2+V4
·119
U3+V3=70 U3=26 U3+V1
·115
U3+V4=90 V4=64 U3+V2
·106
U1=0 U1=0
Условие оптимальности выполнено.
Fmin=70*40+101*10+90*25+75*5+70*25+90*35=11335
X11=40
X21=10
X22=25
X23=5
X33=25
X34=35
Вариант D.

Потр.
Пост.
P
Q
R
S
Запасы

A
70

94

46

120

40

B
101

90

75
119

40

C
135

95

80

84

60

Спрос
50
25
30
35



Распределим запасы в соответствии со спросом, удовлетворяя в первую очередь спрос тех, чей тариф минимален. Получаем:
Потр.
Пост.
P
Q
R
S
Запасы

A
70
10
94
0
46
30
120
0
0

B
101
15
90
25
75
0
119
0
0

C
135
25
95
0
80
0
84
35
0

Спрос
0
0
0
0



Проверка M+N-1=6.
F=70*10+46*30+101*15+90*25+135*25+84*35=12160
Проверим план на оптимальность с помощью потенциалов:
U1+V1=70 V1=70 U1+V2
·94
U1+V3=46 V3=46 U1+V4
·120
U2+V1=101 U2=31 U2+V3
·75 U2+V3=77
U2+V2=90 V2=59 U2+V4
·119
U3+V1=135 U3=65 U3+V2
·95 U3+V2 =124
U3+V4=84 V4=19 U3+V3
·80 U3+V3 =111
U1=0 U1=0
Условие оптимальности не выполнено для клеток (3;3), (3;2) и (2;3). Выбираем клетку (3;3), т.к. условие оптимальности в ней нарушено в наибольшей степени.
Потр.
Пост.
P
Q
R
S
Ui

A
+ 70
10
94
0
- 46
30
120
0
0

B
101
15
90
25
75
0
119
0
31

C
135
25 -
95
0
80
0 +
84
35
65

Vj
70
59
46
19




·=25




Потр.
Пост.
P
Q
R
S
Ui

A
+ 70
35
94
0
- 46
5
120
0
0

B
101
15 -
90
25
75
0 +
119
0
31

C
135
0
95
0
80
25
84
35
34

Vj
70
59
46
50



Снова проверяем условия оптимальности:
U1+V1=70 V1=70 U1+V2
·94
U1+V3=46 V3=46 U1+V4
·120
U2+V1=101 U2=31 U2+V3
·75 U2+V3=77
U2+V2=90 V2=59 U2+V4
·119
U3+V3=80 U3=34 U3+V1
·135
U3+V4=84 V4=50 U3+V2
·95
U1=0 U1=0
Условие оптимальности нарушено в клетке (2;3).






Потр.
Пост.
P
Q
R
S
Ui

A
70
40
94
0
46
0
120
0
0

B
101
10
90
25
75
5
119
0
31

C
135
0
95
0
80
25
84
35
36

Vj
70
59
44
48



Проверяем условие оптимальности:
U1+V1=70 V1=70 U1+V2
·94
U2+V1=101 V3=44 U1+V3
·46
U2+V2=90 U2=31 U1+V4
·120
U2+V3=75 V2=59 U2+V4
·119
U3+V3=80 U3=36 U3+V1
·135
U3+V4=84 V4=48 U3+V2
·95
U1=0 U1=0
Условие оптимальности выполнено.
Fmin=70*40+101*10+90*25+75*5+80*25+84*35=11375
X11=40
X21=10
X22=25
X23=5
X33=25
X34=35
Краткий вывод.
В обоих случаях мы нашли оптимальный план. Однако первый вариант более экономен (хотя не на много). Поэтому новый склад нужно размещать в соответствии с первым вариантом.
15

Приложенные файлы

  • doc 23875878
    Размер файла: 453 kB Загрузок: 1

Добавить комментарий