Мет.моделирования и прогнозирования эк-ки

Отметим, наконец, что если переменная xk не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными uk и vk, приняв xk = uk – vk .

2.2. ОПТИМИЗАЦИОННЫЕ МОДЕЛИ ЗАДАЧ ТОРГОВОЙ ДЕЯТЕЛЬНОСТИ

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

Многие задачи, возникающие сфере коммерции и торговой деятельности носят оптимизационный характер (рис.2.1).

Ниже в качестве примеров приводятся некоторые оптимизационные модели задач торговой и коммерческой деятельности.

Модель размещения розничной торговой сети Спрос на различные товары зависит от населения, товары в ма-

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

Введем обозначения:

i – номер склада (базы);

n – число всех складов (баз); r – вид товара;

R – число всех видов товара;

j – номер торговой точки (магазина); m – число торговых точек;

q – номер варианта развития торговой точки;

Qj – число возможных вариантов развития j -й торговой точки;

Nir – количество r -го вида товара на i -м складе;

M qjr – количество реализуемой продукции r -го вида в j -й тор-

говой точке согласно q -му варианту;

Pjq – приведенные затраты j -й торговой точки согласно q -му варианту;

ного обслуживания) в j -й торговой точке, развивающейся согласно q -

му варианту;

xqj – искомая величина, равная 1, если в j -й торговой точке выбирается q -й вариант, и равная 0 в противном случае;

xirj – объем перевозки r -й продукции из i -го склада в j -ю тор-

говую точку.

В этой модели размещения розничной торговой сети требуется

и выполняются условия:

вывоз товаров из складов должен быть в пределах возможного

j1

поставляемые товары должны соответствовать мощностям торговых точек

объем поставляемой продукции должен соответствовать потреблению

должен быть выбран только один вариант развития торговой

точки

выражении при реализации единицы s -го вида товара из r -й группы;

мальная прибыль

R Sr

Prsxrs max

r1s 1

ивыполняются ограничения:

по имеющимся трудовым ресурсам

r1s 1

по имеющимся видам площадей

r1s 1

по имеющимся видам издержек обращения

R Sr

Q1 qrsxrs Q2, r 1s 1

по выполнению плана ассортимента товаров

rs xrs rs.

Решая полученную модель как задачу линейного программирования, получаем оптимальный план реализации товаров xrs и товаро-

R Sr

оборота Q qrsxrs. Прибыль торгового предприятия равна разно-

r 1s 1

сти между валовым доходом и издержками обращения. Валовый доход может измеряться суммой торговых скидок, составляющих определен-

ка; Crs - суммарные издержки обращения на единицу s -го вида товара

из r -й группы.

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

2.3. ОПТИМИЗАЦИЯ ТРАНСПОРТНЫХ ПОТОКОВ

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1, A2, ..., Аm в n пунктов назначения В1, В2, ..., Вn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки [1, 14].

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через cij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через аi – запасы груза в i-м пункте отправления, через bj – потребности в грузе в j-м пункте назначения, а через хij – количество единиц груза, перевозимого из i-го пункта отправления в j-Й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

Поскольку переменные xij (i 1,m; j 1,n) удовлетворяют сис-

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

Всякое неотрицательное решение систем линейных уравнений

(2.6) и (2.7), определяемое матрицей X ( xij ); (i 1,m; j 1,n), назы-

вается планом транспортной задачи.

План X* ( x*ij ) (i 1,m; j 1,n), при котором функция (2.5) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные задачи записывают в виде табл.2.1. Таблица 2.1

Исходные данные транспортной задачи

j 1

потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

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

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

(2.9).

гаются равными нулю: cm 1j 0 ( j 1,n). Этим задача сводится к

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

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

Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2.6) и (2.7) равно n + m. Так как мы предполагаем, что выполняется условие (2.9), то число линейно независимых уравнений равно n + m – 1. Следовательно, опорный план транспортной задачи может иметь не более n + m – 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n + m – 1, то план является невырожденным, а если меньше

– то вырожденным.

Для определения опорного плана существует несколько методов: метод северо-западного угла, метод минимального элемента, метод аппроксимации Фогеля и др. Как и для всякой задачи линейного про-

граммирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать стандартные методы линейного программирования, например, симплекс-метод. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждая неизвестная входит лишь в два уравнения систем (2.6) и (2.9) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы: метод потенциалов, метод дифференциальных рент и др.

Определение опорного плана транспортной задачи

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

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

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

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

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

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

В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-нибудь одно). В итоге, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку.

Указанные выше условия гарантируют получение n+m-1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x11 («северо-западный угол») и заканчивается клеткой для неизвестного xmn, т. е. идет как бы по диагонали таблицы.

Пример 2.2. На три базы A1, A2, A3 поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения B1, B2, B3, B4, B5 соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза указаны в следующей табл. 2.2. Найти план перевозок данной транспортной задачи методом северо-западного угла.

Таблица 2.2

Исходные данные задачи

Решение. Здесь число пунктов отправления m = 3, а число пунктов назначения n = 5. Следовательно, опорный план задачи определяется числами, стоящими в 5 + 3 – 1 = 7 заполненных клетках.

Заполнение таблицы начнем с клетки для неизвестного x11, т. е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта A1 больше, чем потребности пункта B1, то полагаем x11 = 60, записываем это значение в соответствующей клетке табл.2.3 и временно исключаем из рассмотрения столбец B1, считая при этом запасы пункта А1 равными 80.

Рассмотрим первые из оставшихся пунктов отправления А1 и назначения В2. Запасы пункта А1 больше потребностей пункта В2. Положим x12 = 70, запишем это значение в соответствующей клетке табл.6.3 и временно исключим из рассмотрения столбец B2. В пункте A1 запасы считаем равными 10 ед. Снова рассмотрим первые из оставшихся пунктов отправления А1 и назначения В3. Потребности пункта В3 больше оставшихся запасов пункта A1. Положим x13 = 10 и исключим из рассмотрения строку A1. Значение x13 = 10 запишем в соответствующую клетку табл. 2.3 и считаем потребности пункта В3 равными 110 ед.

Теперь перейдем к заполнению клетки для неизвестного x23 и т. д. Через шесть шагов остается один пункт отправления A3 с запасом груза 100 ед. и один пункт назначения B5 с потребностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая x35 = 100 (табл.2.3). В результате получаем опорный план

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет S = 2 60 + 3 70 + 4 10 + 1 110 + 4 70 + 7 60 + 2 100 = 1370.

Определение оптимального плана транспортной задачи

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