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

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