Найти кратчайшее расстояние от всех точек до точек 1, 3, 5, 8, 12 сети, изображенной на рисунке 20.

122. Пронумеровать узлы сети, изображенной на рисунке 21, так, чтобы для любой ее ориентированной дуги (i, j) имело место неравенство i < j.

 

123. Составить самостоятельно задачу по определению кратчайших расстояний для 16 точек и выполнить задачу 121.

124. Задана транспортная сеть, на которой указаны пункт отправления A и пункт назначения В (рис. 22). Между ними имеется много других пунктов. Некоторые соединены между собой участками пути. Над каждым участком транспортной сети поставлены цифры, указывающие расстояния между данными пунктами. Требуется составить маршрут минимальной длины из пункта А в пункт В.

125. Владелец озера должен решить, сколько форели вылавливать и продавать каждый год. Если он продает х форелей в течение года t, то доход составляет r(x). Стоимость отлова х форелей в течение года есть функция c(x,b) от х – количества вылавливаемых форелей и b – количество форелей на начало года. Конечно, форель размножается. Предположим, что количество форелей к началу каждого года возрастает на 20 % по сравнению с количеством на конец предыдущего. Предположим также, что в начале первого года в озере 10000 форелей. Применяя рекурсию по методу динамического программирования, определить план отлова, который максимизирует чистую суммарную прибыль за период T лет.

 

126. Известны прогнозные значения потребления электроэнергии на ближайшие T лет, а именно - прогнозируемая мощность потребления электроэнергии в год t. Каждый год необходимо принимать решение, на сколько нужно увеличить (или уменьшить) мощность выработки электроэнергии. Пусть - стоимость увеличения мощности на х кВт ч в году t. Так как мощность может сокращаться, х может быть отрицательной величиной. В течение года 10% ранее выработанной, но не использованной электрической мощности теряется (в первый год потери не происходят). Себестоимость выработки i единиц электрической мощности в год t составляет . В начале первого года уровень вырабатываемой электрической мощности составляет 100000 кВт ч. Сформулируйте рекурсивное соотношение для метода динамического программирования, позволяющее компании найти решение, удовлетворяющее потребностям в электроэнергии на ближайшие T лет с минимальными затратами.

 

127. Руководство фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях . Каждое предприятие представило на рассмотрение различные проекты наращивания своих производственных мощностей, реализацию каждого из которых характеризуют величины (в условных денежных единицах) суммарных затрат C и суммарных доходов R (см. таблицу 14). Возможность отказа фирмы от наращивания производственных мощностей учтена проектом, для которого С =0 и R =0. Для расширения производства на всех трех предприятиях фирма выделяет средства в объеме 5 условных денежных единиц. Их нужно распределить между предприятиями так, чтобы с учетом представленных проектов получить максимальный доход от инвестиций.

 

Таблица 14.

 

Номер проекта	A1	A2	A3
C1	R1	C2	R2	C3	R3
	–	–			– –	– –

128. Пусть планируется деятельность некоторой системы S промышленных предприятий на некоторый период времени T, состоящий из k хозяйственных лет , причем . В начале периода T на развитие предприятий выделены основные средства D. В начале каждого хозяйственного года производиться финансирование всей системы предприятий, т.е. выделяется доля основных средств. Известны первоначальное состояние системы , характеризуемое количеством средств, уже вложенных в предприятия, и конечное состояние , характеризуемое всей дополнительно вложенной суммой D. Как следует распределить по предприятиям и годам основные средства D, чтобы к концу периода T суммарный доход W от всей системы предприятий был максимальным?

129. В судно грузоподъемностью 5 тонн загружаются предметы 4-х наименований. Таблица 9 содержит данные о весе одного предмета (в тоннах) и прибыли (в тыс. рублей), получаемой от одного загруженного предмета. Как нужно загрузить судно, чтобы получить оптимальную прибыль.

Таблица 9.

Предмет i	Вес 1 предмета (тоннах)	Прибыль 1 предмета (´1000 рубл.)

 

130. Консервный комбинат имеет в своём составе 5 заводов, на каждом из которых может изготовляться четыре вида консервов. Мощности заводов равны 300, 250, 350, 420 и 180 тыс. банок в день. Ежедневные потребности в консервах каждого вида также известны и составляют 430, 500, 430 и 440 т. Себестоимость 1 т каждого вида консервов на каждом заводе задана матрицей

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

131. В пять газетных киосков поставляется печатная продукция с трёх оптовых баз. Ежедневно с баз вывозится 150, 230 и 340 единиц продукции соответственно. Киоски могут разместить 170, 160, 100, 120 и 180 единиц продукции. Тарифы перевозок единицы продукции с каждой базы в киоски задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок будет минимальной.

132. Мёд закупается на четырёх пасеках в количествах 230, 320, 520 и 210 т и хранится на пяти складах. Складские помещения могут вместить по 300 т мёда каждое. Затраты, связанные с закупкой и доставкой 1 т мёда, задаются матрицей

Составить такой план доставки мёда на склады, чтобы затраты были минимальными.

133. Мебельная фабрика имеет в своём составе три филиала, которые производят наборы мягкой мебели в количествах, равных 400, 600 и 500 единиц. Эту продукцию получают четыре торговые точки, расположенные в разных местах. Их торговые площади позволяют размещать 500, 350, 450 и 400 комплектов соответственно. Стоимость перевозок единицы продукции от каждого филиала соответствующим потребителям задаётся матрицей

Составить такой план поставок, при котором общая стоимость перевозок будет минимальной.

134. Фирма имеет пять торговых точек по продаже мороженого с объемом холодильников 120, 130, 100, 90 и 150 кг. Мороженое завозится с четырёх комбинатов в количестве 140, 110, 175 и 165 кг соответственно.

Затраты, связанные с закупкой и доставкой 1кг мороженого, задаются матрицей

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

135. Фирма обратилась в три кадровые агентства за строительными рабочими для своих четырёх строек. На стройки требуется 53, 47, 98 и 33 рабочих соответственно. Кадровые агентства нашли для фирмы 80, 90 и 70 рабочих. Причём транспортные расходы на одного рабочего в зависимости от нахождения места его работы и расположения кадрового агентства будут определяться матрицей тарифов

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