Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
РЫБИНСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ имени П. А. СОЛОВЬЕВА
Факультет заочного обучения
Кафедра математического и программного обеспечения
электронных вычислительных средст
КОНТРОЛЬНАЯ РАБОТА
по дисциплине «Математические методы анализа экономики»
ВАРИАНТ № 3
Студентка: Степанова Елена Михайловна
Группа: ЗЭВ — 10 (з)
Преподаватель: Барашков В.М.
Оценка________________________________
Подпись
преподавателя _________________________
Дата __________________________________
Рыбинск 2011
ОГЛАВЛЕНИЕ
Задача № 1
Построение задачи, двойственной к исходной задаче. Теоремы двойственностию.
Задача № 2
Решить задачу графическим методом.
z = x1 + 7 x2 → max
при следующих ограничениях:
5 x1 - x2 ≥10
7 x1 +9 x2 ≤63
х1, х2, х3 ≥ 0.
Задача № 3.
Решить задачу симплекс-методом
z = 5x1 + 7x2 + 2x3 → max
3x1 + 3x2 + 5x3 ≤ 15
5x1 + x2 + 2x3 ≤ 10
4x1 + 3x2 - 4x3 ≤ 12
x1, x2, x3 ≥ 0
Задача № 4.
Решить транспортную задачу
|
2 |
7 |
2 |
0 |
20 |
|
3 |
4 |
0 |
0 |
20 |
|
2 |
2 |
6 |
12 |
10 |
|
6 |
7 |
2 |
4 |
15 |
13 13 14 25
Задача № 1
Построение задачи, двойственной к исходной задаче. Теоремы двойственностию.
Построение задачи, двойственной к исходной задаче.
Каждой задаче линейного програмирования (1) можно поставить в соответствие задачу, называемую двойственной (2).
Если построить двойственную задачу по отношению к задаче (2), то получим задачу (1). Задачи 1 и 2 – взаимно-двойственные задачи линейного программирования.
Схема построения двойственных задач.
1. Упорядочивается запись исходной задачи, целевая функция должна стремиться к max, ограничения-неравенства приводятся к виду ≤.
2. Число переменных двойственной задачи (2) Ui равно числу ограничений прямой задачи (1) (т.е. числу m). И наоборот, число ограничений двойственной задачи равно числу переменных прямой задачи n.
3. Свободные члены двойственной задачи (2) есть коэффициенты целевой функции задачи (1) и наоборот.
4. Максимум целевой функции в задаче (1) заменяется на минимум в задаче (2).
5. Матрица коэффициентов ограничений задачи (2) получается путем транспонирования соответствующей матрицы задачи (1).
6. Каждой переменной Ui задачи (2) соответствует i-е ограничение прямой задачи (1). И наоборот, каждой переменной прямой задачи (1) xj соответствует j-е ограничение двойственной задачи (2).
7. Если на j-ю переменную наложено условие не отрицательности, то j-е ограничение будет неравенством типа ≥, в противном случае j-е ограничение будет равенством =. Аналогично связаны между собой ограничения прямой задачи (1) и переменные задачи (2).
Пример.
приводим к виду (1)
Двойственная задача
Теоремы двойственности.
ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство
L(x)max = S(y)min.
Если одна из двойственных задач неразрешима ввиду того, что L(x)max → ∞ (или S(y)min → - ∞), то другая задача не имеет допустимых решений.
ТЕОРЕМА 2. Для оптимальности допустимых решений X и Y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений
Xопт j ( ∑aijyопт i - cj ) = 0,
yопт i ( ∑aijxопт j - bi ) = 0.
Теоремы позволяют определить оптимальное решение одной из пары задач по решению другой.
Задача № 2
Решить задачу графическим методом.
z = x1 + 7 x2 → max
при следующих ограничениях:
5 x1 - x2 ≥10
7 x1 +9 x2 ≤63
х1, х2, х3 ≥ 0.
Решение :
В первую очередь, найдем область допустимых значений, т.е. точки x1 и x2, которые удовлетворяют системе ограничений. По условию задачи x1≥0, x2≥0, т.е. мы рассматриваем только те точки, которые принадлежат первой четверти.
1. Рассмотрим неравенство 1 системы ограничений.
5 x1 - x2≥10
Построим прямую. Заменим знак неравенства на знак равенства.
5 x1 - x2 = 10
Преобразуем уравнение следующим образом.
x1 x2
+ = 10
1/5 -1
Каждый член уравнения разделим на 10.
x x2
+ = 1
2 - 10
Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.
На оси X1 рисуем точку с координатой (2).
На оси X2 рисуем точку с координатой (-10).
Соединяем полученные точки и получаем необходимую прямую.
Нас интересуют точки:
5 x1 - x2 ≥ 10
x2 ≤ 5 x1 - 10
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.
Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.
Область допустимых значений выделена штриховкой.
Точки принадлежащие области допустимых значений: A (2; 0); В (0; 10)
2. Рассмотрим неравенство 2 системы ограничений.
7 x1 + 9 x2 ≤ 63
Построим прямую. Заменим знак неравенства на знак равенства.
7 x1 + 9 x2 = 63
Преобразуем уравнение следующим образом .
x1 x2
+ = 63
1/7 1/9
Каждый член уравнения разделим на 63.
x1 x2
+ = 1
9 7
Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.
На оси X1 рисуем точку с координатой (9).
На оси X2 рисуем точку с координатой (7).
Соединяем полученные точки и получаем необходимую прямую.
Нас интересуют точки:
7 x1 + 9 x2 ≤ 63
9 x2 ≤ -7 x1 + 63
x2 ≤ -7/9 x1+ 7
Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.
Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.
Область допустимых значений выделена штриховкой.
Точки принадлежащие области допустимых значений:
A (2; 0); C (9;0); D (27/38; 245/38)
3. Вернемся к исходной функции z.
z = x1 + 7 x2
Допустим значение функции z равно 1 (абсолютно произвольно выбранное число), тогда
1 = x1 + 7 x2
Данное уравнение является уравнением прямой на плоскости. Из курса аналитической геометрии известно, что данная прямая перпендикулярна вектору, координатами которого являются коэффициенты функции, а именно вектору ON = (1; 7).
Следовательно, с геометрической точки зрения, наша исходная функция z изображается как множество прямых перпендикулярных вектору ON = (1; 7).
Построим вектор ON = (1; 7)
Вектор ON нарисован не в масштабе, исключительно для большей наглядности. Причем очевидно, что значение функции будет возрастать при перемещении прямой в направлении вектора ON.
Диапазон перемещения прямой не от точки O до точки N, а именно, в направлении от точки O к точке N.
Будем перемещать прямую, перпендикулярную вектору ON, до тех пор, пока она полностью не пройдет область допустимых решений.
В нашем случае, касание прямой, перед выходом из области допустимых решений, произойдет в точке D (27/38 , 245/38) . В данной точке значение функции будет наибольшим.
Ответ: Наибольшее значение функция достигает при x1 = 27/38 и x2 = 245/38. Значение функции : z = 871/19
Задача № 3.
Решить задачу симплекс-методом
z = 5x1 + 7x2 + 2x3 → max
3x1 + 3x2 + 5x3 ≤ 15
5x1 + x2 + 2x3 ≤ 10
4x1 + 3x2 - 4x3 ≤ 12
x1, x2, x3 ≥ 0
Решение :
Необходимо найти начальное опорное (абсолютно произвольное) решение для функции z, которое бы удовлетворяло системе наложенных ограничений. Далее, применяя симплекс таблицы, будем получать решения, при которых значение функции будет, как минимум, не убывать. И так до тех пор, пока не достигнем оптимально решения, при котором функция достигает своего максимума. Если, конечно, рассматриваемая нами линейная функция обладаем максимальным значением при заданной системе ограничений. Перед применением симплекс таблиц, необходимо преобразовать систему линейных ограничений и рассматриваемую функцию z к вполне определенному виду.
Свободные члены системы ограничений должны быть неотрицательными.
Свободные члены системы ограничений неотрицательные.
Система ограничений должна быть приведена к каноническому виду.
К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x4 - преобразуем неравенство 1 в равенство.
К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x5 - преобразуем неравенство 2 в равенство.
К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x6 - преобразуем неравенство 3 в равенство.
3x1 + 3x2 + 5x3 + x4 =15
5x1 + x2 + 2x3 + x5 = 10
4x1 + 3x2 -4x3 + x6 = 12
Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.
Определимся с начальным опорным решением.
Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:
Переменная x4 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная.
Переменная x5 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная.
Переменная x6 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x6 - базисная переменная.
Переменные, которые не являются базисными называются свободными переменными. Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное опорное решение.
x нач. = (0, 0, 0, 15, 10, 12)
Функция z не должна содержать базисных переменных.
Вернемся к рассмотрению функции z.
z = 5 x1 + 7 x2 + 2 x3
Функция z не содержат базисных переменных.
Значение функции z для начального решения: z (x нач.) = 0
Для составления начальной симплекс таблицы выполнили все условия.
В процессе дальнейших преобразований возможны два случая. Если в симплекс таблице, на каком то шаге, получим строку z состоящую из неотрицательных элементов - задача решена, мы нашли оптимальное решение. В противном случае - функция не является ограниченной.
При составлении исходной симплекс таблицы, коэффициенты при переменных функции z записываются с противоположными знаками, а свободный член со своим знаком.
|
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
отношение |
|
x4 |
15 |
5 |
||||||
|
x5 |
10 |
10 |
||||||
|
x6 |
12 |
4 |
||||||
|
z |
-5 |
-7 |
-2 |
0 |
0 |
0 |
0 |
- |
Разделим элементы строки 3 на 3.
|
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
отношение |
|
x4 |
15 |
5 |
||||||
|
x5 |
10 |
10 |
||||||
|
x6 |
4 |
4 |
||||||
|
z |
-5 |
-7 |
-2 |
0 |
0 |
0 |
0 |
- |
От элементов строки 1 отнимает соответствующие элементы строки 3, умноженные на 3.
От элементов строки 2 отнимает соответствующие элементы строки 3.
От элементов строки z отнимает соответствующие элементы строки 3, умноженные на -7.
|
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
|
x4 |
3 |
||||||
|
x5 |
6 |
||||||
|
x6 |
4 |
||||||
|
z |
0 |
0 |
0 |
28 |
x1 = (0, 4, 0, 3, 6, 0 )
z = 28 -13/3 x1 + 34/3 x3 -7/3 x6
Значение функции z для данного решения: z (x1) = 28.
|
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
отношение |
|
x4 |
3 |
|||||||
|
x5 |
6 |
|||||||
|
x6 |
4 |
- |
||||||
|
z |
0 |
0 |
0 |
28 |
- |
Разделим элементы строки 1 на 9.
|
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
отношение |
|
x4 |
||||||||
|
x5 |
6 |
|||||||
|
x6 |
4 |
- |
||||||
|
z |
0 |
0 |
0 |
28 |
- |
От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 10/3.
От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на - 4/3.
От элементов строки L отнимает соответствующие элементы строки 1, умноженные на - 34/3.
|
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
|
x4 |
|||||||
|
x5 |
|||||||
|
x6 |
|||||||
|
z |
0 |
0 |
0 |
x2 = (0, 40/9, 1/3, 0, 44/9, 0 )
z = 286/9 -83/27 x1 -34/27 x4 -29/27 x6
Значение функции z для данного решения: z (x2) = 286/9
Учитывая, что все xi ≥ 0, по условию задачи, наибольшее значение функции L равно свободному члену 286/9, т.е. мы получили оптимальное решение.
Ответ : xопт = (0, 40/9, 1/3, 0, 44/9, 0). Значение функции : z = 286/9
Задача № 4
Решить транспортную задачу:
|
2 |
7 |
2 |
0 |
20 |
|
3 |
4 |
0 |
0 |
20 |
|
2 |
2 |
6 |
12 |
10 |
|
6 |
7 |
2 |
4 |
15 |
13 13 14 25
Решение :
Найдем начальное решение методом минимального элемента. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется неоптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.
В нашем случае, потребность всех потребителей - 65 единиц продукции равна запасам всех поставщиков.
1) Согласно условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
2) Минимальный элемент матрицы тарифов находится в ячейке A1B4 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B4 наиболее рентабельный.
Запасы поставщика A1 составляют 20 единиц продукции. Потребность потребителя B4 составляет 25 единиц продукции. (см. таблицу пункта 1).
От поставщика A1 к потребителю B4 будем доставлять min = {20, 25} = 20 единиц продукции.
Разместим в ячейку A1B4 значение равное 20.
Мы полностью израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
3) Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.
Запасы поставщика A2 составляют 20 единиц продукции. Потребность потребителя B3 составляет 14 единиц продукции. (см. таблицу пункта 2).
От поставщика A2 к потребителю B3 будем доставлять min = { 20, 14 } = 14 единиц продукции.
Разместим в ячейку A2B3 значение равное 14
Мы полностью удовлетворили потребность потребителя B3. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
4) Минимальный элемент матрицы тарифов находится в ячейке A2B4 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B4 наиболее рентабельный.
Запасы поставщика A2 составляют 6 единиц продукции. Потребность потребителя B4 составляет 5 единиц продукции. (см. таблицу пункта 3).
От поставщика A2 к потребителю B4 будем доставлять min = { 6, 5 } = 5 единиц продукции.
Разместим в ячейку A2B4 значение равное 5.
Мы полностью удовлетворили потребность потребителя B4. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
5) Минимальный элемент матрицы тарифов находится в ячейке A3B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B1 наиболее рентабельный.
Запасы поставщика A3 составляют 10 единиц продукции. Потребность потребителя B1 составляет 13 единиц продукции. (см. таблицу пункта 4).
От поставщика A3 к потребителю B1 будем доставлять min = { 10, 13 } = 10 единиц продукции.
Разместим в ячейку A3B1 значение равное 10.
Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
|||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
6) Минимальный элемент матрицы тарифов находится в ячейке A2B1 и равен 3, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B1 наиболее рентабельный.
Запасы поставщика A2 составляют 1 единиц продукции. Потребность потребителя B1 составляет 3 единиц продукции. (см. таблицу пункта 5).
От поставщика A2 к потребителю B1 будем доставлять min = { 1, 3 } = 1 единиц продукции.
Разместим в ячейку A2B1 значение равное 1.
Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
7) Минимальный элемент матрицы тарифов находится в ячейке A4B1 и равен 6, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B1 наиболее рентабельный.
Запасы поставщика A4 составляют 15 единиц продукции. Потребность потребителя B1 составляет 2 единиц продукции. (см. таблицу пункта 6).
От поставщика A4 к потребителю B1 будем доставлять min = { 15, 2 } = 2 единиц продукции.
Разместим в ячейку A4B1 значение равное 2.
Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
8) Минимальный элемент матрицы тарифов находится в ячейке A4B2 и равен 7, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B2 наиболее рентабельный.
Запасы поставщика A4 составляют 13 единиц продукции. Потребность потребителя B2 составляет 13 единиц продукции. (см. таблицу пункта 7).
От поставщика A4 к потребителю B2 будем доставлять 13 единиц продукции.
Разместим в ячейку A4B2 значение равное 13.
Мы полностью израсходoвали запасы поставщика A4. Вычеркиваем строку 4 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
10 |
||||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Заполненные нами ячейки будем называть базисными, остальные - свободными.
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.
Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
S0 = 0 * 20 3 * 1 0 * 14 0 * 5 2 * 10 6 * 2 7 * 13 = 126 ден. ед.
Общие затраты на доставку всей продукции, для начального решения , составляют 126 ден. ед.
Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:
2. Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.
3. Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.
4. Находим новое решение, как минимум, не хуже предыдущего.
5. Вычисляем общую стоимость доставки всей продукции для нового решения.
1. ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
ui + vj = cij, где cij - тариф клетки AiBj.
Посколько, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем v1 = 0.
v1 + u2 = c21 v1 + u2 = 3 u2 = 3 - 0 = 3
v3 + u2 = c23 v3 + u2 = 0 v3 = 0 - 3 = -3
v4 + u2 = c24 v4 + u2 = 0 v4 = 0 - 3 = -3
v1 + u3 = c31 v1 + u3 = 2 u3 = 2 - 0 = 2
v1 + u4 = c41 v1 + u4 = 6 u4 = 6 - 0 = 6
v2 + u4 = c42 v2 + u4 = 7 v2 = 7 - 6 = 1
v4 + u1 = c14 v4 + u1 = 0 u1 = 0 - ( -3 ) = 3
|
Поставщик |
Потребитель |
Ui |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- 2 |
- 7 |
- 2 |
20 0 |
U1 = 3 |
|
А2 |
1 3 |
- 4 |
14 0 |
5 0 |
U2 = 3 |
|
А3 |
10 2 |
- 2 |
- 6 |
- 12 |
U3 = 2 |
|
А4 |
2 6 |
13 7 |
- 2 |
- 4 |
U4 = 6 |
|
Vi |
V1 = 0 |
V2 = 1 |
V3 = - 3 |
V4 = - 3 |
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
∆11 = c11 - (u1 + v1) = 2 - (3 + 0) = -1
∆12 = c12 - (u1 + v2) = 7 - (3 + 1) = 3
∆13 = c13 - (u1 + v3) = 2 - (3 + ( -3)) = 2
∆22 = c22 - (u2 + v2 ) = 4 - (3 + 1) = 0
∆32 = c32 - (u3 + v2) = 2 - (2 + 1) = -1
∆33 = c33 - (u3 + v3) = 6 - (2 + ( -3)) = 7
∆34 = c34 - (u3 + v4) = 12 - (2 + ( -3)) = 13
∆43 = c43 - (u4 + v3) = 2 - (6 + ( -3)) = -1
∆44 = c44 - (u4 + v4) = 4 - (6 + ( -3)) = 1
|
Поставщик |
Потребитель |
Ui |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- -1 2 |
- 3 7 |
- 2 2 |
20 0 |
U1 = 3 |
|
А2 |
1 3 |
- 4 |
14 0 |
5 0 |
U2 = 3 |
|
А3 |
10 2 |
- -1 2 |
- 7 6 |
- 13 12 |
U3 = 2 |
|
А4 |
2 6 |
13 7 |
- -1 2 |
- 1 4 |
U4 = 6 |
|
Vi |
V1 = 0 |
V2 = 1 |
V3 = - 3 |
V4 = - 3 |
Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.
Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A3B2 (∆32 = -1).
Построим цикл для выбранной ячейки A3B2.
Поставьте курсор мыши в выбранную свободную ячейку A3B2. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A3B2. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения. Ячейки образующие цикл для свободной ячейки A3B2: A3B2, A3B1, A4B1, A4B2. Пусть ячейка A3B2, для которой мы строили цикл, имеет порядковый номер один.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
1 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Среди ячеек цикла A3B1, A4B2, номера которых четные, найдем ячейку, обладающую найменьшим значением.
min = { 10, 13 } = 10
В данном случае, это ячейка A3B1.
Другими словами, из маршрутов достаки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A3 к потребителю B1, по которому доставляется меньше всего (10) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
От ячеек цикла с четными номерами отнимает 10. К ячейкам с нечетными номерами прибавляем 10.
Мы вводим новый маршрут доставки продукции от поставщика A3 к потребителю B2. По данному маршруту доставим 10 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 10 ден. ед.
По маршруту от поставщика A3 к потребителю B1 мы полностью перестаем доставлять продукцию.
Общие затраты уменьшатся на 2 * 10 ден. ед.
От поставщика A4 к потребителю B1 дополнительно поставим 10 единиц продукции, по цене доставки 6 за единицу продукции. Общие затраты увеличатся на 6 * 10 ден. ед.
Сократим поставку от поставщика A4 к потребителю B2 на 10 единиц продукции, по цене доставки 7 за единицу продукции. Общие затраты уменьшатся на 7 * 10 ден. ед.
Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
2 * 10 - 2 * 10 + 6 * 10 - 7 * 10 = ( 2 - 2 + 6 - 7 ) * 10 = -1 * 10 ден. ед.
Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 126 + ( - 10 ) = 116 ден. ед.
Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
Воспользовавшись таблицей, в которой мы находили оценки свободных ячеек, вы можете убедиться, что в случае выбора:
ячейки A1B1, общая стоимость доставки всей продукции изменилась бы на ∆11 * 1 = -1 * 1 = -1 ден. ед.
ячейки A4B3, общая стоимость доставки всей продукции изменилась бы на ∆43 * 2 = -1 * 2 = -2 ден. ед.
Ячейка A3B1 выйдет из базиса, мы перестали доставлять продукцию от поставщика A3 к потребителю B1
Ячейка A3B2 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A3 к потребителю B2 .
2. ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки AiBj)
Посколько, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем u2 = 0.
v1 + u2 = c21 v1 + u2 = 3 v1 = 3 - 0 = 3
v3 + u2 = c23 v3 + u2 = 0 v3 = 0 - 0 = 0
v4 + u2 = c24 v4 + u2 = 0 v4 = 0 - 0 = 0
v1 + u4 = c41 v1 + u4 = 6 u4 = 6 - 3 = 3
v2 + u4 = c42 v2 + u4 = 7 v2 = 7 - 3 = 4
v4 + u1 = c14 v4 + u1 = 0 u1 = 0 - 0 = 0
v2 + u3 = c32 v2 + u3 = 2 u3 = 2 - 4 = -2
|
Поставщик |
Потребитель |
Ui |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- 2 |
- 7 |
- 2 |
20 0 |
U1 = 0 |
|
А2 |
1 3 |
- 4 |
14 0 |
5 0 |
U2 = 0 |
|
А3 |
- 2 |
10 2 |
- 6 |
- 12 |
U3 = - 2 |
|
А4 |
12 6 |
3 7 |
- 2 |
- 4 |
U4 = 3 |
|
Vi |
V1 = 3 |
V2 = 4 |
V3 = 0 |
V4 = 0 |
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
∆11 = c11 - ( u1 + v1 ) = 2 - ( 0 + 3 ) = -1
∆12 = c12 - ( u1 + v2 ) = 7 - ( 0 + 4 ) = 3
∆13 = c13 - ( u1 + v3 ) = 2 - ( 0 + 0 ) = 2
∆22 = c22 - ( u2 + v2 ) = 4 - ( 0 + 4 ) = 0
∆31 = c31 - ( u3 + v1 ) = 2 - ( -2 + 3 ) = 1
∆33 = c33 - ( u3 + v3 ) = 6 - ( -2 + 0 ) = 8
∆34 = c34 - ( u3 + v4 ) = 12 - ( -2 + 0 ) = 14
∆43 = c43 - ( u4 + v3 ) = 2 - ( 3 + 0 ) = -1
∆44 = c44 - ( u4 + v4 ) = 4 - ( 3 + 0 ) = 1
|
Поставщик |
Потребитель |
Ui |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- - 1 2 |
- 7 |
- 2 |
20 0 |
U1 = 3 |
|
А2 |
1 3 |
- 4 |
14 0 |
5 0 |
U2 = 3 |
|
А3 |
- 2 |
10 2 |
- 6 |
- 12 |
U3 = 2 |
|
А4 |
12 6 |
3 7 |
- -1 2 |
- 4 |
U4 = 6 |
|
Vi |
V1 = 3 |
V2 = 4 |
V3 = 0 |
V4 = 0 |
Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным. Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A4B3 (∆43 = - 1).
Построим цикл для выбранной ячейки A4B3: выбираем свободную ячейку A4B3. Используя горизонтальные и вертикальные перемещения, соединяем непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A4B3. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки. Он единственный. Направление обхода не имеет значения. Ячейки образующие цикл для свободной ячейки A4B3:
A4B3, A4B1, A2B1, A2B3 .
Пусть ячейка A4B3, для которой мы строили цикл, имеет порядковый номер один.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Среди ячеек цикла A4B1 , A2B3 , номера которых четные, найдем ячейку, обладающую найменьшим значением. min = { 12, 14 } = 12. В данном случае, это ячейка A4B1.
Из маршрутов достаки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A4 к потребителю B1, по которому доставляется меньше всего (12) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
От ячеек цикла с четными номерами отнимает 12. К ячейкам с нечетными номерами прибавляем 12. Вводим новый маршрут доставки продукции от поставщика A4 к потребителю B3. По данному маршруту доставим 12 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 12 ден. ед.
По маршруту от поставщика A4 к потребителю B1 мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 6 * 12 ден. ед.
От поставщика A2 к потребителю B1 дополнительно поставим 12 единиц продукции, по цене доставки 3 за единицу продукции. Общие затраты увеличатся на 3 * 12 ден. ед.
Сократим поставку от поставщика A2 к потребителю B3 на 12 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 12 ден. ед.
Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
В итоге получим:
Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
2 * 12 - 6 * 12 + 3 * 12 - 0 * 12 = ( 2 - 6 + 3 - 0 ) * 12 = - 1 * 12 ден. ед.
Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
Когда нашли ячеку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на 43 * 12 = - 1 * 12 = - 12 ден. ед.
Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 116 + ( - 12 ) = 104 ден. ед. .
Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
Воспользовавшись таблицей, в которой мы находили оценки свободных ячеек, вы можете убедиться, что в случае выбора:
ячейка A1B1, общая стоимость доставки всей продукции изменилась бы на 11 * 1 = - 1 * 1 = - 1 ден. ед.
ячейка A4B1 выйдет из базиса, мы перестали доставлять продукцию от поставщика A4 к потребителю B1
ячейка A4B3 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A4 к потребителю B3.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
3 ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута. (ui + vj = cij, где cij - тариф клетки AiBj).
Посколько, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем u2 = 0.
v1 + u2 = c21 v1 + u2 = 3 v1 = 3 - 0 = 3
v3 + u2 = c23 v3 + u2 = 0 v3 = 0 - 0 = 0
v4 + u2 = c24 v4 + u2 = 0 v4 = 0 - 0 = 0
v3 + u4 = c43 v3 + u4 = 2 u4 = 2 - 0 = 2
v4 + u1 = c14 v4 + u1 = 0 u1 = 0 - 0 = 0
v2 + u4 = c42 v2 + u4 = 7 v2 = 7 - 2 = 5
v2 + u3 = c32 v2 + u3 = 2 u3 = 2 - 5 = - 3
|
Поставщик |
Потребитель |
Uj |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- 2 |
- 7 |
- 2 |
20 0 |
u1 = 0 |
|
А2 |
13 3 |
- 4 |
2 0 |
5 0 |
u2 = 0 |
|
А3 |
- 2 |
10 2 |
- 6 |
- 12 |
u3 = - 3 |
|
А4 |
- 6 |
3 7 |
12 2 |
- 4 |
u4 = 2 |
|
Vi |
V1 = 3 |
V2 = 5 |
V3 = 0 |
V4 = 0 |
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
∆11 = c11 - (u1 + v1) = 2 - (0 + 3) = -1
∆12 = c12 - (u1 + v2) = 7 - (0 + 5) = 2
∆13 = c13 - (u1 + v3) = 2 - (0 + 0) = 2
∆22 = c22 - (u2 + v2) = 4 - (0 + 5) = -1
∆31 = c31 - (u3 + v1) = 2 - (-3 + 3) = 2
∆33 = c33 - (u3 + v3) = 6 - (-3 + 0) = 9
∆34 = c34 - (u3 + v4) = 12 - (-3 + 0) = 15
∆41 = c41 - (u4 + v1) = 6 - (2 + 3) = 1
∆44 = c44 - (u4 + v4) = 4 - (2 + 0) = 2
|
Поставщик |
Потребитель |
Uj |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- - 1 2 |
- 2 7 |
- 2 2 |
20 0 |
u1 = 0 |
|
А2 |
13 3 |
- - 1 4 |
2 0 |
5 0 |
u2 = 0 |
|
А3 |
- 2 2 |
10 2 |
- 9 6 |
- 15 12 |
u3 = - 3 |
|
А4 |
- 1 6 |
3 7 |
12 2 |
- 4 |
u4 = 2 |
|
Vi |
V1 = 3 |
V2 = 5 |
V3 = 0 |
V4 = 0 |
Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.
Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A1B1 (11 = - 1).
Построим цикл для выбранной ячейки A1B1.
Ячейки образующие цикл для свободной ячейки A1B1: A1B1, A1B4, A2B4, A2B1.
Пусть ячейка A1B1, для которой мы строили цикл, имеет порядковый номер один.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Среди ячеек цикла A1B4, A2B1, номера которых четные, найдем ячейку, обладающую найменьшим значением min = {20, 13} = 13. В данном случае, это ячейка A2B1.
Другими словами, из маршрутов достаки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A2 к потребителю B1, по которому доставляется меньше всего (13) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
От ячеек цикла с четными номерами отнимает 13. К ячейкам с нечетными номерами прибавляем 13.
Мы вводим новый маршрут доставки продукции от поставщика A1 к потребителю B1. По данному маршруту доставим 13 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 13 ден. ед.
Сократим поставку от поставщика A1 к потребителю B4 на 13 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 13 ден. ед.
От поставщика A2 к потребителю B4 дополнительно поставим 13 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 13 ден. ед.
По маршруту от поставщика A2 к потребителю B1 мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 3 * 13 ден. ед.
Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
2 * 13 - 0 * 13 + 0 * 13 - 3 * 13 = ( 2 - 0 + 0 - 3 ) * 13 = - 1 * 13 ден. ед.
Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
В тот момент, когда мы нашли ячеку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на
∆11 * 13 = -1 * 13 = -13 ден. ед.
Общие затраты на доставку всей продукции, для данного решения, составляют
S0 = 104 + (- 13) = 91 ден. ед. .
Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
Воспользовавшись таблицей, в которой мы находили оценки свободных ячеек, мы можем убедиться, что в случае выбора: ячейки A2B2, общая стоимость доставки всей продукции изменилась бы на ∆22 * 2 = -1 * 2 = - 2 ден. ед.
Ячейка A2B1 выйдет из базиса, мы перестали доставлять продукцию от поставщика A2 к потребителю B1.
Ячейка A1B1 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A1 к потребителю B1.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
4 ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки AiBj)
Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем v4 = 0.
v4 + u1 = c14 v4 + u1 = 0 u1 = 0 - 0 = 0
v4 + u2 = c24 v4 + u2 = 0 u2 = 0 - 0 = 0
v1 + u1 = c11 v1 + u1 = 2 v1 = 2 - 0 = 2
v3 + u2 = c23 v3 + u2 = 0 v3 = 0 - 0 = 0
v3 + u4 = c43 v3 + u4 = 2 u4 = 2 - 0 = 2
v2 + u4 = c42 v2 + u4 = 7 v2 = 7 - 2 = 5
v2 + u3 = c32 v2 + u3 = 2 u3 = 2 - 5 = - 3
|
Поставщик |
Потребитель |
Uj |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- 2 |
- 7 |
- 2 |
20 0 |
u1 = 0 |
|
А2 |
13 3 |
- 4 |
2 0 |
5 0 |
u2 = 0 |
|
А3 |
- 2 |
10 2 |
- 6 |
- 12 |
u3 = - 3 |
|
А4 |
- 6 |
3 7 |
12 2 |
- 4 |
u4 = 2 |
|
Vi |
V1 = 2 |
V2 = 5 |
V3 = 0 |
V4 = 0 |
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
∆12 = c12 - (u1 + v2) = 7 - (0 + 5) = 2
∆13 = c13 - (u1 + v3) = 2 - (0 + 0) = 2
∆21 = c21 - (u2 + v1) = 3 - (0 + 2) = 1
∆22 = c22 - (u2 + v2) = 4 - (0 + 5) = -1
∆31 = c31 - (u3 + v1) = 2 - (-3 + 2) = 3
∆33 = c33 - (u3 + v3) = 6 - (-3 + 0) = 9
∆34 = c34 - (u3 + v4) = 12 - (-3 + 0) = 15
∆41 = c41 - (u4 + v1) = 6 - (2 + 2) = 2
∆44 = c44 - (u4 + v4) = 4 - (2 + 0) = 2
|
Поставщик |
Потребитель |
Uj |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
- 2 |
- 2 7 |
- 2 2 |
20 0 |
u1 = 0 |
|
А2 |
13 1 3 |
- - 1 4 |
2 0 |
5 0 |
u2 = 0 |
|
А3 |
- 3 2 |
10 2 |
- 9 6 |
- 15 12 |
u3 = - 3 |
|
А4 |
- 2 6 |
3 7 |
12 2 |
- 2 4 |
u4 = 2 |
|
Vi |
V1 = 2 |
V2 = 5 |
V3 = 0 |
V4 = 0 |
Оценка свободной ячейки A2B2 (незадействованного маршрута) отрицательная (∆22 = - 1), следовательно решение не является оптимальным.
Построим цикл для выбранной ячейки A2B2:
Поставьте курсор мыши в выбранную свободную ячейку A2B2. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A2B2. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения. Ячейки образующие цикл для свободной ячейки A2B2:
A2B2, A2B3, A4B3, A4B2
Пусть ячейка A2B2, для которой мы строили цикл, имеет порядковый номер один.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Среди ячеек цикла A2B3, A4B2, номера которых четные, найдем ячейку, обладающую найменьшим значением. min = {2, 3} = 2
В данном случае, это ячейка A2B3.
Другими словами, из маршрутов достаки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A2 к потребителю B3, по которому доставляется меньше всего (2) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
От ячеек цикла с четными номерами отнимает 2. К ячейкам с нечетными номерами прибавляем 2.
Что мы делаем?
Мы вводим новый маршрут доставки продукции от поставщика A2 к потребителю B2. По данному маршруту доставим 2 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты увеличатся на 4 * 2 ден. ед.
По маршруту от поставщика A2 к потребителю B3 мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 0 * 2 ден. ед.
От поставщика A4 к потребителю B3 дополнительно поставим 2 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 2 ден. ед.
Сократим поставку от поставщика A4 к потребителю B2 на 2 единиц продукции, по цене доставки 7 за единицу продукции. Общие затраты уменьшатся на 7 * 2 ден. ед.
Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
4 * 2 - 0 * 2 + 2 * 2 - 7 * 2 = ( 4 - 0 + 2 - 7 ) * 2 = - 1 * 2 ден. ед.
Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
В тот момент, когда мы нашли ячеку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на
∆22 * 2 = -1 * 2 = -2 ден. ед.
Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 91 + ( - 2 ) = 89 ден. ед. .
Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
Ячейка A2B3 выйдет из базиса, мы перестали доставлять продукцию от поставщика A2 к потребителю B3.
Ячейка A2B2 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A2 к потребителю B2.
|
Поставщик |
Потребитель |
Запас |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
20 |
||||
|
А2 |
20 |
||||
|
А3 |
111 |
10 |
|||
|
А4 |
15 |
||||
|
Потребность |
13 |
13 |
14 |
25 |
5 ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки AiBj)
Посколько, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем v2 = 0.
v2 + u2 = c22 v2 + u2 = 4 u2 = 4 - 0 = 4
v4 + u2 = c24 v4 + u2 = 0 v4 = 0 - 4 = -4
v2 + u3 = c32 v2 + u3 = 2 u3 = 2 - 0 = 2
v2 + u4 = c42 v2 + u4 = 7 u4 = 7 - 0 = 7
v3 + u4 = c43 v3 + u4 = 2 v3 = 2 - 7 = -5
v4 + u1 = c14 v4 + u1 = 0 u1 = 0 - ( -4 ) = 4
v1 + u1 = c11 v1 + u1 = 2 v1 = 2 - 4 = -2
|
Поставщик |
Потребитель |
Uj |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
13 2 |
- 7 |
- 2 |
7 0 |
u1 = 4 |
|
А2 |
- 3 |
2 4 |
- 0 |
18 0 |
u2 = 4 |
|
А3 |
- 2 |
10 2 |
- 6 |
- 12 |
u3 = 2 |
|
А4 |
- 6 |
1 7 |
14 2 |
- 4 |
u4 = 7 |
|
Vi |
V1 = - 2 |
V2 = 0 |
V3 = - 5 |
V4 = - 4 |
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
∆12 = c12 - (u1 + v2) = 7 - (4 + 0) = 3
∆13 = c13 - (u1 + v3) = 2 - (4 + ( -5 )) = 3
∆21 = c21 - (u2 + v1) = 3 - (4 + ( -2 )) = 1
∆23 = c23 - (u2 + v3) = 0 - (4 + ( -5 )) = 1
∆31 = c31 - (u3 + v1) = 2 - (2 + ( -2 )) = 2
∆33 = c33 - (u3 + v3) = 6 - (2 + ( -5 )) = 9
∆34 = c34 - (u3 + v4) = 12 - (2 + ( -4 )) = 14
∆41 = c41 - (u4 + v1) = 6 - (7 + ( -2 )) = 1
∆44 = c44 - (u4 + v4) = 4 - (7 + ( -4 )) = 1
|
Поставщик |
Потребитель |
Uj |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
13 2 |
- 3 7 |
- 3 2 |
7 0 |
u1 = 4 |
|
А2 |
- 1 3 |
2 4 |
- 1 0 |
18 0 |
u2 = 4 |
|
А3 |
- 2 2 |
10 2 |
- 9 6 |
- 14 12 |
u3 = 2 |
|
А4 |
- 1 6 |
1 7 |
14 2 |
- 1 4 |
u4 = 7 |
|
Vi |
V1 = - 2 |
V2 = 0 |
V3 = - 5 |
V4 = - 4 |
Все оценки свободных ячеек положительные, следовательно, найдено оптимальное решение.
Ответ:
13 0 0 7
X опт = 0 2 0 18
0 10 0 0
0 1 14 0
Smin = 2 * 13 + 0 * 7 + 4 * 2 + 0 * 18 + 2 * 10 + 7 * 1 + 2 * 14 = 89
Общие затраты на доставку всей продукции, для оптимального решения, составляют 89 ден. ед.