Решение задачи распределения ресурсов

Значительное число задач в экономике составляют задачи распределения ресурсов. Наиболее часто математической моделью таких задач является задача линейного программирования.

Суть задачи о распределении ресурсов.

Предположим, имеются какие-либо ресурсы (сырье, рабочая, сила, оборудование):

R₁, R₂, … , R_m (5.42)

в количествах, соответственно:

b₁, b₂, … , b_m (5.43)

единиц ресурсов.

С помощью ресурсов R₁, R₂, … , R_m могут производится различные товары

T₁, T₂, … , T_m (5.44)

Для производства одной единицы товара T_j необходимо a_ij единиц ресурса R_i (i = 1, 2, … , m; j = 1, 2, … , n), где m – количество ресурсов,n – количество видов продукции).

Каждая единица ресурса R_iстоит d_i рублей (i = 1, 2, … , m). Каждая единица товара может быть реализована по цене с_j(j = 1, 2, … , n).

Количество произведенных единиц должно быть ограничено спросом, т.к. рынок не может поглотить больше, чем k_j единиц товара T (j = 1, 2, …, n).

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

Введем некоторые обозначения:

x₁, x₂, … , x_n – количества товаров T₁, T₂, … , T_n , запланированных к производству.

Условия спроса налагают на эти величины следующие ограничения:

x₁ £ k₁; x₂ £ k₂; … ; x_n £ k_2n ; (5.45)

Нельзя израсходовать ресурсов больше, чем имеется в наличии. Следовательно получаем ограничения по использованию ресурсов:

, (5.46)

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

Теперь необходимо выразить прибыль L в зависимости от элементов решения x₁, x₂, … , x_n, т.е. планируемых объемов производства продукции. Для этого сначала необходимо определить себестоимость товара.

Себестоимость s_j единицы товара T_j будет равна:

s_j = a_1jd₁ + a_2jd₂ + … + a_mjd_m­,, (5.47)

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

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

s₁, s₂, … , s_n (5.48)

Прибыль от реализации одного какого-либо вида продукции q_i будет рассчитываться по формуле:

q_i = c_i – s_i; (5.49)

где c_i – продажная (отпускная) цена какого-либо вида продукции, s_i– себестоимость вида продукции; i = 1, 2, …, n; n – кол-во видов продукции.

В результате вычисления прибыли от реализации по каждому виду продукции получим набор значений:

q₁, q₂, … , q_n (5.50)

Общая прибыль от реализации всех видов продукции составит:

L = q₁x₁ + q₂x₂ + … + q_nx_n , (5.51)

где q_i– прибыль от реализации единицы продукции; x_i – объем производства данного вида продукции.

Задача сводится к тому, чтобы выбрать такие неотрицательные значения переменных x₁, x₂, … , x_n (объемы производства продукции по каждому виду), чтобы удовлетворялись наложенные ограничения по ресурсам и соблюдались условия спроса на производимую продукцию, и при этом была бы получена максимальная прибыль, т.е. целевая функция принимала бы максимально возможное значение.

Для решение задачи распределения ресурсов используют симплекс-метод решения задач линейного программирования.

Пример решения

В Excel имеется стандартных механизм разрешения подобных задач заключенный в надстройке «Поиск решения». Для его использования необходимо активировать данную надстройку: Сервис ® Надстройки …

Далее активировать элемент списка Поиск решения, как это показано на рисунке выше и нажать Ok. После этого опция Поиск решения станет доступна в меню Сервис.

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

Какие же формулы должны быть введены в ячейки, отмеченные черным цветом? Это формулы, рассчитывающие соответствующие значения математических выражений, рассмотренных выше:

1. В ячейку E8 должна быть введена формула, рассчитывающая целевую функцию (ЦФ). Целевая функция, как было рассмотрено выше, для задачи распределения ресурсов представляет собой сумму произведений переменных «прибыль от реализации единицы продукции» (q_i) на объем производства данной продукции (x_i), т.е. L = q₁x₁ + q₂x₂ + … + q_nx_n.

Т.к. q_i - коэффициенты целевой функции, представленные в ячейках диапазона B8:D8, а x_i – объемы производства, которые будут после решения задачи представлены в ячейках B5:D5, то формула расчета целевой функции должна рассчитывать сумму произведений ячеек B5:D5 на B8:D8.

Для расчета суммы произведений диапазонов ячеек предусмотрена математическая функция Excel «СУММПРОИЗВ».

= СУММПРОИЗВ(Список перемножаемых диапазонов)

Для расчета целевой функции необходимо в ячейку E8 ввести формулу

=СУММПРОИЗВ(B$5:D$5;B8:D8)

Теперь необходимо ввести ограничения использования ресурсов – систему неравенств-ограничений, исходные данные которой должны быть представлены в секции «Ограничения».

Каждое неравенство выражает ограничение объемов производства различных видов продукции имеющимся количеством данного ресурса и имеет левую и правую часть. Левая часть неравенства, как уже было рассмотрено представляет собой сумму произведений количества ресурса, требуемого на производство единицы продукции, (a_ij) на объем производства данного вида продукции (x_i). Правая часть неравенства отражает количество ресурса, которое имеется в распоряжении.

Т.к. объемы производства представлены в диапазоне ячеек B5:D5, а количество ресурса, необходимое для производства единицы продукции, представлено в диапазонах B12:D12 (для ресурса «Ресурс1»), B13:D13 (для ресурса «Ресурс2»), B14:D14 (для ресурса «Ресурс3»), то в ячейках E12:E14 соответственно должны быть формулы:

E12 = СУММПРОИЗВ(B$5:D$5; B12:D12)

E13 = СУММПРОИЗВ(B$5:D$5; B13:D13)

E14 = СУММПРОИЗВ(B$5:D$5; B14:D14)

т.е. суммы произведений соответствующих ячеек.

После ввода формул в ячейки форма примет следующий вид:

Если включить режим отображения формул (Сервис ® Параметры … ® Вид ® Параметры окна ® Формулы ® Ok), то форма примет следующий вид:

Отключить режим отображения формул можно аналогичным способом.

После ввода формул необходимо ввести исходные данные задачи.

Исходные данные

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

,

где первое неравенство – ограничение по ресурсу1, второе – по ресурсу2, третье – по ресурсу3. Правая часть неравенств отражает ограничение по использованию данного ресурса для производства.

Целевая функция выглядит следующим образом:

L = 80x₁ + 100x₂ + 50x₃

Из условия задачи видно, что значения коэффициентов при переменных первого уравнения необходимо ввести в ячейки B12, C12, D12 соответственно. Значения коэффициентов второго уравнения необходимо ввести в ячейки B13, C13, D13 формы, коэффициенты третьего уравнения – в ячейки B14, C14, D14.

Правую часть неравенств уравнений необходимо ввести соответственно для первого уравнения – в ячейку G12, для второго – в ячейку G13, третьего – G14.

В ячейки F12:F14 введем знаки неравенств <= (меньше или равно). Следует отметить, что введенные знаки никак не влияют на процесс расчета, однако они необходимы для понимания представленных в форме данных.

Введем коэффициенты при целевой функции в ячейки В8:D8. В ячейку F8 введем направление поиска оптимального значения целевой функции: минимум или максимум (значение данной ячейки также необходимо только для понимания представленных данных и не влияет на ход расчета).

В результате ввода данных форма примет следующий вид:

Теперь необходимо задействовать механизм поиска оптимального решения (значений x₁, x₂, x₃ для получения максимального значения целевой функции L): Сервис ® Поиск решения….

Появившийся в результате диалог «Поиск решения» (см. ниже) необходим для определения параметров расчета и его настроек:

1. В поле «Установить целевую ячейку» необходимо указать $E$8.

Рис.Диалог «Поиск решения»

2. Активировать переключатель «максимальному значению», что значает, что будет производится максимизация значения целевой функции.

3. В поле «Изменяя ячейки» указать диапазон ячеек, в которые необходимо будет поместить значения объемов производства для каждого вида продукции, т.е. необходимо указать диапазон B5:D5.

4. В секции «Ограничения:» необходимо добавить настройки ограничений расчета, для чего необходимо:

1. Нажать кнопку «Добавить»

и в появившемся диалоге заполнить параметры ограничения для каждого неравенства:

- в поле «Ссылка на ячейку» выбрать ячейку, содержащую формулу левой части соответствующего неравенства, т.е. для первого неравенства выбрать ячейку E12;

- далее знак ограничения оставить без изменений;

1.в поле «Ограничение» необходимо ввести имя ячейки, содержащей значение правой части неравенства (для первого неравенства это G12).

2. Рассмотренную в п. 1 процедуру повторить для каждого неравенства.

Таким образом, после ввода параметров диалог «Поиск решения» примет следующий вид:

5. Нажать кнопку «Параметры» диалога «Поискрешения», что приведет к активации диалога «Параметры поиска решения».

В появившемся диалога необходимо все оставить без изменения за исключением переключателя «Линейная модель» ® Нажать Ok.

6. В диалоге «Поискрешения» нажать кнопку «Выполнить». Если оптимальное решение существует на экран будет выведен следующий
диалог.

Диалог свидетельствует об успешном поиске оптимального решения.

Предложенное «Сохранить найденное значение» означает, что найденные значения объемов производства x1, x2, x3, максимизирующие целевую функцию прибыли будут помещены в соответствующие ячейки.

«Восстановить исходные значения» – означает отмену проведенного расчета.

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

Результат расчета представлен на следующем рисунке:

Из рисунка видно, что максимальная прибыль составит 20 денежных единиц, при этом необходимо запланировать выпуск продукции Продукция1 в объеме 12 единиц, продукции Продукция2– в объеме 8 единиц, а продукцию Продукция3 не производить вовсе в условиях установленных ограничений на использование ресурсов.

Решение транспортной задачи

Транспортная задача – это задача о минимизации расходов на перевозку грузов. Классическая транспортная задача формулируется следующим образом.

Имеется некоторое количество (m) пунктов отправления:

A₁, A₂, …, A_m (5.52)

в котором сосредоточены запасы какого-либо однородного товара в количествах

a₁, a₂, …, a_m (5.53)

Имеется также n пунктов назначения:

B₁, B₂, …, B_n (5.54)

подавших заявки определенное количество товара соответственно:

b₁, b₂, …, b_n (5.55)

Предполагается, что сумма всех заявок равна сумме всех запасов

. (5.56)

Стоимость перевозки товара из пункта отправления i в пункт назначения j известна для всех вариантов перевозок и равна с_ij­. Таким образом имеется матрица стоимостей перевозок:

. (5.57)

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

Так как показателем эффективности является стоимость перевозок, то данную задачу можно назвать транспортной задачей по критерию стоимости.

Рассмотрим математическую формулировку задачи.

Введем некоторые обозначения:

x_ij – количество груза, отправляемого из i-го пункта отправления А_i в j-й пункт назначения B_j (i = 1, …, n; j = 1, …, m). Переменные x₁₁, x₁₂, …, x_mn должны быть неотрицательны и должны удовлетворять следующим условиям:

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

(5.58)

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

(5.59)

3. Стоимость всех перевозок должна быть минимальной.

Методы решения транспортной задачи не требуют манипуляций с симплекс-таблицами, а сводятся к более простым операциям непосредственно с таблицей, где в определенном порядке записаны все условия транспортной задачи.

В транспортной таблице записываются:

- пункты отправления (заголовки строк) и назначения (заголовки столбцов);

- запасы, имеющиеся в пунктах отправления (последний столбец таблицы);

- заявки, поданные пунктами назначения (последняя строка таблицы);

- стоимости перевозок из каждого пункта отправления в каждый пункт назначения (табличная часть).

		Пункты назначения
		B1	B2	…..	Bn	Запасы аi
Пункты отправления	A1	C11	C12	…..	C1n	a1
A2	C21	C22	…..	C2n	a2
.   .	. . .	. . .	. . .	. . .	. . .
An	Cm1	Cm2	. . .	Cmn	am
	Заявки bi	b1	b2	. . .	bn

Для решения транспортной задачи используется надстройка «Поиск решения» (Сервис ® Надстройки ® Поиск решения). Перед использованием механизма поиска решения необходимо ввести исходные данные и расположить их на листе соответствующим образом. Рассмотрим процесс решения транспортной задачи на примере.

Пример решения

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

Наименование товара	Спрос, ед.
Товар1
Товар2
Товар3
Товар4	5 000
Товар5	10 000

Товары находятся в разных городах на разных оптовых базах. Запасы товаров на складах в различных городах представлены ниже в таблице.