Решение ассортиментной задачи

    Найдем  опорный план способом минимального элемента: 

    Для этого  выберем в таблице элемент (X_ij) с наименьшим ценовым показателем и заполним его значением, удовлетворяющим спросу соответствующего поставщика. Таким элементом может быть выбрана перевозка X₄₅ т.к. ее стоимость = 0.

    Следовательно, целевая функция F = 5*70 + 9*30 + 3*130 + 3*180 + 7*40 + 14*80 =

                                        = 350 + 390 + 540 + 280 + 270 + 1 120 = 2 950 

    - Опорный  план задачи - вырожденный, т.к. количество положительных поставок меньше суммы ширины и высоты образованной матрицы перевозок -1 или: (x_ij ≥ 0) < m + n -1.

    Для преодоления  вырожденности поместим в клетку X₂₅ значение = 0. Это изменение никак не повлияет на результат целевой функции, однако поможет вычислить потенциалы и произвести расчеты.  
 

    Для выполнения расчетов прибегнем к методу потенциалов: 

    Так как  все потенциалы (U и V) неизвестны, за начало расчетов возьмем строку А4, т.к. данный поставщик обладает наибольшей мощностью = 260, и присвоим U4 значение = 0. Затем рассчитаем остальные потенциалы по следующей формуле: U_j = C_{ij  -} V_j, где C_{ij –} стоимость перевозки X_ij. Соответственно: V_i = C_ij - U_j.

    В результате получим: 

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

При этом сумма потенциалов  для клеток, содержащих значения = Cij.

    Для проверки плана на оптимальность рассчитаем характеристики свободных клеток таблицы  по формуле: ∆ij = Cij - (Vi + Uj) 

    Как мы видим, некоторые характеристики являются отрицательными значениями (∆ij < 0). Экономический смысл таких характеристик, заключается в том, что они выражают возможность дальнейшей оптимизации плана на содержащиеся в них значение.

    Следовательно, данный план не оптимален. Для достижения F->min нам необходимо произвести еще один или несколько пересчетов таблицы, до тех пор, пока характеристики свободных клеток не будут содержать значения >= 0.

    Для построения нового (более оптимального плана) нам  необходимо произвести смещение значений Xij в клетках таблицы. Мы должны занять положительной поставкой клетку, имеющую  наименьшую из отрицательных  характеристик. В данном случае такой клеткой является X24 т.к. ∆24 = -7.  Для перемещения составляется цепь пересчета из которой выбирается наименьшая по значению (кол. ед. груза) поставка со знаком минус.

    Переместим  поставку из клетки 25 в клетку 24 и  пересчитаем потенциалы.  

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