Модели распределительных процессов

 

Задачи оптимального распределения взаимозаменяемых ресурсов получили название распределительных задач. Для их формулировки введём обозначения:

 

i – номер одного из взаимозаменяемых ресурсов, p – общее число взаимозаменяемых ресурсов;

a_i – общее количество i -го ресурса;

k – номер потребителя, q – общее число всех потребителей;

b_k – количество «единиц потребности» k -того потребителя;

c_ik – оценка использования единицы i -го ресурса на удовлетворение k -го потребителя;

l_ik – количество «единиц потребности» k -того потребителя, которые удовлетворяются единицей i -го ресурса;

x_ik – количество единиц i -го ресурса, используемых для удовлетворения k -го потребителя.

C учётом обозначений математическая модель распределительных процессов имеет следующий вид:

(1)

(2)

 

. (3)

 

В зависимости от конкретного характера задачи может варьироваться конкретное содержание, а также размерность исходных величин a_i, b_k, c_ik, l_ik, что в свою очередь приведёт к некоторой модификации модели. Так, например, l_ik может выражать число единиц i -го ресурса, затрачиваемых на единицу k -той потребности. Тогда ограничения (1), (2) заменяются на

.

Если при этом c_ik означает оценки единицы k -го изделия в руб./шт, то изменится и выражение для целевой функции:

 

.

 

Целевая функция может максимизироваться, например, если c_ik означает прибыль, стоимость и т.д., или минимизироваться, если эти оценки измеряют затраты, себестоимость и т.д. Форма модели также будет зависеть от выбора переменных x_ik. Вне зависимости от этих полученных модификаций модели она имеет некоторое сходство с транспортной. Однако наличие в одной из групп ограничений множителей l_ik приводит к известным осложнениям при анализе этих моделей.

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

1) простые распределительные задачи (все l_ik = const);

2) задачи с однородными ресурсами (все строки матрицы одинаковы, то есть l_ik = l_1k при различных k);

3) задачи с пропорциональными ресурсами (l_ik = a_il_1k при различных i).

Задачи для закрепления приемов моделирования

Распределительных процессов

 

Задача 1. Имеется три сорта бумаги в количествах 10, 8 и 5 т, которые можно использовать на издание четырёх книг тиражом в 8000, 6000, 15000 и 10000 экземпляров. Расход бумаги на одну книгу составляет 0,6, 0,8, 0,4 и 0,5 кг, а себестоимость (в коп.) печатания книги при использовании i -го сорта бумаги задаётся матрицей:

 

 

Определить оптимальное распределение бумажных ресурсов.

Вариант решения 1. Обозначим через x_ik количество бумаги i -го сорта, расходуемой на печать k -той книги. Тогда получим следующие ограничения на запасы бумаги (по каждому сорту):

 

(1)

 

Ограничения на производственную программу:

 

(2)

 

Требование неотрицательности переменных:

 

. (3)

 

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

 

. (4)

 

Ограничения (1-3) и целевая функция (4) составляют искомую математическую модель.

Вариант решения 2. Обозначим через x_ik количество экземпляров k -той книги, отпечатанной на бумаге i -того сорта. Тогда получим следующие ограничения на запасы бумаги (по каждому сорту):

 

.

 

Ограничения на производственную программу:

 

.

 

Требование неотрицательности переменных:

 

. Функция цели:

 

Задача 2. Авиакомпания для организации пассажирских перевозок между центром и четырьмя городами располагает тремя группами самолётов: 1-я группа – из 10 четырёхмоторных самолётов, 2-я – из 25 двухмоторных самолётов и 3-я – из 40 двухмоторных старого образца.

Минимальное (гарантированное) количество пассажиров, перевозимых одним самолётом данного типа по каждому маршруту за один месяц (в тыс. человек), и связанные с этим эксплуатационные расходы на 1 самолёт (в тыс. рублей) указаны соответственно в правых верхних и левых нижних углах каждой клетки таблицы. Там же в двух последних строках приведены: количество пассажиров, которое нужно перевезти по данному маршруту в месяц, и стоимость одного билета.

 

маршрут самолет	Город
	1,6	2,2	1,3	–
	2,8	3,0	2,4	2,0
	0,8	–	1,0	1,5
Количество пассажиров, тыс. чел.
Стоимость билета, руб.

 

Распределить самолёты по маршрутам из условия достижения максимальной прибыли авиакомпании.

Решение. Обозначим через x_ij количество самолетов i -го вида, выполняющих рейсы по j -му маршруту. Тогда получим ограничения на количество самолетов каждого вида:

(1)

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

 

(2)

 

Требование неотрицательности переменных:

 

. (3)

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

(4)

 

2.3. Задачи для самостоятельного решения

 

Задача 1. На четырёх ткацких станках с объёмом рабочего времени 200, 300, 250 и 400 станко-часов может изготавливаться ткань трёх артикулов в количествах 260, 200, 340 и 500 метров за 1 час. Составить модель формирования плана загрузки станков, если прибыль (в руб.) от реализации 1 м ткани i -го артикула при её изготовлении на k -м станке характеризуется элементами матрицы:

,

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

Задача 2. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 50, 70, 65 и 60 руб. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300 и 200 машин. Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ, в 3-й и 4-й мастерских – только на указанный вид работ. Матрица

характеризует транспортные расходы на доставку машины с i -й автобазы на k -тую ремонтную мастерскую.

Определить минимальную годовую потребность в кредитах на выполнение указанного объёма ремонтных работ по всем автобазам.

Задача 3. Четыре различных предприятия могут выпускать любой из четырёх видов продукции. Производственные мощности предприятий позволяют обеспечить выпуск продукции каждого вида в количествах (по заводам): 50, 70, 100 и 30 тыс. штук, а плановое задание составляет соответственно (по видам продукции) 30, 80, 20 и 100 тыс. шт. Матрица

 

 

характеризует себестоимость единицы k -го вида продукции при производстве его на i -м предприятии.

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

Задача 4. Имеется три предприятия (1, 2, 3), которые могут выпускать три вида продукции: А, Б, В. Каждое из них располагает двумя видами ресурсов (I, II), объёмы которых составляют для 1-го предприятия 250 и 150 единиц, для 2-го 100 и 200 единиц и для 3-го соответственно 240 и 300 единиц. Известны: нормы затрат каждого ресурса на i -м предприятии для производства единицы k -й продукции (k = 1, 2, 3); себестоимость производства единицы k -й продукции на i -м предприятии; объём производства k -й продукции, предусмотренный производственной программой.

Все указанные числовые данные приведены в следующей таблице:

 

Предпри-ятия	Продукция А	Продукция Б	Продукция В
Нормы затрат	себесто-имость	Нормы затрат	себесто-имость	Нормы затрат	себесто-имость
I ресурс	II ресурс	I ресурс	II ресурс	I ресурс	II ресурс
				1,1			2,5
	1,5			1,6			2,2	2,5
	2,2		2,5	1,2	2,4		2,4	4,2
Програм-ма выпуска

 

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

Решить ту же задачу из предположения, что I вид ресурсов жёстко закреплён за предприятием, а II вид можно передавать от одного предприятия другому.