Пример решения ассортиментных задач с помощью надстройки Поиск решения

В цехе пищевого предприятия вырабатывается три вида продукции П₁, П₂, П₃. Известны виды используемых ресурсов в процессе производства P₁, P₂, Р₃, нормы расхода их на единицу готовой продукции и наличие каждого ресурса. В качестве критерия оптимальности принята прибыль на единицу каждого вида продукции. Численная информация задачи представлена в табл.3.1.

 

Таблица 3.1

Виды основных ресурсов	Расход ресурсов на 1т продукции, т	Наличие ресурсов, т
П1	П2	П3
P1	0,3	0,4	0,1
P2	0,2	0,1	0,3
Р3	0,4	0,3	0,1
Прибыль на 1т, руб.

 

 

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

1. Переменные, значения которых необходимо вычислить (переменные из формальной модели – x1, x2, x3).

2. Ограничения – записанные математически ограничения из формальной модели.

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

 

Перед выполнением каких-либо вычислений в Excel, надо ввести построенную математическую модель на рабочий лист Excel (рис.3.1).

 

 

Рис. 3.1. Математическая модель в Excel

 

На рабочем листе Excel задаются параметры для поиска решения, запускается программа Поиск решения.

После выполнения итераций получается результат (рис. 3.2).

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

 

 

Рис. 3.2. Результаты поиска решения в Excel

 

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

 

Задача 2 (Транспортная задача)

Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 6-ти потребителям. Поставщики (П), потребители (М), объемы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоза приведены в таблицах.

Поставщики	Потребители	Объемы вывоза, тонн
М1	М2	М3	М4	М5	М6
П1
П2
П3
П4
Объемы завоза, т

 

При решении транспортных задач ограничениями служат: объемы вывоза (запасы) каждым поставщиком и объемы за­воза (потребности) каждого потребителя.

Обозначим неизвестную величину перевозимого груза от по­ставщиков к потребителям через x с подстрочными индексами.

Индексы показывают координаты каждой неизвестной, т. е. но­мер строки и номер столбца таблицы, на пересечении которых находится данная неизвестная.

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

Таблица 1.2

Поставщик		Потребитель	Объемы вывоза, т
М1	М2	М3	М4	М5	М6
П1	Х11	Х12	Х13	Х14	Х15	Х16
П2	Х21	Х22	Х23	Х24	Х25	Х26
П3	Х31	Х32	Х33	Х34	Х35	Х36
П4	Х41	Х42	Х43	Х44	Х45	Х46
Объемы завоза, т

 

Из данных табл. 1.2 можно заключить, что объемы запасов у каждого поставщика должны быть равны сумме переменных, находящихся в строке каждого поставщика. В математической форме это будет выражаться так:

 

(1.1)

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

(1.2)

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

 

При этом считается, что все неизвестные, содержащиеся в уравнениях (1.1), (1.2), (1.3), могут быть выражены только положительными или нулевыми числами. Неизвестные не мо­гут выражаться отрицательными числами, так как это озна­чало бы отрицательную перевозку — от потребителя к по­ставщику. Это математическое условие выражается в форме следующих неравенств:

 

(1.4)

Следовательно, задача состоит в определении таких значе­ний неизвестных, удовлетворяющих равенствам (1.1), (1.2) и неравенствам (1.4), при которых объем транспортной работы, выраженный равенством (1.3), становится минимальным.

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

По изложенной схеме можно составить модель для любого числа предприятий-поставщиков и предприятий-потребителей, выразив ее в математической форме.

В общем виде математическая модель транспортной задачи будет иметь следующее содержание. Необходимо перевести не­которое число единиц однородной продукции от нескольких по­ставщиков к нескольким потребителям. Каждому из этих по­требителей требуется определенная величина продукции и каж­дый поставщик может поставить только определенную величину этой же продукции. Принимаем следующие обозначения: т — число поставщиков; n — число потребителей; а_i — общее коли­чество продукции, выделяемой для перевозки i- мпоставщиком; b_j — общее количество продукции, необходимой j -му потребителю; с_ij — расстояние(или тариф) перевозок продукции от i -гo поставщика до j -го потребителя; x_ij — количество продук­ции, перевозимой от i - гопоставщика к j -му потребителю.

Пользуясь принятыми обозначениями, условия транспорт­ной задачи общего вида можно выразить следующим образом.

1. Каждый поставщик может отправить потребителям столько продукции, сколько он имеет, т. е. сумма поставок по каждой строке должна быть равна запасам по этой строке:

(1.5)

или

(1.5′)

 

2. Каждому потребителю необходимо получить столько про­дукции, сколько ему требуется, т. е. сумма поставок по каж­дому столбцу должна быть равна потребностям по этому столбцу:

 

(1.6)

или

(1.6′)

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

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

 

или

(1.7)

4. Запасы и потребности должны удовлетворять условиям неотрицательности:

 

(1.8)

(1.9)

5. Условиям неотрицательности должны удовлетворять и неизвестные величины

(1.10)

Перечисленные параметры являются известными величинами (а_i, b_j, с_ij). Целевая функция - транспортная работа, является критерием оптимальности, выражается в тоннокилометрах.

Поскольку решение задачи заключается в поиске такого плана перевозок, который обеспечивал бы в принятых условиях наименьшую транспортную работу, неизвестными (изменяемыми) принимаются величины x_ij — количество продук­ции, перевозимой от i - гопоставщика к j -му потребителю.