35835

Математические методы анализа экономики

Контрольная

Математика и математический анализ

Для разрешимости транспортной задачи необходимо чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. В нашем случае потребность всех потребителей 65 единиц продукции равна запасам всех поставщиков. из незадействованных маршрутов маршрут доставки продукции от поставщика 1 к потребителю B4 наиболее рентабельный. Запасы поставщика 1 составляют 20 единиц продукции.

Русский

2013-09-20

435 KB

1 чел.

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

РЫБИНСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ имени П. А. СОЛОВЬЕВА

Факультет заочного обучения

Кафедра математического и программного обеспечения

электронных вычислительных средст

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Математические методы анализа экономики»

ВАРИАНТ № 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 - x210  

Построим прямую. Заменим знак неравенства на знак равенства.

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 записываются с противоположными знаками, а свободный член со своим знаком.

  1.  За ведущий выберем столбец 2 , так как -7 наименьший элемент в z строке. Элемент z строки, принадлежащий столбцу свободных членов не рассматриваем. За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2.

базисные

переменные

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.

  1.  За ведущий выберем столбец 3 , так как -34/3 наименьший элемент в z строке. Элемент z строки, принадлежащий столбцу свободных членов не рассматриваем. За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 3.

базисные

переменные

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 ден. ед.  

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

  1.  Находим потенциалы поставщиков и потребителей для имеющегося решения.

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 ден. ед.


 

А также другие работы, которые могут Вас заинтересовать

5500. Характеристика Европы, Азии, Африки и Америки 69.5 KB
  Общая характеристика Европы Европа - это часть света. Вместе с Азией Европа составляет единый материк, который называется Евразия. На территории Европы более 40 государств, Они различаются по площади, численности населения, государственному уст...
5501. Общенаучные конкретно предметные методы ИССЭП 19.55 KB
  Общенаучные конкретно предметные методы ИССЭП. Общенаучные методы исследования. Метод социальное диалектики Анализ и синтез Индукция и дедукция Моделирование Закон восхождения от простого к сложному от низшего к высшему и...
5502. Сегментация сфер затрат и организация центров ответственности 50 KB
  Сегментация сфер затрат и организация центров ответственности Согласно современным представлениям эффективное управление предприятием и его подразделами может осуществляться на основе применения экономических методов. Теоретическую платформу указанн...
5503. Основные теоремы о пределах 124.5 KB
  Основные теоремы о пределах. Теорема (о предельном переходе в равенствах). Если в некоторой окрестности точки значения функций f(x) и g(x) совпадают, то их пределы в этой точке равны: f(x)=g(x) => . Теорема (о предельном перехо...
5504. Стадии разработки технических кодексов 75 KB
  Стадии разработки технических кодексов Разработка ТКП включает следующие стадии: - подготовка к разработке - разработка рабочего проекта ТКП - разработка окончательной редакции проекта ТКП - утверждение ТКП - государственная регистрация ТКП. Рес...
5505. Интерфейсы. Определение и реализация интерфейсов 71.5 KB
  Интерфейсы В этом разделе рассматриваются интерфейсы за счет представления полного определения одного из интерфейсов, определенного Microsoft - System. IDisposable. Интерфейс IDisposable содержит один метод Dispose, предназначенный для...
5506. Микозы. Особенности заболевания и ухода за больным 77 KB
  Микозы Определение Этиология Классификация по клиническим формами разновидностям Тактика среднего медицинского работника при данных заболеваниях Принципы лечения Особенности ухода за пациентами Диспансеризац...
5507. Основные правовые и законодательные документы по осуществлению агропромышленной интеграции 50.61 KB
  Основные правовые и законодательные документы по осуществлению агропромышленной интеграции В агропромышленном комплексе России функционируют различные агропромышленные формирования (агрофирмы, холдинги, финансово-промышленные группы и др.), деятельн...
5508. Використання вбудованих функцій excel для фінансових розрахунків 495 KB
  Використання вбудованих функційexcel для фінансових розрахунків Фінансові функції Excel призначенні для обчислення базових величин, необхідних для проведення складних фінансових розрахунків. Прості та складні відсотки Прості відсотки...