Модели оптимального объема производства
Министерство образования и науки
Российской Федерации
Федеральное государственное бюджетное
образовательное учреждение высшего профессионального образования
Санкт-Петербургский государственный
горный университет
Кафедра информатики и
компьютерных технологий
Курсовая работа
По дисциплине: Экономико-математические модели и методы
Модели оптимального объема производства
Выполнил: студент ЛГ-08
Перцева Е.А.
Проверил: Доцент
Петухова Н.М.
Санкт-Петербург 2012
Содержание
1. Введение
. Задача 1
. Задача 2
. Задача 3
. Задача 4
1. Введение
Целью курсовой работы является развитие у студентов навыков использования
математических методов при решении экономических задач и задач управления. При
выполнении курсовой работы студент осваивает следующие этапы решения задачи:
)построение математической модели
)нахождение оптимального решения, используя математические методы
)решение задачи средствами Excel
модель
оптимальный объем производство перевозка
2. ЗАДАЧА 1
УСЛОВИЯ ЗАДАЧИ
Цех предприятия производит два вида изделий А и В, для изготовления
которых требуются ресурсы трех видов R1, R2, R3.
Данные о наличии ресурсов, количество ресурсов каждого вида, необходимое для
изготовления тысячи изделий А и В (нормы расхода), а также прибыль, получаемая
от реализации тысячи изделия каждого вида, приведены в табл. 1.1. Определить
оптимальные объемы производства каждого вида изделий за плановый период,
обеспечивающие максимальную прибыль предприятию.
Таблица 1.1
|
Виды ресурсов
|
Наличие
|
Нормы расхода
|
|
|
Тип А
|
Тип В
|
|
R1
|
200
|
10
|
5
|
|
R2
|
100
|
2,5
|
5
|
|
R3
|
60
|
2
|
1,2
|
|
Прибыль от продажи
|
15
|
16
|
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
Пусть за плановый период выпускается Х1 (тыс. шт.)
изделий А и Х2 (тыс. шт.) изделий В. По условию
задачи (табл.1) прибыль, получаемая от реализации 1000 шт. изделий А,
составляет 15 (уел. ед.), а 1000 шт. изделий В - 16 (усл.ед.).
Тогда прибыль, получаемая от реализации Xt (тыс. шт.)
изделий А и Х2 (тыс. шт.) изделий В, выпущенных
за плановый период, может быть записана в виде выражения Z= 15 Х1+16Х2.
Отрицательные значения Х1 и Х2 не
имеют смысла, то есть Х1 >=0, Х2 >=0.
Величины Х1 и Х2 нельзя выбирать
произвольно, так как на них накладываются ограничения, определяемые наличием
ресурсов R1, R2, R3. Как видно из табл. 1, для изготовления тыс.
шт. изделий А требуется 10 (ед.) ресурса R1, а для изготовления
тыс. шт. изделий В - 5 (ед.) ресурса R1. Следовательно,
расход ресурса R1 для выпуска Х1 (тыс.шт.) изделий А
составит 10 Х1 (ед.), а для выпуска Х2 (тыс.
шт.) изделий В - 5Х2 (ед.). Таким образом, для
планового выпуска деталей А и В потребуется 10 Х1+
5Х2 (ед.) ресурса R1. В связи с тем, что запас ресурса
R1 составляет 200 (ед.), ограничение по нему будет иметь вид: 10 Х1
+ 5Х2, <= 200;
Аналогично рассуждая, можно составить ограничения для ресурсов R2
и R3: R2: 2,5Х1 + 5Х2<=
100;
R3: 2 Х1 + 1,2Х2<= 60.
Получили математическую модель задачи.
Имеем целевую функцию линейной формы:
Z = 15Xi + 16Х2 -> шах (1)
систему линейных ограничений:
10 Х1 + 5Х2, <= 200
,5Х1 + 5Х2<= 100 (2)
Х1 + 1,2Х2<= 60
и граничные условия: X, >= 0, Х2 >=0 (3)
Задача формулируется следующим образом: найти такие неотрицательные
значения переменных X, и Х2, которые будут
удовлетворять системе ограничений (2) и обращать в максимум целевую
функцию (1).
Целевая функция и ограничения имеют линейную форму, поэтому данная задача
относится к классу задач линейного программирования и для ее решения можно
использовать симплекс-метод. Так как задача имеет только две переменные, она
может быть решена графическим методом.
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ
Введем на плоскости прямоугольную систему координат Х1, Х2.
ОПРЕДЕЛЕНИЕ ОБЛАСТИ ДОПУСТИМЫХ РЕШЕНИЙ
Область допустимых решений определяется граничными условиями (3) и
системой неравенств (2). Граничные условия Х1 >=0, Х2
>=0 указывают на то, что область допустимых решений находится в 1-м
квадранте.
Построим систему неравенств (2). Каждое неравенство геометрически
определяет полуплоскость с граничными прямыми
10 Х1 + 5Х2, <= 200
,5Х1 + 5Х2<= 100 (4)
Х1 + 1,2Х2<= 60
Построим эти прямые (рис. 1). Каждая из них делит плоскость на две
полуплоскости. Решение следует искать в той полуплоскости, все точки которой
удовлетворяют неравенству. Чтобы определить эту полуплоскость, возьмем
какую-нибудь точку на плоскости, например точку с координатами (0,0). Если
приравнять нулю значения Х1 и Х2 в левой
части соответствующих неравенств, получим соотношение 0 <= const, значит
точка с координатами (0,0) входит в полуплоскость, соответствующую
рассматриваемому неравенству. Во все полуплоскости, соответствующие ограничениям
(2) входит начало координат (при Х1=Х2=0 10 Х1 + 5Х2,
<= 200, 2,5Х1 + 5Х2<= 100, 2 Х1 + 1,2Х2<=
60). Так как система (2) совместна, то полуплоскости, пересекаясь, образуют
общую для всех полуплоскостей часть, которая представляет собой многоугольник.
Таким образом, определили область, удовлетворяющую всем ограничениям и
граничным условиям, то есть область допустимых решений (многоугольник решений).
Известно, что оптимальное решение должно находиться на границе этой области, и,
если решение единственное, в одной из ее вершин. Точка с координатами (X1,
Х2), в которой значение целевой функции достигает максимума,
должна находиться в одной из вершин выделенного многоугольника.
НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ
Проведем линию уровня целевой функции, проходящую через начало
координат:= 15Х1 + 16Х2 = 0.
Значение Z возрастает в направлении нормального вектора п = {15;
16}. Будем передвигать прямую параллельно самой себе в направлении вектора п до
тех пор, пока многоугольник решений не будет находиться по одну сторону от нее,
и прямая не будет иметь с ним, по крайней мере, одну общую точку. Этой точкой
будет точка С с координатами Х1 = 13,3 и Х2= 13,3,
в которой целевая функция Z принимает максимальное значение. Подставив значения
Х1= 13,3 и Х2= 13,3 в целевую функцию Z=
15Х1 + 16Х2 = 0. Получим ее максимальное значение Z = 15∙13,3+16∙13,3
=413.
Общая прибыль от реализации x1 изделий вида А и x2
изделий вида В составит:
Z=15∙x1+16∙x2→max
Таким образом, мы приходим к решению следующей математической задачи:
среди всех неотрицательных решений данной системы линейных неравенств требуется
найти такое, при котором функция Z принимает максимальное значение.
Решим неравенства, преобразовав их в равенства:
1) 10∙x1+5∙x2=2001=0
→ x2=402=0 → x1=20
) 2,5∙x1+5∙x2=1001=0
→ x2=202=0 → x1=40
) 2∙x1+1,2∙x2=601=0
→ x2=502=0 → x1=30
∙x1+5∙x2=200
,5∙x1+5∙x2=1001=13,3
(13)2=13,3 (13)=15∙13,3+16∙13,3=413
Это оптимальное решение.
(Точность решения задачи будет зависеть от точности
построения графика.)
Ответ: max Z =413 при Xt = 13,3, Х2 =
13,3.
ИСПОЛЬЗОВАНИЕ СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧИ
Определение базисного (допустимого) решения
∙x1+5∙x2≤200 10∙x1+5∙x2+x3=200
,5∙x1+5∙x2≤100 2,5∙x1+5∙x2+x4=100
∙x1+1,2∙x2≤60 2∙x1+1,2∙x2+x5=601,
x2, x3, x4, x5≥0 Z=15∙x1+16∙x2+0∙x3+0∙x4+0∙x53=200-(10∙x1+5∙x2)4=100-(2,5∙x1+5∙x2)5=60-(2∙x1+1,2∙x2)=0-(-15∙x1-16∙x2-0∙x3-0∙x4-0∙x5)
x1=0, x2=0, x3=200, x4=100, x5=60
. Из отрицательных элементов последней строки табл.1.2, соответствующих
переменным x1 и x2, выберем максимальный по модулю
элемент: -16, соответствует x2. Небазисная переменная x2 должна
быть введена в базис. 2. Поделим элементы столбца значений базисных переменных
на соответствующие положительные коэффициенты выбранного столбца: 200/5=40
/5=20
60/1,2=50
Запишем частные от деления во вспомогательный столбец б. Выберем элемент,
который дает минимальное частное от деления: 20. Минимальное частное 20
соответствует второй строке с базисной переменной x4. Переменная x4
должна быть выведена из базиса.
. Разделим элементы выбранной строки (второй строки) на разрешающий
элемент (5). Результат запишем во вторую строку симплекс-таблицы 9. Построение
первой строки симплекс-таблицы 1.3
. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на
коэффициент первого элемента выделенного столбца симплекс-таблицы 1.2 и вычтем
из соответствующих элементов первой строки симплекс-таблицы 1.2. Получим первую
строку симплекс-таблицы 1.3.
Построение третьей строки симплекс-таблицы 1.3.
. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на
коэффициент третьего элемента выделенного столбца симплекс-таблицы 1.2 и вычтем
из соответствующих элементов третьей строки симплекс-таблицы 1.2. Получим
третью строку симплекс-таблицы 1.3.
Построение четвертой строки симплекс-таблицы 1.3
. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на
коэффициент четвертого элемента выделенного столбца симплекс-таблицы 1.2 и
вычтем из соответствующих элементов четвертой строки симплекс-таблицы 1.2.
Получим четвертую строку симплекс-таблицы 1.3. 7. В симплекс-таблице 1.3
проделываются аналогичные операции, что и в симплекс-таблице 1.2. Полученные
результаты записываем в симплекс-таблицу 1.4.
Таблица 1.2
|
№
|
Базисные переменные
|
Значения базисных переменных
|
Коэффициенты
|
|
|
|
|
х1
|
х2
|
х3
|
х4
|
х5
|
б
|
|
1
|
х3
|
200
|
10
|
5
|
1
|
0
|
0
|
40
|
|
2
|
х4
|
100
|
2,5
|
5
|
0
|
1
|
0
|
20
|
|
3
|
х5
|
60
|
2
|
1,2
|
0
|
0
|
1
|
50
|
|
4
|
z
|
0
|
-15
|
-16
|
0
|
0
|
0
|
|
Таблица 1.3
|
№
|
Базисные переменные
|
Значения базисных переменных
|
Коэффициенты
|
|
|
|
|
х1
|
х2
|
х3
|
х4
|
х5
|
б
|
|
1
|
х3
|
100
|
7,5
|
0
|
1
|
-1
|
0
|
13,3
|
|
2
|
х2
|
20
|
0,5
|
1
|
0
|
0,2
|
0
|
40
|
|
3
|
х5
|
36
|
1,4
|
0
|
0
|
-0,24
|
1
|
25,7
|
|
4
|
z
|
320
|
-7
|
0
|
0
|
3,2
|
0
|
|
Проверим, является ли данное решение допустимым.
Так как в столбце значений базисных переменных все элементы
неотрицательные, то полученное решение является допустимым.
Проверка на оптимальность:
целевая функция имеет максимальное значение, так как все коэффициенты в
строке целевой функции положительны.
Таблица 1.4
|
№
|
Базисные переменные
|
Значения базисных переменных
|
Коэффициенты
|
|
|
|
х1
|
х2
|
х3
|
х4
|
х5
|
|
1
|
x1
|
13,33
|
1
|
0
|
0,1333
|
-0,133
|
0
|
|
2
|
x2
|
13,33
|
0
|
1
|
-0,07
|
0,27
|
0
|
|
3
|
x5
|
17,33
|
0
|
0
|
-0,19
|
-0,05
|
1
|
|
4
|
z
|
413
|
0
|
0
|
1
|
2
|
0
|
Двойственная задача
Исходная задача Двойственная задача
10∙x1+5∙x2≤200 10∙y1+2,5∙y2+2∙y3≥15
,5∙x1+5∙x2≤100 5∙y1+5∙y2+1,2∙y3≥16
∙x1+1,2∙x2≤601,x2≥0=15∙x1+16∙x2→max
Zд=200∙y1+100∙y2+60∙y3→min
Анализ оптимального решения
При увеличении ресурса Ri: Z=Zопт+yi∙1
При уменьшении ресурса Ri: Z=Zопт-yi∙11:
Z=Zопт+1∙1=413+1=414
Z=Zопт-1∙1=413-1=4122: Z=Zопт+2∙1=413+2=415
Z=Zопт-2∙1=413-2=4113: Z=Zопт+0∙1=413+0=413
Z=Zопт-0∙1=413-0=413
Отчёты по пределам
Z=15∙13,3+16∙13,3=413
Для значения х1 на нижнем пределе:=15∙0+16∙13,3=213
Для значения х2 на нижнем пределе:=15∙13,3+16∙0=200
РЕШЕНИЕ ЗАДАЧИ В EXCEL
Для решения задачи составьте электронную таблицу, отражающую ее
математическую модель (рис. 2, 3). На рис. 2 показана электронная таблица в
режиме отображения вычислений (исходное состояние), на рис. 3 - в режиме
отображения формул. На рисунках введено сокращение: ЦФ - целевая функция.
Рис. 2
Рис. 3
|
переменные
|
х1
|
х2
|
|
|
|
|
значение
|
0
|
0
|
|
|
|
|
|
|
цф
|
|
|
|
коэф вцф
|
15
|
16
|
=СУММПРОИЗВ(B3:C3;B5:C5)
|
|
|
|
|
|
|
|
|
|
ресурсы
|
|
|
левая часть
|
знак
|
правая часть
|
|
R1
|
10
|
5
|
=СУММПРОИЗВ($B$3:$C$3;B8:C8)
|
≤
|
200
|
|
R2
|
2,5
|
5
|
=СУММПРОИЗВ($B$3:$C$3;B9:C9)
|
≤
|
100
|
|
R3
|
2
|
1,2
|
=СУММПРОИЗВ($B$3:$C$3;B10:C10)
|
≤
|
60
|
Работа в диалоговом окне «Поиск решения»
Для подготовки к решению задачи оптимизации выполните команду: Сервис
- Поиск решения. На экране появится диалоговое окно Поиск решения (рис.
4). Выполните следующие действия:
1.В поле Установить
целевую ячейку введите адрес $D$5.
2.Для выбора направления
изменения целевой функции установите переключатель в положение Максимальному
значению.
Рис. 4
В поле Изменяя ячейки введите адрес блока ячеек $В$3: $С$3.
.Введите граничные условия и ограничения: щелкните по кнопке Добавить.
На экране появится диалоговое окно Добавление ограничения. Для ввода
граничных условий Х1чХ2 > 0 в поле Ссылка на
ячейку введите левую часть отношения (B3:СЗ), в следующее поле - его
знак (≥), в последнее поле введите правую часть ограничения - 0. Щелкните
по клавише Добавить. На экране появится диалоговое окно Добавление
ограничения. Введите ограничения по ресурсам: D8:D10 ≤ F8:F10
аналогичным образом и щелкните по кнопке ОК. На экране появится
диалоговое окно Поиск решения с введенными ограничениями (рис. 5).
Решение задачи Решение задачи будем производить в диалоговом окне Поиск
решения. В нем выполните следующие действия:
1.Щелкните по кнопке Параметры. Появится диалоговое окно Параметры
поиска решения (рис. 6).
.Установите Максимальное время решения задачи (оставьте
предлагаемое по умолчанию - 100 с), Предельное число итераций (оставьте
предлагаемое по умолчанию - 100).
.Установите флажок Линейная модель.
.Нажмите ОК. Появится диалоговое окно Поиск решения.
.Щелкните по кнопке Выполнить. Появится диалоговое окно Результаты
поиска решения (рис.7).
Рис. 5
Рис. 6
Рис. 7
5. В окне Результаты поиска решения в
поле Тип отчета выделите названия всех трех отчетов: Результаты,
Устойчивость, Пределы. В рабочей книге появятся три новых листа с их
именами.
6. Закройте окно, нажав ОК. На
экране появится исходная таблица с результаты решения задачи (рис. 8): в блоке
ячеек ВЗ:СЗ - значения переменных Х1-Х2 (Х1=13,33,
Х2=13,33), в ячейке D5 - максимальное значение
целевой функции (413,33).
Результаты решения в Excel совпадают с результатами, полученными при
решении задачи графическим методом и симплекс-методом.
Рис. 8
Анализ оптимального решения задачи в Excel
Отчет по результатам
Щелкните мышью по ярлычку Отчет по результатам. На экране появится
лист данного отчета (рис. 9).
В верхней таблице отчета указан номер ячейки - $D$5 (целевой
ячейки), в которой находится значение целевой функции, исходное, равное 0, и
результирующее - максимальное значение целевой функции - 413,33, полученное в
результате решения задачи оптимизации.
В средней
таблице отчета располагаются номера ячеек, в которых находятся значения искомых
переменных Х1 и Х2, исходные
(равные нулю) и результирующие значения (соответственно 13,33 и 13,33), при
которых целевая функция достигает максимального значения.
Рис. 9
В нижней
таблице представлены номера ячеек, в которых записаны значения левых частей
ограничений, полученные после решения задачи оптимизации (требуемое количество
ресурсов каждого вида, необходимое для получения максимального значения целевой
функции). В столбце Разница приводятся данные о разности между
значениями левых частей ограничений, полученных в результате решения задачи
(требуемым количеством ресурсов), и правых частей ограничений (имеющимся
количеством ресурсов), другими словами, данные о количестве неиспользованного
ресурса каждого вида. Если разность равна нулю (ресурс используется полностью),
то в соответствующей ячейке столбца Статус указывается связанное, если
разность не равна нулю (ресурс используется не полностью), в соответствующей
ячейке столбца Статус записано не связанное.
Ниже приводятся номера ячеек, в которых располагаются значения искомых
переменные Х1 и Х2 и их
значения, при которых целевая функция достигает максимального значения.
Отчет по устойчивости
Щелкните мышью по ярлычку Отчет по устойчивости. На экране появится
лист данного отчета (рис. 10).
Рис. 10
В нем приводятся данные о чувствительности целевой ячейки к изменению
ограничений. Отчет состоит из двух таблиц: Изменяемые ячейки и Ограничения.
В таблице Изменяемые ячейки выводятся номера ячеек, в которых
находятся искомые переменные Х1 и Х2 и
их значения, при которых целевая функция достигает максимума.
В столбце Целевой коэффициент приводятся значения коэффициентов
при изменяемых переменных Х1 и Х2 в
выражении целевой функции.
Столбцы Допустимое увеличение и Допустимое уменьшение
характеризуют пределы, в которых могут изменяться эти коэффициенты, без
изменения найденного оптимального решения.
В таблице Ограничения содержится информация об ограничениях,
накладываемых на оптимизируемые переменные.
В столбце Результирующие значения указаны данные о потребности в
ресурсах для оптимального решения.
Данные столбца Теневая цена характеризуют изменение значения
целевой функции (Z) при увеличении на единицу значения соответствующего
ограничения (для ресурсов R1, R2, R3), т.е.
двойственные оценки (Y1 Y2,
Y3)
Столбцы Допустимое увеличение и Допустимое уменьшение характеризуют
пределы, в которых могут изменяться объемы изменяющихся ресурсов, если не
изменять оптимального набора переменных, входящих в оптимальное решение.
Отчет по пределам
Щелкните по ярлычку Отчет по пределам. Появится окно отчета (рис.
11).
Рис. 11
В нем приводится оптимальное значение целевой функции и соответствующие
ему значения переменных Х1 и Х2, а также
нижний и верхний пределы их изменения, при которых не нарушаются ограничения
модели. Например,
Z=
15Х1 + 16Х2 = 15Ч13,33 + 16Ч13,33 = 76,7+
73,3 = 413,3 - оптимальное решение.
Задача 2
Условие задачи
Таблица 2.1
|
Наличие товаров на складах
|
Спрос на товары в магазинах
|
|
|
Ml
|
М2
|
МЗ
|
М4
|
|
|
30
|
10
|
30
|
30
|
|
S1
|
25
|
6
|
10
|
4
|
7
|
|
S2
|
45
|
9
|
12
|
6
|
4
|
|
S3
|
30
|
2
|
3
|
5
|
8
|
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
Пусть Xij - количество товара, отправляемого из склада i
в магазин j, Cij - стоимость перевозки тысячи
единиц товара со склада i в магазин j. Очевидно, что Xij ≥
0 и Cij ≥ 0. В силу ограничений наличие товара на складах
и спрос на него в магазинах величина должны выполняться следующие условия:
1.
X11 + X12 + X13 + X14 =
2521 + X22 + X23 + X24 =
4531 + X32 + X33 + X34
= 30
2.
X11 + X21 + X31
= 3012 + X22 + X32 =
1013 +X23 + X33 = 3014 +X24
+ X34 = 30
Общая стоимость перевозок равна:
Для рассматриваемого примера
Z = 6 ∙ X11 + 10 ∙ X12 + 4 ∙
X13 + 7 ∙ X14 + 9 ∙ X21 + 12 ∙
X22 + 6 ∙ X23 + 4 ∙ X24 + 2 ∙
X31 +3 ∙ X32 + 5 ∙ X33 + 8 ∙
X34
Задача формулируется следующим образом: определить такие неотрицательные
значения переменных Xij , которые удовлетворяют ограничениям
1 и 2 и обращают в минимум целевую функцию Z. В такой постановке
является транспортной задачей линейного программирования. Необходимым и
достаточным условием разрешимости транспортной задачи является условие баланса:
Где
= 
- суммарное количество товара на складах;
= 
- суммарное количество товара, требуемое в магазинах.
В данной задаче
= 100,
Следовательно, задача с балансом.
РЕШЕНИЕ ЗАДАЧИ
Решение транспортной задачи состоит из двух этапов:
1. Определение допустимого решения
(базисного решения).
2. Определение оптимального решения
путем последовательного улучшения допустимого решения методом потенциалов.
Определение допустимого решения методом северо-западного угла
Согласно условию задачи составим таблицу. (тарифы cij располагаются
в нижнем правом углу ячейки)
Рассмотрим маршрут доставки от поставщика S1 к
потребителю M1 (ячейка S1M1).
Запасы поставщика S1 составляют 25 единиц продукции.
Потребность потребителя M1 составляет 30 единиц продукции. От
поставщика S1 к потребителю M1 будем
доставлять min = { 25 , 30 } = 25 единиц продукции. Разместим в ячейку S1M1
значение равное 25
Мы полностью удовлетворили потребность потребителя S1.
Вычеркиваем строку 1 таблицы, т.е исключаем её из дальнейшего рассмотрения.
Таблица 2.2
|
Остатки
|
Mi
|
5
|
|
|
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6 25
|
10
|
4
|
7
|
|
S2 = 45
|
9
|
12
|
6
|
4
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
Рассмотрим маршрут доставки от поставщика S2 к
потребителю M1 (ячейка S2M1).
Запасы поставщика S2 составляют 45 единиц продукции.
Потребность потребителя M1 составляет 5 единиц продукции. От
поставщика S2 к потребителю M1 будем
доставлять min = { 45 , 5 } = 5 единиц продукции.
Разместим в ячейку S2M1 значение равное 5
Мы полностью израсходoвали запасы поставщика M1.
Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Таблица 2.3
|
Остатки
|
Mi
|
0
|
|
|
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6 25
|
10
|
4
|
7
|
|
40
|
S2 = 45
|
9 5
|
12
|
6
|
4
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
Рассмотрим маршрут доставки от поставщика S2 к
потребителю M2 (ячейка S2M2).
Запасы поставщика S2 составляют 40 единиц продукции.
Потребность потребителя M2 составляет 10 единиц продукции. От
поставщика S2 к потребителю M2 будем
доставлять min = { 40 , 10 } = 10 единиц продукции. Разместим в ячейку S2M2
значение равное 10
Мы полностью удовлетворили потребность потребителя M2.
Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Таблица 2.4
|
Остатки
|
Mi
|
0
|
0
|
|
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6 25
|
10
|
4
|
7
|
|
30
|
S2 = 45
|
9 5
|
12 10
|
6
|
4
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
Рассмотрим маршрут доставки от поставщика S2 к
потребителю M3 (ячейка S2M3).
Запасы поставщика S2 составляют 30 единиц продукции. Потребность
потребителя M3 составляет 30 единиц продукции. От поставщика S2
к потребителю M3 будем доставлять min = { 30 , 30 } = 30
единиц продукции.
Разместим в ячейку S2M3 значение равное 30
Мы полностью израсходoвали запасы поставщика S2 и удовлетворили
потребность потребителя M3. Вычеркиваем строку 2 таблицы и
столбец 3, т.е исключаем их из дальнейшего рассмотрения.
Таблица 2.5
|
Остатки
|
Mi
|
0
|
0
|
0
|
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6 25
|
10
|
4
|
7
|
|
0
|
S2 = 45
|
9 5
|
12 10
|
6 30
|
4
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
Рассмотрим маршрут доставки от поставщика S3 к
потребителю M4 (ячейка S3M4).
Запасы поставщика S3 составляют 30 единиц продукции.
Потребность потребителя M3 составляет 30 единиц продукции.
От поставщика S3 к потребителю M4
будем доставлять min = { 30, 30 } = 30 единиц продукции.
Разместим в ячейку S3M4 значение равное 30
Мы полностью удовлетворили потребность потребителя M4 и
израсходовали запасы поставщика S3. Вычеркиваем столбец 4 и
строку 3 таблицы, т.е исключаем его из дальнейшего рассмотрения..
Таблица 2.7
|
Остатки
|
Mi
|
0
|
0
|
0
|
0
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6 25
|
10
|
4
|
7
|
|
0
|
S2 = 45
|
9 5
|
12 10
|
6 30
|
4
|
|
0
|
S3 = 30
|
2 0
|
3
|
5
|
8 30
|
Заполненные нами ячейки будем называть базисными, остальные - свободными.
Для решения задачи методом потенциалов, количество базисных ячеек
(задействованных маршрутов) должно равняться m + n - 1, где m -
количество строк в таблице, n - количество столбцов в таблице.
Количество базисных ячеек (задействованных маршрутов) равно 6, что и
требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и
удовлетворили все потребности потребителей.
Z
= 6 * 25 + 5 * 9 + 10 * 12 + 30 * 6 + 30 * 8 = 735 ден. ед.
Общие затраты на доставку всей продукции, для начального решения ,
составляют 735 ден. ед.
ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.
Каждой строке Si ставим в соответствие некоторое число - ui,
называемое потенциалом поставщика.
Каждому столбцу Mj ставим в соответствие некоторое число - vj,
называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов
поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки SiMj)
Поскольку, число базисных клеток - 6, а общее количество потенциалов
равно 7, то для однозначного определения потенциалов, значение одного из них
можно выбрать произвольно.
Примем v1 = 0.
V1 + u1 = c11 v1
+ u1 = 6 u1 = 6 - 0 = 6
V1 + u2 = c21 v1
+ u2 =9 u2 = 9 - 0 = 9
V2 + u2 = c22 v2
+ u2 = 12 v2 = 12 - 9 = 3
V3 + u2 = c23 v3
+ u2 = 6 v3 = 6 - 9 = -3
V1 + u3 = c31 v1
+ u3 = 2 u3 = 2 - 0 = 2
V4 + u3 = c34 v4
+ u3 = 8 v4 = 8 - 2 = 6
Найдем оценки свободных ячеек следующим образом (в таблице они
располагаются в нижнем левом углу ячейки):
Таблица 2.8
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
Ui
|
|
S1 =25
|
4
|
5
|
6
|
7
|
U1=6
|
|
S2 = 45
|
5
|
6
|
9
|
2
|
U2=9
|
|
S3 = 30
|
1
|
5
|
4
|
3
|
U3=-2
|
|
Vj
|
V1=0
|
V2=3
|
V3=-3
|
V4=6
|
|
G12 = c12 - ( u1 + v2
) =
10 - ( 6 + 3 ) = 1
G13 = c13 - ( u1 + v3
) =
4 - ( 6 + (-3) ) = 1
G14 = c14 - ( u1 + v4
) = 7 - (
6 + 6 ) = -5
G24 = c24 - ( u2 + v4
) = 4 - (
9 + 6 ) = -11
G31 = c31 - ( u3 + v2
) = 3 - (
2 + 3 ) = -2
G32 = c32 - ( u3 + v3
) =
5 - ( 2 + (-3)) = 6
Среди оценок свободных ячеек есть отрицательные, следовательно решение не
является оптимальным.
Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные
оценки, остановим свой выбор на ячейке S1M4 (14=-5).
Построим цикл для выбранной ячейки S1M4:
Среди ячеек цикла S1M4 , S1M1
, S3M1 ,S3M4 номера которых четные,
найдем ячейку, обладающую найменьшим значением.= { 25, 30} = 25 В данном случае
это ячейка S1M1.
Другими словами, из маршрутов доставки продукции, номера которых нечетные
в данном цикле, выберем маршрут от поставщика S1 к потребителю M1,
по которому доставляется меньше всего (25) единиц продукции. Данный маршрут мы
исключим из схемы доставки продукции.
От ячеек цикла с четными номерами отнимает 25. К ячейкам с нечетными
номерами прибавляем 25.
Таблица 2.9
|
Остатки
|
Mi
|
0
|
0
|
0
|
0
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6 25-25
|
10
|
4
|
7 +25
|
|
0
|
S2 = 45
|
9 5
|
12 10
|
6 30
|
4
|
|
0
|
S3 = 30
|
2 0+25
|
3
|
5
|
8 30-25
|
Таблица 2.10
|
Остатки
|
Mi
|
0
|
0
|
0
|
0
|
|
|
Склады
|
Магазины
|
|
Si
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
0
|
S1 =25
|
6
|
10
|
4
|
7 25
|
|
0
|
S2 = 45
|
9 5
|
6 30
|
4
|
|
0
|
S3 = 30
|
2 25
|
3
|
5
|
8 5
|
Общие затраты на доставку всей продукции, для данного решения,
составляют:= 5* 9 + 2 * 25 + 12 * 10 + 6 * 30 + 7 * 25+5*8 = 610 ден. ед.
Если оценки всех свободных ячеек (незадействованных маршрутов)
неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.
Каждой строке Si ставим в соответствие некоторое число - ui,
называемое потенциалом поставщика.
Каждому столбцу Mj ставим в соответствие некоторое число - vj,
называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов
поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки SiMj)
Поскольку, число базисных клеток - 6, а общее количество потенциалов
равно 7, то для однозначного определения потенциалов, значение одного из них
можно выбрать произвольно.
Примем u2 = 0
v1 + u2 = c21 v1
+ u2 = 9
v1 = 9 - 0 = 9
v2 + u2 = c22
v2 + u2 = 12 v2 = 12 - 0 = 12
v3 + u2 = c23
v3 + u2 = 6 v3 = 6 - 0 = 6
v1 + u3 = c31
v1 + u3 = 2 u3 = 2 - 9 = -7
v4 + u3 = c34
v4 + u3 = 8 v4 = 8 - (-7) = 15
v4 + u1 = c14 v4
+ u1
= 7 u1 = 7 - 15 = -8
Найдем оценки свободных ячеек следующим образом (в таблице они
располагаются в нижнем левом углу ячейки):
Таблица 2.11
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
Ui
|
|
S1 =25
|
6
|
10
|
4
|
7
|
U1=-8
|
|
S2 = 45
|
9
|
12
|
6
|
4
|
U2=0
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
U3=-7
|
|
Vj
|
V1=9
|
V2=12
|
V3=6
|
V4=15
|
|
G11 = c11 - ( u1 + v1
) =
6 - ( -8 + 9 ) = 5
G12 = c12 - ( u1 + v2
) = 10 -
( -8 + 12) = 6
G13 = c13 - ( u1 + v3
) = 4 - (
-8 + 6 ) = 6
G24 = c24 - ( u2 + v4
) = 4 - (
0 + 15 ) = -11
G32 = c32 - ( u3 + v2
) = 3 - (
-7 + 12 ) = -2
G33 = c33 - ( u3 + v3
) = 5 - (
-7 + 6 ) = 6
Среди оценок свободных ячеек есть отрицательные, следовательно решение не
является оптимальным. Из свободных ячеек (незадействованных маршрутов), имеющих
отрицательные оценки остановим свой выбор на ячейке S2M4 (G24=-11)
Построим цикл для выбранной ячейки S2M4
Ячейки образующие цикл для свободной ячейки S2M4:2M4,
S2M1, S3M1, S3M4
Пусть ячейка S2M2 , для которой мы строили цикл,
имеет порядковый номер один.
Среди ячеек цикла S2M1,S3M4
номера которых четные, найдем ячейку, обладающую наименьшим значением= {5,5} =
5
В данном случае, таких ячеек две. Остановим выбор на ячейке S2M1
Другими словами, из маршрутов доставки продукции, номера которых нечетные
в данном цикле, выберем маршрут от поставщика S2 к потребителю M1
, по которому доставляется меньше всего (5) единиц продукции. Данный
маршрут мы исключим из схемы доставки продукции.
От ячеек цикла с четными номерами отнимаем 5. К ячейкам с нечетными
номерами прибавляем 5.
Данные преобразования не изменяет баланс между поставщиками и
потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат
необходимое им количество продукции.
Таблица 2.12
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6
|
10
|
4
|
7 25
|
|
S2 = 45
|
9 5-5
|
12 10
|
6 30
|
4 +5
|
|
S3 = 30
|
2 25+5
|
3
|
5
|
8 5-5
|
Таблица 2.13
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6
|
10
|
4
|
7 25
|
|
S2 = 45
|
9
|
12 10
|
6 30
|
4 5
|
|
S3 = 30
|
2 30
|
3
|
5
|
8
|
Z=2*30+12*10+6*30+7*25+4*5=555 ден.ед.
ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.
Каждой строке Si ставим в соответствие некоторое число - ui,
называемое потенциалом поставщика.
Каждому столбцу Mj ставим в соответствие некоторое число - vj,
называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов
поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки SiMj)
Поскольку, число базисных клеток - 6, а общее количество потенциалов
равно 7, то для однозначного определения потенциалов, значение одного из них
можно выбрать произвольно.
Примем v4 = 0
V4 + u1 = c14 v4
+ u1 = 7 u1 = 7 - 0 = 7
V4 + u2 = c24 v4
+ u2 = 4 u2 = 4 - 0 = 4
V4 + u3 = c34 v4
+ u3 = 8 u3 = 8 - 0 = 8
V2 + u2 = c22 v2
+ u2 = 12 v2 = 12 - 4 = 8
V3 + u2 = c23 v3
+ u2 = 6 v3 = 6 - 4 = 2
V1 + u3 = c31 v1 +
u3 = 2
v1 = 2 - 8 = -6
Найдем оценки свободных ячеек следующим образом (в таблице они
располагаются в нижнем левом углу ячейки):
Таблица 2.14
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
Ui
|
|
S1 =25
|
6
|
10
|
4
|
7
|
U1=7
|
|
S2 = 45
|
9
|
12
|
6
|
4
|
U2=4
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
U3=8
|
|
Vj
|
V1=-6
|
V2=8
|
V3=2
|
V4=-0
|
|
G11 = c11 - ( u1 + v1
) =
6 - ( 7 + (-6) ) = 5
G12 = c12 - ( u1 + v2
) = 10 -
( 7 + 8) = -5
G13 = c13 - ( u1 + v3
) = 4 - (
7 + 2 ) = -5
G21 = c21 - ( u2 + v1
) = 9 - (
4 + (-6) ) = 11
G32 = c32 - ( u3 + v2
) = 3 - (
8 + 8 ) = -13
G33 = c33 - ( u3 + v3
) = 5 - (
8 + 2 ) = -5
Оценка свободной ячейки S1M3 (незадействованного
маршрута) отрицательная (G13 = -5), следовательно решение не
является оптимальным.
Построим цикл для выбранной ячейки S1M3 :
Ячейки образующие цикл для свободной ячейки S1M3: S1M3,
S1M4, S2M4, S2M3
Пусть ячейка S1M3 , для которой мы строили цикл,
имеет порядковый номер один.
Среди ячеек цикла S1M4, S2M3
, номера которых четные, найдем ячейку, обладающую наименьшим значением.=
{25,30} = 25
В данном случае, это ячейка S1M4.
Другими словами, из маршрута доставки продукции, номера которых нечетные
в данном цикле, выберем маршрут от поставщика S1 к потребителю M4,
по которому доставляется меньше всего (25) единиц продукции. Данный маршрут мы
исключаем из схемы доставки продукции.
От ячеек цикла с четными номерами отнимаем 25. К ячейкам с нечетными
номерами прибавляем 25.
Таблица 2.15
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6
|
10
|
4 +25
|
7 25-25
|
|
S2 = 45
|
9
|
12 10
|
6 30-25
|
4 5+25
|
|
S3 = 30
|
2 30
|
3
|
5
|
8
|
Таблица 2.16
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6
|
10
|
4 25
|
7
|
|
S2 = 45
|
9
|
12 10
|
6 5
|
4 30
|
|
S3 = 30
|
2 30
|
3
|
5
|
8
|
Z= 2*30+12*10+4*25+6*5+4*30=430 ден.ед.
ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.
Каждой строке Si ставим в соответствие некоторое число - ui,
называемое потенциалом поставщика.
Каждому столбцу Mj ставим в соответствие некоторое число - vj,
называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов
поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки SiMj)
Поскольку, число базисных клеток - 5, а общее количество потенциалов
равно 7, то для однозначного определения потенциалов, значение одного из них
можно выбрать произвольно.
Примем u2 = 0
V2 + u2 = c22 v2
+ u2 = 12
v1 = 12 - 0 = 12
V3 + u2 = c23 v3
+ u2 = 6 v3 = 6 - 0 = 6
v4 + u2 = c24 v4
+ u2 = 4 v4 = 4 - 0 = 4
v4 + u3 = c34 v4
+ u3 = 8 u3 = 8 - 4 = 4
v3 + u1 = c13 v3
+ u1 = 4 u1 = 4 - 6 = -2
v1 + u3 = c31 v1+
u3 = 2 v1
= 2 - 4 = -2
Таблица 2.17
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
Ui
|
|
S1 =25
|
6
|
10
|
4
|
7
|
U1=-2
|
|
S2 = 45
|
9
|
12
|
6
|
4
|
U2=0
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
U3=-4
|
|
Vj
|
V1=-2
|
V2=12
|
V3=6
|
V4=4
|
|
G11 = c11 - ( u1 + v1
) =
6 - ( -2 + (-2) ) = 10
G12 = c12 - ( u1 + v2
) = 10 -
( -2 + 12) = 0
G14 = c14 - ( u1 + v4
) = 7 - (
-2 + 4 ) = 5
G21 = c21 - ( u2 + v1
) = 9 - (
0 + (-2)) = 11
G32 = c32 - ( u3 + v2
) = 3 - (
4 + 12 ) = -13
G33 = c33 - ( u3 + v3
) = 3 - (
4 + 6 ) = -5
Оценка свободной ячейки S3M2 (незадействованного
маршрута) отрицательная (G32 = -13), следовательно решение не
является оптимальным.
Построим цикл для выбранной ячейки S3M2 :
Ячейки образующие цикл для свободной ячейки S3M2: 3M2,
S3M4, S2M4, S2M2
Пусть ячейка S3M2 , для которой мы строили цикл,
имеет порядковый номер один.
Среди ячеек цикла S3M4, S2M2
, номера которых четные, найдем ячейку, обладающую наименьшим значением.=
{0,10} = 0
В данном случае, это ячейка S3M4.
Другими словами, из маршрута доставки продукции, номера которых нечетные
в данном цикле, выберем маршрут от поставщика S3 к потребителю M4,
по которому доставляется меньше всего (0) единиц продукции. Данный маршрут мы
исключаем из схемы доставки продукции.
От ячеек цикла с четными номерами отнимаем 0. К ячейкам с нечетными
номерами прибавляем 0.
Таблица 2.15
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6
|
10
|
4 25
|
7
|
|
S2 = 45
|
9
|
12 10-0
|
6 5
|
4 30+0
|
|
S3 = 30
|
2 30
|
3 +0
|
5
|
8 0-0
|
Таблица 2.16
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6
|
10
|
4 25
|
7
|
|
S2 = 45
|
9
|
12 10
|
6 5
|
4 30
|
|
S3 = 30
|
2 30
|
3
|
5
|
8
|
Z= 2*30+12*10+4*25+6*5+4*30=430 ден.ед.
ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.
Каждой строке Si ставим в соответствие некоторое число - ui,
называемое потенциалом поставщика. Каждому столбцу Mj ставим в
соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов
поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки SiMj)
Поскольку, число базисных клеток - 5, а общее количество потенциалов
равно 7, то для однозначного определения потенциалов, значение одного из них
можно выбрать произвольно.
Примем u2 = 0 V2 + u2 = c22
v2 + u2 = 12 v2 = 12 - 0 =
12
V3 + u2 = c23 v3
+ u2 = 6 v3 = 6 - 0 = 6
v4 + u2 = c24 v4
+ u2 = 4 v4 = 4 - 0 = 4
v2 + u3 = c32 v2
+ u3 = 3 u3 = 3 - 12 = -9
v3 + u1 = c13 v3
+ u1 = 4 u1 = 4 - 6 = -2
v1 + u3 = c31 v1+
u3 = 2 v1
= 2 - (-9)= 11
Таблица 2.17
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
Ui
|
|
S1 =25
|
6
|
10
|
4
|
7
|
U1=-2
|
|
S2 = 45
|
9
|
12
|
6
|
4
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
U3=- -9
|
|
Vj
|
V1=11
|
V2=12
|
V3=6
|
V4=4
|
|
G11 = c11 - ( u1 + v1
) =
6 - ( -2 + 11 ) = -3
G12 = c12 - ( u1 + v2
) = 10 -
( -2 + 12) = 0
G14 = c14 - ( u1 + v4
) = 7 - (
-2 + 4 ) = 5
G21 = c21 - ( u2 + v1
) = 9 - (
0 + 11) = -2
G33 = c33 - ( u3 + v3
) = 5 - (
-9 + 6 ) = 8
G34 = c34 - ( u3 + v3
) = 8 - (
-9 + 4 ) = 13
Оценка свободной ячейки S1M1 (незадействованного
маршрута) отрицательная (G11 = -3), следовательно решение не
является оптимальным.
Построим цикл для выбранной ячейки S1M1 :
Ячейки образующие цикл для свободной ячейки S1M1:
S1M1, S1M3, S2M3,
S2M2, S3M2, S3M1
Пусть ячейка S1M1 , для которой мы строили цикл,
имеет порядковый номер один. Среди ячеек цикла S1M3, S2M2
, S3M1, номера которых четные, найдем ячейку, обладающую
наименьшим значением. Min = {25,10,30} = 10 В данном случае, это ячейка S2M2.
Другими словами, из маршрута доставки продукции, номера которых нечетные в
данном цикле, выберем маршрут от поставщика S2 к потребителю M2,
по которому доставляется меньше всего (10) единиц продукции. Данный маршрут мы
исключаем из схемы доставки продукции. От ячеек цикла с четными номерами
отнимаем 10. К ячейкам с нечетными номерами прибавляем 10.
Таблица 2.15
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6 +10
|
10
|
4 25-10
|
7
|
|
S2 = 45
|
9
|
12 10-10
|
6 5+10
|
4 30
|
|
S3 = 30
|
2 30-10
|
3 0+10
|
5
|
8
|
Таблица 2.16
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
|
S1 =25
|
6 10
|
10
|
4 15
|
7
|
|
S2 = 45
|
9
|
12
|
6 15
|
4 30
|
|
S3 = 30
|
2 20
|
3 10
|
5
|
8
|
Z= 6*10+2*20+3*10+4*15+6*15+4*30=400 ден.ед.
ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.
Каждой строке Si ставим в соответствие некоторое число - ui,
называемое потенциалом поставщика.
Каждому столбцу Mj ставим в соответствие некоторое число - vj,
называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов
поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки SiMj)
Поскольку, число базисных клеток - 5, а общее количество потенциалов
равно 7, то для однозначного определения потенциалов, значение одного из них
можно выбрать произвольно.
Примем v3 = 0
V3 + u1 = c13 v3
+ u1 = 4
u1 = 4 - 0 = 4
V3 + u2 = c23 v3
+ u2 = 6 u2 = 6 - 0 = 6
v4 + u2 = c24 v4
+ u2 = 4 v4 = 4 - 6 = -2
v1 + u1 = c11 v1
+ u1 = 6 v1 = 6 - 4 = 2
v1 + u3 = c31 v1
+ u3 = 2 u3= 2 - 2 = 0
v2 + u3 = c32 v2+
u3 = 3 v2
= 3 - 0= 3
Таблица 2.17
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 30
|
М4 = 30
|
Ui
|
|
S1 =25
|
6
|
10
|
4
|
7
|
U1=4
|
|
S2 = 45
|
9
|
12
|
6
|
4
|
U2=6
|
|
S3 = 30
|
2
|
3
|
5
|
8
|
U3=- 0
|
|
Vj
|
V1=2
|
V2=3
|
V3=0
|
V4= -2
|
|
G12 = c11 - ( u1 + v2) = 10- ( 4 + 3 ) = 3
G14 = c14 - ( u1 + v4
) = 7 - (
4 + (-2)) = 5
G21 = c21 - ( u2 + v1
) = 9 - (
6 + 2 ) = 1
G22 = c22 - ( u2 + v2
) = 12 -
( 6 + 3) = 3
G33 = c33 - ( u3 + v3
) = 5 - (
0 + 0 ) = 5
G34 = c34 - ( u3 + v3
) = 8 - (
0 + (-2) ) = 10
Все оценки свободных ячеек положительные, следовательно, найдено
оптимальное решение.
Таблица 2.18
|
Склады
|
Магазины
|
|
М1= 30
|
М2= 10
|
М3 = 40
|
М4 = 30
|
|
S1 =25
|
6 10
|
10
|
4 15
|
7
|
|
S2 = 45
|
9
|
12
|
6 15
|
4 30
|
|
S3 = 40
|
2 20
|
3 10
|
5
|
8
|
Z = 6*10+2*20+3*10+6*15+4*15+4*30=400 ден.ед.
РЕШЕНИЕ ЗАДАЧИ В EXCEL
Для решения задачи составим электронную таблицу, отражающую
математическую модель задачи. Электронная модель (исходное состояние),
представлена в режиме вычислений - на рис. 1, в режиме отображения формул - на
рис. 2 .
|
Исходные данные
|
|
Спрос на товары в магазинах
|
|
Наличие товаров на складах
|
М1
|
М2
|
М3
|
М4
|
|
30
|
10
|
30
|
30
|
|
Стоимость перевозки ед.груза
|
|
S1
|
25
|
6
|
10
|
4
|
7
|
|
S2
|
45
|
9
|
12
|
6
|
4
|
|
S3
|
30
|
2
|
3
|
5
|
8
|
|
Решение
|
|
|
|
|
|
|
|
|
Наличие товаров на складах
|
М1
|
М2
|
М3
|
М4
|
|
0
|
0
|
0
|
0
|
|
S1
|
0
|
0
|
0
|
0
|
0
|
|
S2
|
0
|
0
|
0
|
0
|
0
|
|
S3
|
0
|
0
|
0
|
0
|
0
|
|
стоимость перевозки
|
|
М1
|
М2
|
М3
|
М4
|
|
Общая
|
0
|
0
|
0
|
0
|
0
|
Рис.1
Рис.2
Работа в диалоговом окне «Поиск решения»
Выберите команду: Сервис - Поиск решения. На экране появится диалоговое
окно Поиск решения. Выполните следующие действия:
1.В поле
Установить целевую ячейку введите адрес $Ј$17.
2.Выберите
направление изменения целевой функции: установите переключатель в положение
Минимальному значению.
3.В поле Изменяя
ячейки введите адрес блока ячеек $С$13: $f$15.
4.Введите
ограничения: нажмите кнопку Добавить. На экране появится диалоговое окно
Добавление ограничения. Введите в левое поле левую часть ограничения $5$ 13
.$5$ 15, выберите из раскрывающегося списка знак ограничения =, введите в
правое поле правую часть ограничения $5$6:$5$8; щелкните по клавише Добавить -
на экране опять появится диалоговое окно Добавление ограничения. Введите второе
ограничение $C$12:$.F$12 = $С$4:$7л$4 и граничные условия C$13:.F$15 > 0
аналогичным образом; нажмите кнопку ОК. На экране появится диалоговое окно
Поиск решения с введенными ограничениями (рис. 3)
Рис. 3
Решение задачи
Для решения задачи выполните следующие действия:
1.Щелкните по
кнопке Параметры. Появится диалоговое окно Параметры поиска решения.
2.Оставьте
без изменения Максимальное время решения задачи (100 с) и
Предельное число итераций (100).
3.Установите
флажок Линейная модель.
4.Нажмите
кнопку ОК. Появится диалоговое окно Поиск решения.
5.Щелкните по
кнопке Выполнить. Появится диалоговое окно Результаты поиска решения.
Решение найдено.
6.В окне Результаты поиска решения в поле Тип отчета
выделите
названия всех трех отчетов: Результаты, Устойчивость, Пределы
Появятся три новых листа с именами всех отчетов. Они потребуются
для анализа оптимального решения задачи.
7.Нажмите кнопку ОК. На экране появится исходная таблица
(рис.4), где в блоке ячеек C13:F15 находятся значения искомых пе-
ременных: XI - Х5, а в ячейке В14 значение целевой функции.
Рис.4
Анализ оптимального решения в Excel
Для анализа оптимального решения задачи воспользуемся отчетами:
Результаты, Устойчивость, Пределы.
Отчет по результатам
Щелкните мышью по ярлычку Отчет по результатам. На
экране появится лист данного отчета (рис. 5)
|
Microsoft Excel 12.0 Отчет по результатам
|
|
|
Рабочий лист: [Транспортная задача.xlsx]Лист1
|
|
|
Отчет создан: 31.05.2012 22:58:09
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Целевая ячейка (Минимум)
|
|
|
|
Ячейка
|
Имя
|
Исходное значение
|
Результат
|
|
|
$B$17
|
Общая
|
0
|
400
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Изменяемые ячейки
|
|
|
|
Ячейка
|
Имя
|
Исходное значение
|
Результат
|
|
|
$C$13
|
S1 М1
|
0
|
10
|
|
|
$D$13
|
S1 М2
|
0
|
0
|
|
|
$E$13
|
S1 М3
|
0
|
15
|
|
|
$F$13
|
S1 М4
|
0
|
0
|
|
|
$C$14
|
S2 М1
|
0
|
0
|
|
|
$D$14
|
S2 М2
|
0
|
0
|
|
|
$E$14
|
S2 М3
|
0
|
15
|
|
|
$F$14
|
S2 М4
|
0
|
30
|
|
|
$C$15
|
S3 М1
|
0
|
20
|
|
|
$D$15
|
S3 М2
|
0
|
10
|
|
|
$E$15
|
S3 М3
|
0
|
0
|
|
|
$F$15
|
S3 М4
|
0
|
0
|
|
|
|
|
|
|
|
|
|
Рис.5
|
Ограничения
|
|
|
|
|
|
|
Ячейка
|
Имя
|
Значение
|
Формула
|
Статус
|
Разница
|
|
$B$13
|
S1
|
25
|
$B$13=$B$6
|
не связан.
|
0
|
|
$B$14
|
S2
|
45
|
$B$14=$B$7
|
не связан.
|
0
|
|
$B$15
|
S3
|
30
|
$B$15=$B$8
|
не связан.
|
0
|
|
$C$4
|
М1
|
30
|
$C$4=$C$12
|
не связан.
|
0
|
|
$D$4
|
М2
|
10
|
$D$4=$D$12
|
не связан.
|
0
|
|
$E$4
|
М3
|
30
|
не связан.
|
0
|
|
$F$4
|
М4
|
30
|
$F$4=$F$12
|
не связан.
|
0
|
|
$C$13
|
S1 М1
|
10
|
$C$13>=0
|
не связан.
|
10
|
|
$D$13
|
S1 М2
|
0
|
$D$13>=0
|
связанное
|
0
|
|
$E$13
|
S1 М3
|
15
|
$E$13>=0
|
не связан.
|
15
|
|
$F$13
|
S1 М4
|
0
|
$F$13>=0
|
связанное
|
0
|
|
$C$14
|
S2 М1
|
0
|
$C$14>=0
|
связанное
|
0
|
|
$D$14
|
S2 М2
|
0
|
$D$14>=0
|
связанное
|
0
|
|
$E$14
|
S2 М3
|
15
|
$E$14>=0
|
не связан.
|
15
|
|
$F$14
|
S2 М4
|
30
|
$F$14>=0
|
не связан.
|
30
|
|
$C$15
|
S3 М1
|
20
|
$C$15>=0
|
не связан.
|
20
|
|
$D$15
|
S3 М2
|
10
|
$D$15>=0
|
не связан.
|
10
|
|
$E$15
|
S3 М3
|
0
|
$E$15>=0
|
связанное
|
0
|
|
$F$15
|
S3 М4
|
0
|
$F$15>=0
|
связанное
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.6
В верхней таблице отчета указан номер целевой ячейки - $B$17, в которой
находится значение целевой функции, ее исходное значение, равное 0, и
результирующее - минимальное значение целевой функции, равное 5240, которое
получили в результате решения задачи.
В средней таблице отчета представлены номера ячеек, в которых
располагаются искомые переменные, их исходные значения, равные единице, и
результирующие значения, при которых целевая функция достигает максимального
значения.
В нижней таблице представлены номера ячеек, в которых записаны левые
части ограничений, их значения, полученные после решения задачи оптимизации.
Для каждого ограничения в столбце Разница приводится информация о
разности между значениями левых частей ограничений, полученных в результате
решения задачи, и правых частей ограничений. Если разность равна нулю, то в
соответствующей ячейке столбца Статус указывается связанное, если
разность не равна нулю, в соответствующей ячейке столбца Статус записано
не связанное
Отчет по пределам
Щелкните по ярлычку Отчет по пределам Появится окно
отчета (рис 6). В нем приводятся значение целевой функции и оптимальные
значения каждой изменяемой ячейки, вместе с нижними и верхними пределами ее
изменения, при которых не нарушаются ограничения модели
|
Microsoft Excel 12.0 Отчет по пределам
|
|
|
|
|
|
Рабочий лист: [Транспортная задача.xlsx]Отчет по пределам 1
|
|
|
Отчет создан: 31.05.2012 22:58:10
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Целевое
|
|
|
|
|
|
|
|
|
Ячейка
|
Имя
|
Значение
|
|
|
|
|
|
|
|
$B$17
|
Общая
|
400
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Изменяемое
|
|
|
Нижний
|
Целевой
|
|
Верхний
|
Целевой
|
|
Ячейка
|
Имя
|
Значение
|
|
предел
|
результат
|
|
предел
|
результат
|
|
$C$13
|
S1 М1
|
10
|
|
10
|
400
|
|
10
|
400
|
|
$D$13
|
S1 М2
|
0
|
|
0
|
400
|
|
0
|
400
|
|
$E$13
|
S1 М3
|
15
|
|
15
|
400
|
|
15
|
400
|
|
$F$13
|
S1 М4
|
0
|
|
0
|
400
|
|
0
|
400
|
|
$C$14
|
S2 М1
|
0
|
|
0
|
400
|
|
0
|
400
|
|
$D$14
|
S2 М2
|
0
|
|
0
|
400
|
|
0
|
400
|
|
$E$14
|
S2 М3
|
15
|
|
15
|
400
|
|
15
|
400
|
|
$F$14
|
S2 М4
|
30
|
|
30
|
400
|
|
30
|
400
|
|
$C$15
|
S3 М1
|
20
|
|
20
|
400
|
|
20
|
400
|
|
$D$15
|
S3 М2
|
10
|
|
10
|
400
|
|
10
|
400
|
|
$E$15
|
S3 М3
|
0
|
|
0
|
400
|
|
0
|
400
|
|
$F$15
|
S3 М4
|
0
|
|
0
|
400
|
|
0
|
400
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.6
Отчет по устойчивости Щелкните мышью по ярлычку Отчет по устойчивости.
На экране появится лист данного отчета (рис. 7).
|
Microsoft Excel 12.0 Отчет по устойчивости
|
|
|
|
Рабочий лист: [Транспортная задача.xlsx]Лист1
|
|
|
|
Отчет создан: 31.05.2012 22:58:09
|
|
|
|
|
Изменяемые ячейки
|
|
|
|
|
|
|
|
Результ.
|
Нормир.
|
Целевой
|
Допустимое
|
Допустимое
|
|
Ячейка
|
Имя
|
значение
|
стоимость
|
Коэффициент
|
Увеличение
|
Уменьшение
|
|
$C$13
|
S1 М1
|
10
|
0
|
6
|
1
|
5
|
|
$D$13
|
S1 М2
|
0
|
3
|
10
|
1E+30
|
3
|
|
$E$13
|
S1 М3
|
15
|
0
|
4
|
5
|
1
|
|
$F$13
|
S1 М4
|
0
|
5
|
7
|
1E+30
|
5
|
|
$C$14
|
S2 М1
|
0
|
1
|
9
|
1E+30
|
1
|
|
$D$14
|
S2 М2
|
0
|
3
|
12
|
1E+30
|
3
|
|
$E$14
|
S2 М3
|
15
|
0
|
6
|
1
|
5
|
|
$F$14
|
S2 М4
|
30
|
0
|
4
|
5
|
1E+30
|
|
$C$15
|
S3 М1
|
20
|
0
|
2
|
5
|
3
|
|
$D$15
|
S3 М2
|
10
|
0
|
3
|
3
|
1E+30
|
|
$E$15
|
S3 М3
|
0
|
5
|
5
|
1E+30
|
5
|
|
$F$15
|
S3 М4
|
0
|
10
|
8
|
1E+30
|
10
|
|
|
|
|
|
|
|
|
|
|
|
Результ.
|
Теневая
|
Ограничение
|
Допустимое
|
Допустимое
|
|
Ячейка
|
Имя
|
значение
|
Цена
|
Правая часть
|
Увеличение
|
Уменьшение
|
|
$B$13
|
S1
|
25
|
2
|
25
|
0
|
15
|
|
$B$14
|
S2
|
45
|
4
|
45
|
0
|
30
|
|
$B$15
|
S3
|
30
|
-2
|
30
|
0
|
15
|
|
$C$4
|
М1
|
30
|
-4
|
0
|
0
|
15
|
|
$D$4
|
М2
|
10
|
-5
|
0
|
0
|
15
|
М3
|
30
|
-2
|
0
|
0
|
30
|
|
$F$4
|
М4
|
30
|
0
|
0
|
1E+30
|
0
|
|
|
|
|
|
|
|
|
|
|
|
Рис.7
В нем приводится информация о чувствительности целевой ячейки к изменению
ограничений. Отчет состоит из двух таблиц: Изменяемые ячейки и
Ограничения. В таблице Изменяемые ячейки на отдельной
строке выводятся номера ячеек и результирующие значения изменяемых переменных,
находящихся в них. Данные столбца Нормированная стоимость характеризуют
изменение значения целевой функции при увеличении на единицу значения
соответствующей изменяемой переменной, т. е двойственные оценки. В столбце
Целевой коэффициент приводятся значения коэффициентов при
основных и вспомогательных переменных в выражении целевой функции. Если в окне
Параметры поиска решения установлен флажок Линейная модель,
в отчет включаются данные об изменении целевой функции при увеличении на
единицу значения изменяемой переменной.
Столбцы Допустимое увеличение и Допустимое уменьшение
характеризуют пределы, в которых может изменяться целевой коэффициент, не
изменяя оптимального набора переменных, входящих в оптимальное условие. В
таблице Ограничения содержится информация о значениях левых частей
ограничений, полученных в результате решения задачи, и правых частей
ограничений. Данные столбца Теневая цена характеризуют изменение
значения целевой функции при увеличении на единицу значения соответствующего
ограничения, т.е двойственные оценки.
Столбцы Допустимое увеличение и Допустимое уменьшение
характеризуют пределы, в которых могут изменяться ограничения, если не
изменять оптимального набора переменных, входящих в оптимальное условие.
Задача 3
Задание.
Найти кратчайшие расстояния от вершины х1, используя метод
Дейкстры.
Задача о кратчайшем пути формулируется следующим образом:
Дан связный взвешенный граф G=(X,U) не имеющий параллельных ребер.
Для любых двух выделенных вершин графа требуется найти кратчайший путь между
ними и указать этот путь.
Метод заключается в присвоении вершинам графа временных меток L(xj),
а затем по определенному правилу заменить их постоянными метками L*(xj).
Постоянные метки - кратчайшие расстояния от заданной вершины (х1)
до всех остальных (хj).
Алгоритм нахождения кратчайших путей графа методом Дейкстры.
· Определить множество вершин графа, смежных с вершиной х1:
S(x1)={xj}
· Для каждой вершины, принадлежащей множеству S(x1)
вычислить новые временные метки L(xj), равные min {Lст(xj),
L*(xj) + Rij}, где Lст(xj)
- старая временная метка вершины xj, L(xj) -
постоянная метка вершины xj, Rij - вес ребра (xi,
xj)
· Из всех имеющихся временных меток выбрать наименьшую и
сделать её постоянной для своей вершины.
· Определить множество вершин графа, смежных с вершиной xi,
которой на предыдущем шаге была присвоена постоянная метка S(x1)={xj}
· Перейти к пункту 2. Процесс повторяется до тех пор, пока все
вершины не будут иметь постоянные метки.
Неориентированных граф задан матрицей весов (таблица 1)
Таблица 1 Исходные данные
|
Х1
|
Х2
|
Х3
|
Х4
|
Х5
|
|
Х1
|
∞
|
4
|
∞
|
∞
|
2
|
|
Х2
|
4
|
∞
|
3
|
∞
|
4
|
|
Х3
|
∞
|
3
|
∞
|
1
|
6
|
|
Х4
|
∞
|
∞
|
1
|
∞
|
∞
|
|
Х5
|
2
|
4
|
6
|
∞
|
∞
|
Предварительно вершине х1 (исходной) требуется
присвоить постоянную метку L*(X1)=0, а всем остальным вершинам
- временные метки, равные ∞: L(X2)=L(X3)=L(X4)=L(X5)=
∞ (Таблица 2.1)
Таблица 2.1
|
0
|
1
|
2
|
3
|
4
|
|
Х1
|
0*
|
|
|
|
|
|
Х2
|
∞
|
|
|
|
|
|
Х3
|
∞
|
|
|
|
|
|
Х4
|
∞
|
|
|
|
|
|
Х5
|
∞
|
|
|
|
|
Шаг 1.
А) определим множество вершин графа, смежных с вершиной х1, не
имеющих еще постоянных меток:
S(x1)={x2,x5} L*(x1)=0
Б) min {Lст(xj),L*(x1)+R1j}
Таблица 3
|
Lст(xj)
|
L*(x1)+Rij
|
|
min{Lст(xj),(L*(x1)+Rij)
|
|
L(x2)= ∞
|
L*(x1)+R12=
|
0+4=4
|
Min{∞;4}=4
|
|
L(x5)= ∞
|
L*(x1)+R15=
|
0+2=2
|
Min{∞;2}=2
|
Таблица 2.2
|
0
|
1
|
2
|
3
|
4
|
|
Х1
|
0*
|
|
|
|
|
|
Х2
|
∞
|
4
|
|
|
|
|
Х3
|
∞
|
∞
|
|
|
|
|
Х4
|
∞
|
∞
|
|
|
|
|
Х5
|
∞
|
2*
|
|
|
|
Шаг 2.
А)определим множество вершин графа, смежных с вершиной х5,
не имеющие еще постоянных меток:
S(x5) = {x2,x3} L*(x5)=2
Б)min {Lст(xj), L*(x5)+Rij}
Таблица 4
|
Lст (xj)
|
L*(x5)+R5j
|
|
min{Lст(xj),L*(x5)+R5j}
|
|
L(x2)= ∞
|
L*(x5)+R52=
|
2+4=6
|
min{∞;6}=6
|
|
L(x3)= ∞
|
L*(x5)+R53=
|
2+6=8
|
min{∞;8}=8
|
Таблица 2.3
|
0
|
1
|
2
|
3
|
4
|
|
Х1
|
0*
|
|
|
|
|
|
Х2
|
∞
|
4
|
6*
|
|
|
|
Х3
|
∞
|
∞
|
8
|
|
|
|
Х4
|
∞
|
∞
|
∞
|
|
|
|
Х5
|
∞
|
2*
|
|
|
|
Шаг 3.
А)определим множество вершин графа, смежных с вершиной х2, не
имеющих еще постоянных меток:
S(x2)={x3}*(x2)=6
Таблица 5
|
Lст (xj)
|
L*(x2)+R2j
|
|
min{Lст(xj),L*(x2)+R2j}
|
|
L(x3)= 8
|
L*(x2)+R23=
|
6+3=9
|
min{8;9}=8
|
|
|
|
|
Таблица 2.4
|
0
|
1
|
2
|
3
|
4
|
|
Х1
|
0*
|
|
|
|
|
|
Х2
|
∞
|
4
|
6*
|
|
|
|
Х3
|
∞
|
∞
|
8
|
8*
|
|
|
Х4
|
∞
|
∞
|
∞
|
∞
|
|
|
Х5
|
∞
|
2*
|
|
|
|
Шаг 4.
А)определим множество вершин графа, смежных с вершиной х3, не
имеющих еще постоянных меток:
S(x3)={x4}*(x3)=8
Таблица 6
|
Lст (xj)
|
L*(x3)+R3j
|
|
min{Lст(xj),L*(x2)+R2j}
|
|
L(x3)=∞
|
L*(x3)+R34=
|
8+1=9
|
min{∞;9}=9
|
Таблица 2.5
|
0
|
1
|
2
|
3
|
4
|
|
Х1
|
0*
|
|
|
|
|
|
Х2
|
∞
|
4
|
6*
|
|
|
|
Х3
|
∞
|
∞
|
8
|
8*
|
|
|
Х4
|
∞
|
∞
|
∞
|
∞
|
9*
|
|
Х5
|
∞
|
2*
|
|
|
|
Нахождение кратчайших путей от вершины х1 до всех
остальных.
)Определим кратчайший путь от вершины х1 до вершины х4
А)L*(x4)=9
Таблица 7
|
L*(x3)=8
|
R34=1
|
L*(x3)=L*(x3)+R34=8+1=9
|
|
|
|
Б)Определим, какая вершина предшествует вершине х3 в
кратчайшем пути.
L*(x3)=8
Таблица 8
|
L*(x2)=6
|
R23=3
|
L*(x3)≠L*(x2)+R23=6+3=9
|
|
L*(x5)=2
|
R53=6
|
L*(x3)=L*(x5)+R53=2+6=8
|
В)Определим, какая вершина предшествует вершине х5 в
кратчайшем пути. L*(x5)=2
Таблица 9
|
L*(x1)=0
|
R15=2
|
L*(x5)=L*(x1)+R15=0+2=2
|
|
L*(x2)=6
|
R25=4
|
L*(x5)≠L*(x2)+R25=6+4=10
|
2)Найдем кратчайший путь от вершины х1 до
вершины х2.
А) Вершина х2 имеет смежные вершины с:
S(x1,x3,x5)
Б)Определим, какая вершина предшествует вершине х2 в
кратчайшем пути.
L*(x2)=6
Таблица 10
|
L*(x1)=0
|
R12=4
|
L*(x2)≠L*(x1)+R12=0+4=4
|
|
L*(x3)=8
|
R32=3
|
L*(x2)≠L*(x3)+R32=8+3=11
|
|
L*(x5)=2
|
R52=4
|
L*(x2)=L*(x5)+R52=2+4=6
|
Задача 4
Двухполюсные транспортные сети
Двухполюсной транспортной сетью S называется взвешенный
ориентированный граф (орграф) без петель с множеством вершин X и множеством
дуг U, для которых выполняются следующие условия:
· Существует только одна вершина, в которую не заходит ни одна дуга. Она
называется входом (истоком) сети;
· Существует только одна вершина, из которой не исходит ни одна
дуга. Она называется выходом (истоком) сети;
· Каждой дуге сети поставлено в соответствие неотрицательное
число c(u), называемое пропускной способностью сети;
Потоком в сети S=(X,U) от входа S до выхода tназывается
неотрицательная вещественная функция φ=(I,j), определенная на множестве дуг сети,
для которой выполняются следующие условия:
· Величина потока по каждой дуге не должна превосходить её пропускной
способности;
· величина потока V, входящего в каждую вершину, за
исключением входа и выхода, равна величине потока, выходящего из этой вершины:
0≤φ(u)≤c(u) Для любой вершины, где
- множество дуг, заходящих в вершину х,
- множество дуг, выходящих из вершины х.
· величина потока по каждой дуге не должна превосходить её пропускной
способности;
· величина потока V, входящего в каждую вершину, за
исключением входа и выхода, равна величине потока, выходящего из этой вершины;
Множество вершин сети S=(X,U) можно разбить на два
непересекающихся подмножества Xp и Xp,
Причем вход S принадлежит подмножеству вершин Хр, а выход t
принадлежит подмножеству вершин Хр.
Подмножества Хр и Хр соединяются между собой дугами,
образующими множество Up.
Величина потока из множества Хр в Хр , протекающего по
дугам Up, не может быть больше суммы пропускных способностей дуг этого
множества.
Разрез представляет собой такое множество дуг Up, исключение
которых отделяет вход S от выхода t сети, и, следовательно, отделяет
множество вершин Хр сети от множества Хр сети таким образом, что
существование потока в таком случае невозможно, т.е. V=0
Пропускной способностью разреза или величиной разреза называется сумма
пропускных способностей входящих в него дуг.
Минимальным разрезом сети называется разрез, имеющий минимальную
величину.
Теорема Форда - Фалкерсона.
Величина каждого потока от входа к выходу не превосходит пропускной
способности минимального разреза, разделяющего вход и выход сети, причем
существует максимальный поток, чья величина равна пропускной способности
минимального разреза.
Определение максимального потока сводится к нахождению допустимой дуги и,
если такая дуга найдена, увеличение вдоль нее потока на максимально возможную
величину ∆φ.
Дуга U, соединяющая вершины xi и xj
сети S является допустимой, если для нее выполняется одно из следующих
условий:
· направление дуги совпадает с направлением потока и значение
потока по этой дуге меньше её пропускной способности: φ(u)≤c(u).
Такие дуги называют увеличивающими или согласованными.
· Направление дуги противоположно направлению потока и по ней
проходит ненулевой поток: φ(u)>0
Такие дуги называют уменьшающими или несогласованными.
Увеличивающей цепью, соединяющей вход и выход, называется простая цепь,
все дуги которой являются допустимыми.
Алгоритм построения максимального потока
1. Задать начальное значение потока равным нулю, если оно не задано.
2. Найти увеличивающую цепь от входа S к выходу t.Если
такой цепи нет, максимальный поток построен:
Далее перейти в конец алгоритма.
В противном случае перейти к пункту 3.
3. Вдоль найденной увеличивающей цепи изменить значение потока на
величину δ: по каждой увеличивающей дуге поток увеличить на ∆(u)=c(u)-φ(u), по каждой уменьшающей дуге уменьшить
на величину ∆(u).
Возврат в пункт 2.
Вариант 1.
Двухполюсная транспортная сеть задана матрицей пропускных способностей
(таблица 1)
Найти максимальное значение потока.
Таблица 1 Исходные данные
|
Х1
|
Х2
|
Х3
|
Х4
|
Х5
|
|
S
|
14
|
0
|
13
|
0
|
0
|
|
Х1
|
0
|
6
|
0
|
0
|
0
|
|
Х2
|
0
|
0
|
0
|
9
|
20
|
|
Х3
|
18
|
5
|
0
|
3
|
0
|
|
Х4
|
0
|
0
|
0
|
16
|
Рис 1.
· Рассмотрим цепь (s,x3,x2,x4 ,t).Б)Вдоль
дуги поток можно увеличить на величину ∆(u)=c(u)-φ(u)
Вдоль дуги (s,x3) ∆(u)=13-0=13
Вдоль дуги (x3,x2) ∆(u)=5-0=5
Вдоль дуги (x2,x4) ∆(u)=9-0=9
Вдоль дуги (x4,t) ∆(u)=16-0=16
В)δ=min{13,5,9,16}=5 →
По каждой увеличивающей дуге поток следует увеличить на 5
· Рассмотрим цепь (s,x1,x2,x4,t).
А)Вдоль дуги поток можно увеличить на величину ∆(u)=c(u)-φ(u)
(s,x1) - допустимая (увеличивающая) дуга, так как направление дуги
совпадает с направлением потока и потом по ней меньше пропускной способности:
0<14 (x1,x2) - допустимая (увеличивающая) дуга,
так как направление дуги совпадает с направлением потока и потом по ней меньше
пропускной способности: 0<6
(x2,x4) - допустимая (увеличивающая) дуга,
так как направление дуги совпадает с направлением потока и потом по ней меньше
пропускной способности: 5<9
(x4,t) - допустимая (увеличивающая) дуга, так как направление дуги
совпадает с направлением потока и потом по ней меньше пропускной способности:
5<16
Б)Вдоль дуги поток можно увеличить на величину ∆(u)=c(u)-φ(u)
Вдоль дуги (S,x1) ∆(u)=14-0=14
Вдоль дуги (x1,x2) ∆(u)=6-0=6
Вдоль дуги (x2,x4) ∆(u)=9-5=4
Вдоль дуги (x4,t) ∆(u)=16-5=11
В)δ=min{14,6,4,11}=4 →
По каждой увеличивающей дуге потом следует увеличить на 4.
· Рассмотрим цепь (s,x1,x2,t).
А) (s,x1) - допустимая (увеличивающая) дуга, так как
направление дуги совпадает с направлением потока и потом по ней меньше
пропускной способности: 4<14
(x1,x2) - допустимая (увеличивающая) дуга, так
как направление дуги совпадает с направлением потока и потом по ней меньше
пропускной способности: 4<6
(x2,t) - допустимая (увеличивающая) дуга, так как направление дуги
совпадает с направлением потока и потом по ней меньше пропускной способности:
0<20
Б)Вдоль дуги поток можно увеличить на величину ∆(u)=c(u)-φ(u)
Вдоль дуги (s,x1) ∆(u)=14-4=10
Вдоль дуги (x1,x2) ∆(u)=6-4=2
Вдоль дуги (x2,t) ∆(u)=20-0=20
Б)δ=min{10,2,20}=2 →
По каждой увеличивающей дуге потом следует увеличить на 2.
· Рассмотрим цепь (s,x3,x4,t).
А) (s,x3) - допустимая (увеличивающая) дуга, так как
направление дуги совпадает с направлением потока и потом по ней меньше
пропускной способности: 5<13
(x3,x4) - допустимая (увеличивающая) дуга,
так как направление дуги совпадает с направлением потока и потом по ней меньше
пропускной способности: 0<3
(x4,t) - допустимая (увеличивающая) дуга, так как направление дуги
совпадает с направлением потока и потом по ней меньше пропускной способности:
9<16
Б)Вдоль дуги поток можно увеличить на величину ∆(u)=c(u)-φ(u)
Вдоль дуги (s,x3) ∆(u)=13-5=8
Вдоль дуги (x3,x4) ∆(u)=3-0=3
Вдоль дуги (x4,t) ∆(u)=16-9=7
Б)δ=min{8,3,7}=3 →
По каждой увеличивающей дуге потом следует увеличить на 3.
Минимальный разрез: (х1,х2),(х3,х2),(х3,x4)
Пропускная способность: 6+5+3=14
Решение задачи в Excel
Для решения задачи составим электронную таблицу, отражающую
математическую модель задачи. Электронная модель (исходное состояние),
представлена в режиме вычислений - на рис. 1, в режиме отображения формул - на
рис. 2 . Начальные значение потоков положены равными нулю.
Рис. 1
Рис. 2
Работа в диалоговом окне “Поиск решения”
Для подготовки к решению задачи оптимизации надо выполнить команду: Сервис
- Поиск решения. На экране появится диалоговое окно Поиск решения (
рис. 3 ). Следует выполнить следующие действия:
Рис. 3
1. В поле Установить целевую ячейку ввести адрес $H$13.
2. Выбрать направление изменения целевой функции: установить
переключатель в положение Максимальному значению.
. В поле Изменяя ячейки ввести адрес блока ячеек $C$13:$G$17
. Ввести ограничения: $C$13:$G$17≤$C$5:$G$9, $C$14:$G$17≥0,
$C$18=$H$14, $D$18=$H$15, $E$18=$H$16, $F$18=$H$17
нажимая до ввода каждого ограничения кнопку Добавить. После ввода всех
ограничений нажать кнопку ОК. На экране появится диалоговое окно Поиск
решения с введенными ограничениями.
. Нажать кнопку Параметры. Появится диалоговое окно Параметры
поиска решения.
. Установить флажок Линейная модель .
. Оставить без изменений остальные установки.
8. Нажать ОК. Появится диалоговое окно Поиск решения.
9. Щелкнуть по кнопке Выполнить. Появится диалоговое окно Результаты
поиска решений.
. Нажать ОК. На экране появится исходная таблица ( рис.
4), где в блоке ячеек C13:G17 находятся значения искомых переменных хij
, а в ячейке H13- значение целевой функции.
Рис. 4
