Кириллов Исследование операций / Расчетно-графическое задание №2 по ИО
.docx
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра экономической информатики
Расчетно-графическое задание №2
по курсу
«Исследование операций»
Выполнил:
Факультет Бизнеса
Группа: ФБИ-22
Преподаватель: Кириллов Ю.В.
Новосибирск 2014
Цель работы
– приобрести практические навыки и опыт решения транспортной задачи
(ТЗ) линейного программирования в матричной постановке с помощью программы пакет экономических расчетов (ПЭР);
– научиться анализировать полученное решение, находить возможные варианты решения;
– увидеть связь между ТЗ и общей задачей линейного программирования
(ОЗЛП), а также между математическими моделями ТЗ и задачи о назначениях (ЗН).
Условие задачи
Транспортная фирма обслуживает n поставщиков и m потребителей однородного груза. В течение дня из каждого пункта поставки фирма должна вывезти соответственно A1,A2,…,An тонн груза, а в каждый пункт потребления доставить соответственно B1, B2, …, Bm тонн. Себестоимость (в тысячах рублей) перевозки одной тонны груза от i-го поставщика j-му потребителю заданы матрицей C=║n×m.Найти такой план перевозки грузов, при котором издержки транспортной фирмы будут минимальными.
Рис.1 Исходные условия «Вариант 4»
Запишем математическую модель задачи:
Z(X)= 10x11+8x12+12x13+9x14+6x15+
+5x21+7x22+11x23+6x24+7x25+
+12x31+8x32+9x33+12x34+10x35
Ограничения по полному вывозу имеющейся продукции со всех складов представлены уравнениями:
Ограничения по полному удовлетворению потребностей всех магазинов представлены уравнениями:
Построим модель двойственной к заданной задаче:
Z(x)=80u1+320u2+225u3+215v1+110v2+120v3+90v4+125v5→max
3. Построим опорные планы ТЗ методом северо-западного угла, методом минимального элемента и методом Фогеля. Сравним результаты.
Так как =625, =660 (потребности превышают запасы). Данная модель ТЗ является открытой. Согласно правилам сведения открытой модели ТЗ к закрытой, введем фиктивный склад с запасом =35 ед. Тарифы перевозок с этого склада в любой магазин равны 0.
Таблица 1
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10 |
8 |
12 |
9 |
6 |
80 |
|
A2 |
5 |
7 |
11 |
6 |
7 |
320 |
|
A3 |
12 |
8 |
9 |
12 |
10 |
225 |
|
A4 |
0 |
0 |
0 |
0 |
0 |
35 |
|
Потребность ед. прод. |
215 |
110 |
120 |
90 |
125 |
> 660>625 |
Метод северо-западного угла
Первая клетка для заполнения в табл. 1 А1В1. Потребности в В1 составляют 215, а запасы в А1 равны 80. Удовлетворим полностью потребности В1 и больше туда не с какого склада не повезем. Остаток запасов в А1 равен 135.
Таблица 2
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10 80 |
8 |
12 |
9 |
6 |
80-80=0 |
|
A2 |
5 135 |
7 110 |
11 75 |
6 |
7 |
320-135=185-110=75-75=0 |
|
A3 |
12 |
8 |
9 45 |
12 90 |
10 90 |
225-45=180-90=90-90=0 |
|
A4 |
0 |
0 |
0 |
0 |
0 35 |
35-35=0 |
|
Потребность ед. прод. |
215-80=135-135=0 |
110-110=0 |
120-75=45-45=0
|
90-90=0 |
125-35=90-90=0 |
> 660>625 |
Следующий шаг: из всех оставшихся свободных клеток рабочего поля Т-таблицы левой верхней является А2В1. Отдадим В1 остаток с А2. и рассчитаемся с этим складом полностью. При этом в А2 еще останются запасы в 185 ед.
Следующий кандидат на заполнение – клетка А2В2. С потребностью В2 окончательно рассчитываемся из А2.
Аналогичным образом распределяем оставшиеся запасы между еще имеющимися потребностями. Последовательное заполнение клеток А2В3 , А3В3 , А3В4, А3В5 и А4В5.
Проверим выполнение условия вырождения (число занятых клеток должно равняться): m+n-1=8. Следовательно, данный опорный план является невырожденным.
=
Общая стоимость запланированных в нем перевозок составляет:
Z() = 10*80+5*135+7*110+11*75+9*45+12*90+10*90=5455
Метод минимального элемента
Построим методом МЭ начальный опорный план задачи. Для этого выберем в исходной Т-таблице (см. табл. 1) клетки - кандидаты на заполнение: очевидно, это одна из перевозок А4Вj, тарифы которых наименьшие (равны 0). В принципе выбрать можно любую из них, но мы остановимся на А4В5.
Таблица 3
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10 |
8 |
12 |
9 |
6 80 |
80-80=0 |
|
A2 |
5 215 |
7 5 |
11 |
6 90 |
7 10 |
320-215=105-90=15-10=5 |
|
A3 |
12 |
8 105 |
9 120 |
12 |
10 |
225-105=120-120=0 |
|
A4 |
0 |
0 |
0 |
0 |
0 35 |
35-35=0 |
|
Потребность ед. прод. |
215-215=0 |
110-5=105-105=0 |
120-120=0 |
90-90=0 |
125-35=90-80=10 |
> 660>625 |
Следующими кандидатами на заполнение по методу МЭ будут клетка А2В1.
Следующими кандидатами становятся А1В5 и А2В4, так как тарифы у них равны (с15=с24=6). Теперь А2В2 и А2В5 становятся следующими кандидатами на заполнение на следующем шаге (с22=с25=7).
Следующим «по рангу» кандидатом на заполнение будет клетка А3В2.
Осталась единственная свободная клетка А3В3, заполняя которую, устанавливаем окончательный баланс распределений по строкам и столбцам (т.е. запасов по потребностям).
Проверим выполнение условия вырождения: число занятых клеток должно равняется 8. Следовательно, данный опорный план является невырожденным.
=
Общая стоимость запланированных в нем перевозок составляет: Z() = 6*80+5*215+7*5+6*90+7*10+8*105+9*120=4120
Таким образом, начальный опорный план по методу МЭ оказывается более дешевым по сравнению с начальным планом по методу NWC.
Метод Фогеля
Считаем разности между двумя наименьшими тарифами свободных клеток в каждой строке и каждом столбце и записываем их в соответствующие клетки дополнительной строки и столбца.
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
Δ1 |
||||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
|
|||
A1 |
10 |
8 |
12 |
9 |
6 80 |
80-80=0 |
2,2 |
||
A2 |
5 215 |
7 |
11 |
6 90 |
7 15 |
320-215=105-90=15-15=0 |
1,1,4 |
||
A3 |
12 |
8 110 |
9 85 |
12 |
10 30 |
225-30=195-110=85-85=0 |
1,1,1,1 |
||
A4 |
0 |
0 |
0 35 |
0 |
0 |
35-35=0 |
0 |
||
Потребность ед. прод. |
215-215=0 |
110-110=0 |
120-35=85-85=0 |
90-90=0 |
125-80=45-15=30-30=0 |
||||
Δ1 |
5 5 |
7 1 1 8 |
9 2 2 3 |
6 3 6 |
6 1 3 10 |
Очевидно, что наибольшие разности первого шага находятся в столбце В3. Заполняем клетку с наименьшим тарифом: . На следующем шаге процесс повторяется для оставшихся свободных клеток. Наибольшая разность второго шага становится в столбце В1. Заполняем в нем клетку с наименьшим тарифом .
Аналогично методу МЭ условие вырождения здесь также выполняется, т.к. число занятых клеток равно 8. Это означает, что начальный опорный план является невырожденным .
=
Общие затраты на все перевозки в начальном опорном плане по методу Фогеля составляют:
Z() = 5*215+6*90+6*80+7*15+8*110+9*85+10*30=4145.
4. На основе опорного плана, полученного методом северо-западного угла, решим задачу методом потенциалов.
Таблица 4
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10 80 |
8 |
12 |
9 |
6 |
80-80=0 |
|
A2 |
5 135 |
7 110 |
11 75 |
6 |
7 |
320-135=185-110=75-75=0 |
|
A3 |
12 |
8 |
9 45 |
12 90 |
10 90 |
225-45=180-90=90-90=0 |
|
A4 |
0 |
0 |
0 |
0 |
0 35 |
35-35=0 |
|
Потребность ед. прод. |
215-80=135-135=0 |
110-110=0 |
120-75=45-45=0
|
90-90=0 |
125-35=90-90=0 |
> 660>625 |
Построим уравнения для заполненных клеток табл.4:
Рассмотрим теперь вычисление оценки рентабельности перевозок, не включенных в опорный план Т-таблицы, используя полученные значения потенциалов:
Из системы следует, что критерий оптимальности плана еще не выполняется, т.к. оценки рентабельности перевозок – положительны. С экономической точки зрения это означает, что в условиях, когда запланированные перевозки имеют 100% рентабельность, среди не включенных в план есть такие, которые имеют рентабельность выше 100%, из-за своей низкой себестоимости. Отсюда следует, что перевозку с наибольшей оценкой рентабельности необходимо включить в план в первую очередь. Чтобы включить перевозку в следующий опорный план, необходимо загрузить в клетку определенное количество груза. Но, чтобы не нарушить при этом созданный в начальном опорном плане баланс запасов и потребностей по строкам и столбцам табл.19, необходимо для клетки построить цикл пересчета.
Далее следует обозначить знаками (+) и (-) вершины цикла, начиная обязательно со знака (+) в выбранной свободной клетке, затем по очереди все остальные вершины цикла.
В вершины, обозначенные (+) добавляем часть груза, которую вычитаем у клеток с (-), причем общее количество вычитаемого количества груза равняется количеству добавленного груза. Таким образом, происходит перераспределение груза внутри цикла, но общий баланс по строкам и столбцам не изменяется. Именно поэтому количество клеток цикла с (+) должно равняться количеству клеток с (-). Количество вычитаемого груза определяется по принципу: вычесть у каждой отрицательной клетки количество равное наименьшей загрузке всех клеток с (-).
Таким образом, новый опорный план данной ТЗ будет выглядеть так, как показано в таблице 5.
Таблица 5
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10 5 |
8 |
12 |
9 |
6 75 |
80 |
|
A2 |
5 210 |
7 110 |
11
|
6 |
7 |
320 |
|
A3 |
12 |
8 |
9 120 |
12 90 |
10 15 |
225 |
|
A4 |
0 |
0 |
0 |
0 |
0 35 |
35 |
|
Потребность ед. прод. |
215 |
110 |
120
|
90 |
125 |
> 660>625 |
Z=4630
Далее процесс повторяется: полученный опорный план необходимо вновь проверить по практическим правилам критерия оптимальности. Для этого вновь составляем систему уравнений для занятых клеток табл. 5:
Перевозка имеет самую высокую оценку рентабельности, поэтому включаем её в следующий план.
Таблица 6
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10
|
8 |
12 |
9 |
6 80 |
80 |
|
A2 |
5 215 |
7 105 |
11
|
6 |
7 |
320 |
|
A3 |
12 |
8 5 |
9 120 |
12 90 |
10 10 |
225 |
|
A4 |
0 |
0 |
0 |
0 |
0 35 |
35 |
|
Потребность ед. прод. |
215 |
110 |
120 |
90 |
125 |
> 660>625 |
Z=4590
Из системы следует, что критерий оптимальности плана еще не выполняется. Перевозку с наибольшей оценкой рентабельности необходимо включить в план в первую очередь.
Таблица 7
Пункты отправления, Ai |
Пункты потребления, Bj |
Запасы, ед. прод. |
|||||
B1 |
B2 |
B3 |
B4 |
B5 |
|
||
A1 |
10
|
8 |
12 |
9 |
6 80 |
80 |
|
A2 |
5 215 |
7 15 |
11
|
6 90 |
7 |
320 |
|
A3 |
12 |
8 95 |
9 120 |
12
|
10 10 |
225 |
|
A4 |
0 |
0 |
0 |
0 |
0 35 |
35 |
|
Потребность ед. прод. |
215 |
110 |
120 |
90 |
125 |
> 660>625 |