Модели оптимального объема производства

Получили математическую модель задачи.

Имеем целевую функцию линейной формы:

Z = 15Xi + 16Х₂ --> шах (1)

систему линейных ограничений:

10 Х₁ + 5Х₂, <= 200

2,5Х₁ + 5Х₂<= 100 (2)

2 Х₁ + 1,2Х₂<= 60

и граничные условия: X, >= 0, Х₂ >=0 (3)

Задача формулируется следующим образом: найти такие неотрицательные значения переменных X, и Х₂, которые будут удовлетворять системе ограничений (2) и обращать в максимум целевую функцию (1).

Целевая функция и ограничения имеют линейную форму, поэтому данная задача относится к классу задач линейного программирования и для ее решения можно использовать симплекс-метод. Так как задача имеет только две переменные, она может быть решена графическим методом.

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ

Введем на плоскости прямоугольную систему координат Х_1, Х₂.

ОПРЕДЕЛЕНИЕ ОБЛАСТИ ДОПУСТИМЫХ РЕШЕНИЙ

Область допустимых решений определяется граничными условиями (3) и системой неравенств (2). Граничные условия Х₁ >=0, Х₂ >=0 указывают на то, что область допустимых решений находится в 1-м квадранте.

Построим систему неравенств (2). Каждое неравенство геометрически определяет полуплоскость с граничными прямыми

10 Х₁ + 5Х₂, <= 200

2,5Х₁ + 5Х₂<= 100 (4)

2 Х₁ + 1,2Х₂<= 60

Построим эти прямые (рис. 1). Каждая из них делит плоскость на две полуплоскости. Решение следует искать в той полуплоскости, все точки которой удовлетворяют неравенству. Чтобы определить эту полуплоскость, возьмем какую-нибудь точку на плоскости, например точку с координатами (0,0). Если приравнять нулю значения Х₁ и Х₂ в левой части соответствующих неравенств, получим соотношение 0 <= const, значит точка с координатами (0,0) входит в полуплоскость, соответствующую рассматриваемому неравенству. Во все полуплоскости, соответствующие ограничениям (2) входит начало координат (при Х₁=Х2=0 10 Х₁ + 5Х₂, <= 200, 2,5Х₁ + 5Х₂<= 100, 2 Х₁ + 1,2Х₂<= 60). Так как система (2) совместна, то полуплоскости, пересекаясь, образуют общую для всех полуплоскостей часть, которая представляет собой многоугольник. Таким образом, определили область, удовлетворяющую всем ограничениям и граничным условиям, то есть область допустимых решений (многоугольник решений). Известно, что оптимальное решение должно находиться на границе этой области, и, если решение единственное, в одной из ее вершин. Точка с координатами (X₁, Х₂), в которой значение целевой функции достигает максимума, должна находиться в одной из вершин выделенного многоугольника.

НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ

Проведем линию уровня целевой функции, проходящую через начало координат:

Z= 15Х₁ + 16Х₂ = 0.

Значение Z возрастает в направлении нормального вектора п = {15; 16}. Будем передвигать прямую параллельно самой себе в направлении вектора п до тех пор, пока многоугольник решений не будет находиться по одну сторону от нее, и прямая не будет иметь с ним, по крайней мере, одну общую точку. Этой точкой будет точка С с координатами Х₁ = 13,3 и Х₂= 13,3, в которой целевая функция Z принимает максимальное значение. Подставив значения Х₁= 13,3 и Х₂= 13,3 в целевую функцию Z= 15Х₁ + 16Х₂ = 0. Получим ее максимальное значение Z = 15•13,3+16•13,3 =413.

Общая прибыль от реализации x₁ изделий вида А и x₂ изделий вида В составит:

Z=15•x₁+16•x₂>max

Таким образом, мы приходим к решению следующей математической задачи: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция Z принимает максимальное значение.

Решим неравенства, преобразовав их в равенства:

1) 10•x₁+5•x₂=200

x₁=0 > x₂=40

x₂=0 > x₁=20

2) 2,5•x₁+5•x₂=100

x₁=0 > x₂=20

x₂=0 > x₁=40

3) 2•x₁+1,2•x₂=60

x₁=0 > x₂=50

x₂=0 > x₁=30

10•x₁+5•x₂=200

2,5•x₁+5•x₂=100

x₁=13,3 (13)

x₂=13,3 (13)

Z=15•13,3+16•13,3=413

Это оптимальное решение.

(Точность решения задачи будет зависеть от точности построения графика.)

Ответ: max Z =413 при X_t = 13,3, Х₂ = 13,3.

ИСПОЛЬЗОВАНИЕ СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧИ

Определение базисного (допустимого) решения

10•x₁+5•x₂?200 10•x₁+5•x₂+x₃=200

2,5•x₁+5•x₂?100 2,5•x₁+5•x₂+x₄=100

2•x₁+1,2•x₂?60 2•x₁+1,2•x₂+x₅=60

x₁, x₂, x₃, x₄, x₅?0 Z=15•x₁+16•x₂+0•x₃+0•x₄+0•x₅

x₃=200-(10•x₁+5•x₂)

x₄=100-(2,5•x₁+5•x₂)

x₅=60-(2•x₁+1,2•x₂)

Z=0-(-15•x₁-16•x₂-0•x₃-0•x₄-0•x₅)

x₁=0, x₂=0, x₃=200, x₄=100, x₅=60

1. Из отрицательных элементов последней строки табл.1.2, соответствующих переменным x₁ и x_2, выберем максимальный по модулю элемент: -16, соответствует x₂. Небазисная переменная x₂ должна быть введена в базис. 2. Поделим элементы столбца значений базисных переменных на соответствующие положительные коэффициенты выбранного столбца: 200/5=40

100/5=20

60/1,2=50

Запишем частные от деления во вспомогательный столбец б. Выберем элемент, который дает минимальное частное от деления: 20. Минимальное частное 20 соответствует второй строке с базисной переменной x₄. Переменная x₄ должна быть выведена из базиса.

3. Разделим элементы выбранной строки (второй строки) на разрешающий элемент (5). Результат запишем во вторую строку симплекс-таблицы 9. Построение первой строки симплекс-таблицы 1.3

4. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на коэффициент первого элемента выделенного столбца симплекс-таблицы 1.2 и вычтем из соответствующих элементов первой строки симплекс-таблицы 1.2. Получим первую строку симплекс-таблицы 1.3.

Построение третьей строки симплекс-таблицы 1.3.

5. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на коэффициент третьего элемента выделенного столбца симплекс-таблицы 1.2 и вычтем из соответствующих элементов третьей строки симплекс-таблицы 1.2. Получим третью строку симплекс-таблицы 1.3.

Построение четвертой строки симплекс-таблицы 1.3

6. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на коэффициент четвертого элемента выделенного столбца симплекс-таблицы 1.2 и вычтем из соответствующих элементов четвертой строки симплекс-таблицы 1.2. Получим четвертую строку симплекс-таблицы 1.3. 7. В симплекс-таблице 1.3 проделываются аналогичные операции, что и в симплекс-таблице 1.2. Полученные результаты записываем в симплекс-таблицу 1.4.

Таблица 1.2

Таблица 1.3

Проверим, является ли данное решение допустимым.

Так как в столбце значений базисных переменных все элементы неотрицательные, то полученное решение является допустимым.

Проверка на оптимальность:

целевая функция имеет максимальное значение, так как все коэффициенты в строке целевой функции положительны.

Таблица 1.4

Двойственная задача

Исходная задача Двойственная задача

10•x₁+5•x₂?200 10•y₁+2,5•y₂+2•y₃?15

2,5•x₁+5•x₂?100 5•y₁+5•y₂+1,2•y₃?16

2•x₁+1,2•x₂?60

x₁,x₂?0

Z=15•x₁+16•x₂>max Z_д=200•y₁+100•y₂+60•y₃>min

Анализ оптимального решения

При увеличении ресурса R_i: Z=Z_опт+y_i•1

При уменьшении ресурса R_i: Z=Z_опт-y_i•1

R₁: Z=Z_опт+1•1=413+1=414

Z=Z_опт-1•1=413-1=412

R₂: Z=Z_опт+2•1=413+2=415

Z=Z_опт-2•1=413-2=411

R₃: Z=Z_опт+0•1=413+0=413

Z=Z_опт-0•1=413-0=413

Отчёты по пределам

Z=15•13,3+16•13,3=413

Для значения х₁ на нижнем пределе:

Z=15•0+16•13,3=213

Для значения х₂ на нижнем пределе:

Z=15•13,3+16•0=200

РЕШЕНИЕ ЗАДАЧИ В EXCEL

Для решения задачи составьте электронную таблицу, отражающую ее математическую модель (рис. 2, 3). На рис. 2 показана электронная таблица в режиме отображения вычислений (исходное состояние), на рис. 3 - в режиме отображения формул. На рисунках введено сокращение: ЦФ - целевая функция.

Рис. 2

Рис. 3

Работа в диалоговом окне «Поиск решения»

Для подготовки к решению задачи оптимизации выполните команду: Сервис - Поиск решения. На экране появится диалоговое окно Поиск решения (рис. 4). Выполните следующие действия:

В поле Установить целевую ячейку введите адрес $D$5.

Для выбора направления изменения целевой функции установите переключатель в положение Максимальному значению.

Рис. 4

В поле Изменяя ячейки введите адрес блока ячеек $В$3: $С$3.

4.Введите граничные условия и ограничения: щелкните по кнопке Добавить. На экране появится диалоговое окно Добавление ограничения. Для ввода граничных условий Х₁чХ₂ > 0 в поле Ссылка на ячейку введите левую часть отношения (B3:СЗ), в следующее поле - его знак (?), в последнее поле введите правую часть ограничения - 0. Щелкните по клавише Добавить. На экране появится диалоговое окно Добавление ограничения. Введите ограничения по ресурсам: D8:D10 ? F8:F10 аналогичным образом и щелкните по кнопке ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями (рис. 5).

Решение задачи Решение задачи будем производить в диалоговом окне Поиск решения. В нем выполните следующие действия:

1.Щелкните по кнопке Параметры. Появится диалоговое окно Параметры поиска решения (рис. 6).

2.Установите Максимальное время решения задачи (оставьте предлагаемое по умолчанию - 100 с), Предельное число итераций (оставьте предлагаемое по умолчанию - 100).

3.Установите флажок Линейная модель.

4.Нажмите ОК. Появится диалоговое окно Поиск решения.

5.Щелкните по кнопке Выполнить. Появится диалоговое окно Результаты поиска решения (рис.7).

Рис. 5

Рис. 6

Рис. 7

В окне Результаты поиска решения в поле Тип отчета выделите названия всех трех отчетов: Результаты, Устойчивость, Пределы. В рабочей книге появятся три новых листа с их именами.

Закройте окно, нажав ОК. На экране появится исходная таблица с результаты решения задачи (рис. 8): в блоке ячеек ВЗ:СЗ - значения переменных Х₁-Х₂ (Х₁=13,33, Х₂=13,33), в ячейке D5 - максимальное значение целевой функции (413,33).

Результаты решения в Excel совпадают с результатами, полученными при решении задачи графическим методом и симплекс-методом.

Рис. 8

Анализ оптимального решения задачи в Excel

Отчет по результатам

Щелкните мышью по ярлычку Отчет по результатам. На экране появится лист данного отчета (рис. 9).

В верхней таблице отчета указан номер ячейки - $D$5 (целевой ячейки), в которой находится значение целевой функции, исходное, равное 0, и результирующее - максимальное значение целевой функции - 413,33, полученное в результате решения задачи оптимизации.

В средней таблице отчета располагаются номера ячеек, в которых находятся значения искомых переменных Х₁ и Х₂, исходные (равные нулю) и результирующие значения (соответственно 13,33 и 13,33), при которых целевая функция достигает максимального значения.

Рис. 9

В нижней таблице представлены номера ячеек, в которых записаны значения левых частей ограничений, полученные после решения задачи оптимизации (требуемое количество ресурсов каждого вида, необходимое для получения максимального значения целевой функции). В столбце Разница приводятся данные о разности между значениями левых частей ограничений, полученных в результате решения задачи (требуемым количеством ресурсов), и правых частей ограничений (имеющимся количеством ресурсов), другими словами, данные о количестве неиспользованного ресурса каждого вида. Если разность равна нулю (ресурс используется полностью), то в соответствующей ячейке столбца Статус указывается связанное, если разность не равна нулю (ресурс используется не полностью), в соответствующей ячейке столбца Статус записано не связанное.

Ниже приводятся номера ячеек, в которых располагаются значения искомых переменные Х₁ и Х₂ и их значения, при которых целевая функция достигает максимального значения.

Отчет по устойчивости

Щелкните мышью по ярлычку Отчет по устойчивости. На экране появится лист данного отчета (рис. 10).

Рис. 10

В нем приводятся данные о чувствительности целевой ячейки к изменению ограничений. Отчет состоит из двух таблиц: Изменяемые ячейки и Ограничения.

В таблице Изменяемые ячейки выводятся номера ячеек, в которых находятся искомые переменные Х₁ и Х₂ и их значения, при которых целевая функция достигает максимума.

В столбце Целевой коэффициент приводятся значения коэффициентов при изменяемых переменных Х₁ и Х₂ в выражении целевой функции.

Столбцы Допустимое увеличение и Допустимое уменьшение

характеризуют пределы, в которых могут изменяться эти коэффициенты, без изменения найденного оптимального решения.

В таблице Ограничения содержится информация об ограничениях, накладываемых на оптимизируемые переменные.

В столбце Результирующие значения указаны данные о потребности в ресурсах для оптимального решения.

Данные столбца Теневая цена характеризуют изменение значения целевой функции (Z) при увеличении на единицу значения соответствующего ограничения (для ресурсов R₁, R₂, R₃), т.е. двойственные оценки (Y₁ Y₂, Y₃)

Столбцы Допустимое увеличение и Допустимое уменьшение характеризуют пределы, в которых могут изменяться объемы изменяющихся ресурсов, если не изменять оптимального набора переменных, входящих в оптимальное решение.

Отчет по пределам

Щелкните по ярлычку Отчет по пределам. Появится окно отчета (рис. 11).

Рис. 11

В нем приводится оптимальное значение целевой функции и соответствующие ему значения переменных Х₁ и Х₂, а также нижний и верхний пределы их изменения, при которых не нарушаются ограничения модели. Например,

Z= 15Х₁ + 16Х₂ = 15Ч13,33 + 16Ч13,33 = 76,7+ 73,3 = 413,3 - оптимальное решение.

Задача 2

Условие задачи

Предприятию требуется перевезти товары стрех складов (S₁, S₂, S₃) в четыре магазина (M_l, М₂, М_З, М₄). Данные о наличии товаров на складе, спрос на него в магазинах, а также стоимости перевозки тысячи штук товара (в условных единицах) со складов в магазины приведены в табл. 2,1. Составить такой план перевозки товаров, при котором затраты будут минимальными. (Транспортировка товаров возможна с любого склада в любой магазин.)

Таблица 2.1

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Пусть X_ij - количество товара, отправляемого из склада i в магазин j, C_ij - стоимость перевозки тысячи единиц товара со склада i в магазин j. Очевидно, что X_ij ? 0 и C_ij ? 0. В силу ограничений наличие товара на складах и спрос на него в магазинах величина должны выполняться следующие условия:

1.

X₁₁ + X₁₂ + X₁₃ + X₁₄ = 25

X₂₁ + X₂₂ + X₂₃ + X₂₄ = 45

X₃₁ + X₃₂ + X₃₃ + X₃₄ = 30

2.

X₁₁ + X₂₁ + X₃₁ = 30

X₁₂ + X₂₂ + X₃₂ = 10

X₁₃ +X₂₃ + X₃₃ = 30

X₁₄ +X₂₄ + X₃₄ = 30

Общая стоимость перевозок равна:

Для рассматриваемого примера

Z = 6 • X₁₁ + 10 • X₁₂ + 4 • X₁₃ + 7 • X₁₄ + 9 • X₂₁ + 12 • X₂₂ + 6 • X₂₃ + 4 • X₂₄ + 2 • X₃₁ +3 • X₃₂ + 5 • X₃₃ + 8 • X₃₄

Задача формулируется следующим образом: определить такие неотрицательные значения переменных X_ij , которые удовлетворяют ограничениям 1 и 2 и обращают в минимум целевую функцию Z. В такой постановке является транспортной задачей линейного программирования. Необходимым и достаточным условием разрешимости транспортной задачи является условие баланса:

Где

= - суммарное количество товара на складах;

= - суммарное количество товара, требуемое в магазинах.

В данной задаче

= 100,

Следовательно, задача с балансом.

РЕШЕНИЕ ЗАДАЧИ

Решение транспортной задачи состоит из двух этапов:

Определение допустимого решения (базисного решения).

Определение оптимального решения путем последовательного улучшения допустимого решения методом потенциалов.

Определение допустимого решения методом северо-западного угла

Согласно условию задачи составим таблицу. (тарифы c_ij располагаются в нижнем правом углу ячейки)

Рассмотрим маршрут доставки от поставщика S₁ к потребителю M₁ (ячейка S₁M₁). Запасы поставщика S₁ составляют 25 единиц продукции. Потребность потребителя M₁ составляет 30 единиц продукции. От поставщика S₁ к потребителю M₁ будем доставлять min = { 25 , 30 } = 25 единиц продукции. Разместим в ячейку S₁M₁ значение равное 25

Мы полностью удовлетворили потребность потребителя S₁. Вычеркиваем строку 1 таблицы, т.е исключаем её из дальнейшего рассмотрения.

Таблица 2.2

Рассмотрим маршрут доставки от поставщика S₂ к потребителю M₁ (ячейка S₂M₁).

Запасы поставщика S₂ составляют 45 единиц продукции. Потребность потребителя M₁ составляет 5 единиц продукции. От поставщика S₂ к потребителю M₁ будем доставлять min = { 45 , 5 } = 5 единиц продукции.

Разместим в ячейку S₂M₁ значение равное 5

Мы полностью израсходoвали запасы поставщика M₁. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Таблица 2.3

Рассмотрим маршрут доставки от поставщика S₂ к потребителю M₂ (ячейка S₂M₂). Запасы поставщика S₂ составляют 40 единиц продукции. Потребность потребителя M₂ составляет 10 единиц продукции. От поставщика S₂ к потребителю M₂ будем доставлять min = { 40 , 10 } = 10 единиц продукции. Разместим в ячейку S₂M₂ значение равное 10

Мы полностью удовлетворили потребность потребителя M₂. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Таблица 2.4

Рассмотрим маршрут доставки от поставщика S₂ к потребителю M₃ (ячейка S₂M₃).

Запасы поставщика S₂ составляют 30 единиц продукции. Потребность потребителя M₃ составляет 30 единиц продукции. От поставщика S₂ к потребителю M₃ будем доставлять min = { 30 , 30 } = 30 единиц продукции.

Разместим в ячейку S₂M₃ значение равное 30

Мы полностью израсходoвали запасы поставщика S₂ и удовлетворили потребность потребителя M₃. Вычеркиваем строку 2 таблицы и столбец 3, т.е исключаем их из дальнейшего рассмотрения.

Таблица 2.5

Рассмотрим маршрут доставки от поставщика S₃ к потребителю M₄ (ячейка S₃M₄).

Запасы поставщика S₃ составляют 30 единиц продукции. Потребность потребителя M₃ составляет 30 единиц продукции.

От поставщика S₃ к потребителю M₄ будем доставлять min = { 30, 30 } = 30 единиц продукции.

Разместим в ячейку S₃M₄ значение равное 30

Мы полностью удовлетворили потребность потребителя M₄ и израсходовали запасы поставщика S₃. Вычеркиваем столбец 4 и строку 3 таблицы, т.е исключаем его из дальнейшего рассмотрения..

Таблица 2.7

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 6, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Z = 6 * 25 + 5 * 9 + 10 * 12 + 30 * 6 + 30 * 8 = 735 ден. ед.

Общие затраты на доставку всей продукции, для начального решения , составляют 735 ден. ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

(ui + vj = cij, где cij - тариф клетки SiMj)

Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v1 = 0.

V₁ + u₁ = c₁₁ v₁ + u₁ = 6 u₁ = 6 - 0 = 6

V₁ + u₂ = c₂₁ v₁ + u₂ =9 u₂ = 9 - 0 = 9

V₂ + u₂ = c₂₂ v₂ + u₂ = 12 v₂ = 12 - 9 = 3

V₃ + u₂ = c₂₃ v₃ + u₂ = 6 v₃ = 6 - 9 = -3

V₁ + u₃ = c₃₁ v₁ + u₃ = 2 u₃ = 2 - 0 = 2

V₄ + u₃ = c₃₄ v₄ + u₃ = 8 v₄ = 8 - 2 = 6

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

Таблица 2.8

G₁₂ = c₁₂ - ( u₁ + v₂ ) = 10 - ( 6 + 3 ) = 1

G₁₃ = c₁₃ - ( u₁ + v₃ ) = 4 - ( 6 + (-3) ) = 1

G₁₄ = c₁₄ - ( u₁ + v₄ ) = 7 - ( 6 + 6 ) = -5

G₂₄ = c₂₄ - ( u₂ + v₄ ) = 4 - ( 9 + 6 ) = -11

G₃₁ = c₃₁ - ( u₃ + v₂ ) = 3 - ( 2 + 3 ) = -2

G₃₂ = c₃₂ - ( u₃ + v₃ ) = 5 - ( 2 + (-3)) = 6

Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке S₁M₄ (14=-5).

Построим цикл для выбранной ячейки S₁M₄:

Среди ячеек цикла S₁M₄ , S₁M₁ , S₃M₁ ,S₃M₄ номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 25, 30} = 25 В данном случае это ячейка S₁M_1.

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика S₁ к потребителю M₁, по которому доставляется меньше всего (25) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.

От ячеек цикла с четными номерами отнимает 25. К ячейкам с нечетными номерами прибавляем 25.

Таблица 2.9

Таблица 2.10

Общие затраты на доставку всей продукции, для данного решения, составляют:

Z = 5* 9 + 2 * 25 + 12 * 10 + 6 * 30 + 7 * 25+5*8 = 610 ден. ед.

Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

(ui + vj = cij, где cij - тариф клетки SiMj)

Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем u₂ = 0

v₁ + u₂ = c₂₁ v₁ + u₂ = 9 v₁ = 9 - 0 = 9

v₂ + u₂ = c₂₂ v₂ + u₂ = 12 v₂ = 12 - 0 = 12

v₃ + u₂ = c₂₃ v₃ + u₂ = 6 v₃ = 6 - 0 = 6

v₁ + u₃ = c₃₁ v₁ + u₃ = 2 u₃ = 2 - 9 = -7

v₄ + u₃ = c₃₄ v₄ + u₃ = 8 v₄ = 8 - (-7) = 15

v₄ + u₁ = c₁₄ v₄ + u₁ = 7 u₁ = 7 - 15 = -8

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

Таблица 2.11

G₁₁ = c₁₁ - ( u₁ + v₁ ) = 6 - ( -8 + 9 ) = 5

G₁₂ = c₁₂ - ( u₁ + v₂ ) = 10 - ( -8 + 12) = 6

G₁₃ = c₁₃ - ( u₁ + v₃ ) = 4 - ( -8 + 6 ) = 6

G₂₄ = c₂₄ - ( u₂ + v₄ ) = 4 - ( 0 + 15 ) = -11

G₃₂ = c₃₂ - ( u₃ + v₂ ) = 3 - ( -7 + 12 ) = -2

G₃₃ = c₃₃ - ( u₃ + v₃ ) = 5 - ( -7 + 6 ) = 6

Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным. Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки остановим свой выбор на ячейке S₂M₄ (G₂₄=-11)

Построим цикл для выбранной ячейки S₂M₄

Ячейки образующие цикл для свободной ячейки S₂M₄:

S₂M₄, S₂M₁, S₃M₁, S₃M₄

Пусть ячейка S₂M₂ , для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла S₂M₁,S₃M₄ номера которых четные, найдем ячейку, обладающую наименьшим значением

Min = {5,5} = 5

В данном случае, таких ячеек две. Остановим выбор на ячейке S₂M₁

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика S₂ к потребителю M₁ , по которому доставляется меньше всего (5) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.

От ячеек цикла с четными номерами отнимаем 5. К ячейкам с нечетными номерами прибавляем 5.

Данные преобразования не изменяет баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.

Таблица 2.12

Таблица 2.13

Z=2*30+12*10+6*30+7*25+4*5=555 ден.ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

(ui + vj = cij, где cij - тариф клетки SiMj)

Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v₄ = 0

V₄ + u₁ = c₁₄ v₄ + u₁ = 7 u₁ = 7 - 0 = 7

V₄ + u₂ = c₂₄ v₄ + u₂ = 4 u₂ = 4 - 0 = 4

V₄ + u₃ = c₃₄ v₄ + u₃ = 8 u₃ = 8 - 0 = 8

V₂ + u₂ = c₂₂ v₂ + u₂ = 12 v₂ = 12 - 4 = 8

V₃ + u₂ = c₂₃ v₃ + u₂ = 6 v₃ = 6 - 4 = 2