Построение кольцевых маршрутов
Коммерческая деятельность обычно связана с командировками, поездками по городам для заключения сделок. Расстояния между любой парой множества из nгородов известны и составляют 
.Если прямого маршрута между городами i и j не существует, то допускают, что 
.
Коммерсант, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута
была бы наименьшей.
Экономико-математическая постановка этой задачи может быть представлена как задача целочисленного линейного программирования.
Переменные определим следующим образом:
=1, если коммивояжер переезжает из города i в город j 
; в противном случае =0.
Задача заключается в определении матрицы целых неотрицательных значений переменных, минимизирующих целевую функцию вида
, 
при ограничениях:
1) для въезда в город j только один раз: 
, 
2) для выезда из города i только один раз: 
, 
В такой постановке задача коммивояжера представляет собой задачу целочисленного линейного программирования. Действительно, условия исключают в оптимальном решении значения =1 как не имеющие смысла, а ограничения требуют:
1) чтобы маршрут включал только один въезд в каждый город;
2) чтобы маршрут включал лишь один выезд из каждого города, а целевая функция включала длину маршрута коммивояжера;
3) чтобы маршрут образовывал контур, проходящий через все города.
Таким образом формируется экономный вариант маршрута в виде кольца.
Решение этой задачи строится, например, методом ветвей и границ целочисленного программирования.
Контрольные вопросы
1. Как формулируется общая задача линейного программирования (ОЗЛП)?
2. Какие задачи коммерческой деятельности можно представить в виде ОЗЛП?
3. Какие показатели хозяйственной деятельности предприятий имеют линейную форму связи?
4. Какие показатели коммерческой деятельности могут входить в постановку задач линейного программирования?
5. Приведите пример формализации задачи коммерческой деятельности.
Задачи
1. Постройте экономико-математическую модель оптимизации плана хозяйственной деятельности предприятия розничной торговли, определите объем продажи товаров 
по каждой товарной группе, обеспечивающий максимум прибыли П при заданной величине товарооборота 
с учетом следующих данных:
n- количество товарных групп;
j - номер товарной группы ;
- средняя розничная цена единицы товара j-й группы, руб.;
- объем продажи j-й товарной группы, руб.;
- плановый объем товарооборота;
- уровень издержек обращения, % к товарообороту j-й товарной группы;
- уровень торговой скидки, % к товарообороту j-й товарной группы;
S - полезная площадь торговых залов, 
;
-полезная площадь отдела, в котором продаются товары j-й товарной группы, ;
- норматив товарооборота j-й товарной группы на 1 площади залов, руб./ ;
-рабочее время продавцов квалификации l, 
;
- норматив товарооборота по j-й товарной группе на группу продавцов квалификации l в единицу времени, руб./ч;
- издержки обращения по статье h, руб.;
-плановый норматив издержек обращения по статье h, руб.;
h-номер статьи издержек обращения, 
(h=1 соответствует заработной плате, h=2 — транспортным расходам и т.д.);
Н - количество статей издержек обращения;
- плановый уровень товарооборота j-й товарной группы.
2. Постройте экономико-математическую модель оптимизации плана хозяйственной деятельности предприятия розничной торговли, позволяющую определить товарооборот по каждой товарной группе ,обеспечивающий максимальный объем товарооборота Q при заданной величине прибыли 
и условиях задачи 1.
3. Торговое предприятие в течение месяца осуществляет реализацию nтоварных групп 
, каждая из которых включает r видов товара 
. На реализацию товаров r-го вида каждой товарной j-й группы заданы верхний 
и нижний 
пределы товарооборота. Предприятию установлен месячный план товарооборота (тыс. руб.).
Постройте экономико-математическую модель, позволяющую получить оптимальный месячный план продажи товаров 
обеспечивающий максимальную прибыль П при следующих условиях:
- площадь торговых залов на единицу товарооборота в натуральном выражении при реализации rвида товара из j-й группы;
S -производственная площадь торгового предприятия, ;
- месячный фонд времени работы продавцов квалификации l, , чел.-ч;
- норматив товарооборота на группы продавцов квалификации l при реализации r-го вида товара из j-й группы в единицу времени;
-торговая прибыль от продажи единицы r-го вида товара из j-й группы, руб.;
- средняя розничная цена r-го вида товара из j-й группы, руб.;
-месячный лимит статьи h издержек обращения, , руб.;
- расходы по статье h издержек обращения на 1 тыс. руб. товарооборота по реализации r-го вида товара из j-й группы, руб.;
- плановый объем товарооборота.
4. Торговое предприятие в течение месяца осуществляет продажу nтоварных групп, каждая из которых включает rвидов товара . На реализацию товара r-го вида каждой товарной j-й группы заданы верхний и нижний пределы товарооборота.
Постройте экономико-математическую модель, позволяющую получить оптимальный месячный план продажи х по каждому виду товара 
, обеспечивающий при заданной величине торговой прибыли максимальный объем товарооборота Q по условиям задачи 3.
5. Постройте экономико-математическую модель организации снабжения товарами предприятий розничной торговой сети в городе, обеспечивающую минимум затрат на транспортные расходы Cпо завозу товаров при следующих условиях:
R -количество наименований товарных позиций;
r - номер наименования товара, ;
m - количество розничных торговых предприятий;
i - номер розничного торгового предприятия, 
;
n - количество оптовых торговых предприятий;
j - номер оптового торгового предприятия, ;
- запасы r-го товара на j-м оптовом предприятии;
- объем реализации товара r-го наименования на i-м розничном предприятии;
- спрос населения на товар r-го вида;
- стоимость перевозки единицы товара r-го вида из j-го оптового
торгового предприятия в i-е розничное;
- объем перевозок товаров r-го вида из j-го оптового в i-е розничное торговое предприятие.
6. Постройте экономико-математическую модель организации снабжения товарами предприятий розничной торговли в городе, позволяющую получить максимальный доход по условиям задачи 5.
7. Постройте экономико-математическую модель развития предприятий розничной торговли сети в регионе, обеспечивающую минимум затрат на поездку жителей из населенных пунктов в торговые центры при следующих условиях:
n - число населенных пунктов;
j - номер населенного пункта, ;
- численность населения j-го пункта;
m - количество торговых центров;
i - номер торгового центра, ;
- затраты на поездку одного жителя из пункта j в пункт i торгового центра;
- численность населения j-го пункта, обслуживаемого в i-м центре;
R- количество наименований товарных позиций;
- норма обеспеченности одного жителя товаром r-вида, ;
- объем реализации товара rв i-м торговом центре;
- спрос всего населения в пункте j на товары.
8. Постройте экономико-математическую модель развития предприятий розничной торговли в регионе, обеспечивающую получение максимального дохода по условиям задачи 7.
9. Постройте экономико-математическую модель размещения предприятий розничной торговли в регионе, имеющем n населенных пунктов, среди которых следует выбрать такие m, где будут расположены торговые центры, которые представляли бы населению соответствующие rтовары в объеме 
и ассортименте R, соответствующие нормам обеспеченности всего населения региона в целом S, и при этом средневзвешенные затраты времени на поездку T были бы минимальны с учетом следующих данных:
R -количество наименований товарных позиций;
r - номер наименования товара, ;
- норма обеспеченности одного человека товарами rвида;
j - номер населенного пункта, ;
- численность населения в j-м пункте;
- минимально допустимая численность населения, обслуживаемая торговым центром;
i - номер предприятия розничной торговли, ;
S- объем спроса на товары всего населения региона;
- затраты времени на поездку из j-го пункта до i-го торгового центра;
-максимально допустимые затраты времени на поездку до торгового центра;
, если i-й пункт прикреплен к i-му центру, в противоположном случае он равен 0.
10. Постройте экономико-математическую модель размещения предприятий розничной торговли, позволяющую минимизировать транспортные издержки на доставку товаров по условиям задачи 9.