Задача оптимального раскроя бумажного полотна

 

Бумагоделательная фабрика имеет две бумагоделательные машины (БДМ), характеристики которых приведены в следующей таблице:

 

 

БДМ	Ширина бумажного полотна (м)	Производительность БДМ (тонн в месяц)	Стоимость 1 т бумаги (у.е.)
БДМ-1	3	18	8
БДМ-2	4	21	9

 

На текущий месяц фабрика получила такие заказы на выпуск бумаги:

 

 

Ширина формата (см)	Объем заказа (т)	Заказчик
80	6	Потребитель №1
120	8	Потребитель №2
80	7	Потребитель №3
80	3	Потребитель №4
120	10	Потребитель №5

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

 

Требуется определить планы выпуска и способы раскроя бумаги на каждой БДМ, обеспечивающие минимальные суммарные затраты фабрики на выполнение заказов.

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

 

Дополнительное условие: для повышения однородности бумаги каждого отдельного заказа на формат 120 см заказ должен быть полностью изготовлен на одной (любой) БДМ.

Для этого случая оптимальным является решение, соответствующее минимальной суммарной стоимости бумаги 301 у.е.

Задача о передаче данных

В информационно-вычислительной сети

 

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

Рассмотрим ИВС, функционирующую в следующих условиях. Пропускные способности линий связи в течение рассматриваемого промежутка времени считаются ограниченными. Затраты на передачу данных связаны с необходимостью оплаты используемых линий связи, причем оплата зависит как от объема переданных по линии связи данных, так и от факта ее использования (аренды).

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

ИВС задается в виде графа, в котором вершины соответствуют узлам сети, обозначаемым латинскими буквами, а дуги - каналам связи, идентифицируемым номерами.

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

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

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

 

 

    Сведения о вершинах (узлах ИВС)

 

Вершина (узел ИВС)	Примечание
A	Источник данных
B	Транзитный узел
C	Получатель данных объемом 10 и.е.
D	Транзитный узел
E	Транзитный узел
F	Получатель данных объемом 6 и.е.

 

 

                   Сведения о дугах (линиях связи)

 

№	Связываемые вершины	Пропускная способность (и.е.)	Стоимость передачи 1 и.е. (у.е.)	Стоимость аренды линии связи (у.е.)
1	A, B	25	6	10
2	A, E	15	1	6
3	B, C	8	3	7
4	B, D	17	1	6
5	C, D	7	5	7
6	C, F	11	4	10
7	D, F	9	2	6
8	E, D	12	2	7
9	E, F	5	5	7

 

 

Оптимальное решение задачи обеспечивает затраты на передачу данных, равные 157 у.е.

Список использованной литературы

 

1. Фратер Г. Excel 5.0: Пер. с нем. Киев: Торгово-издательское бюро BHV, 1995. 560 с.

2. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. СПб.: BHV-Санкт-Петербург, 1997. 384 с.

3. Поляков В.В., Карпов А.В., Кузнецов В.А. Решение оптимизационных задач в среде табличного процессора Quattro Pro: Методические указания. Петрозаводск: Изд-во ПетрГУ, 1994. 37 с.

 

 

Владимир Витальевич Поляков

 

Сергей Тимофеевич Коржов

 

Александр Вениаминович Карпов

 

Решение задач математического программирования

в среде табличного процессора Excel

 

Методические указания

 

 

Редактор Л.П.Соколова

 

 

 

Подписано к печати 10.10.98. Формат 60x841/16. 

Бумага типографская. Офсетная печать. 1,1 уч.-изд. л. 

7 усл. кр.-отт. л. Тираж 150 экз. Изд. № 135 “С”.

 

Издательство Петрозаводского государственного

университета

 

185640, г. Петрозаводск, пр. Ленина, 33