Пример решения ассортиментных задач с помощью надстройки Поиск решения
В цехе пищевого предприятия вырабатывается три вида продукции П1, П2, П3. Известны виды используемых ресурсов в процессе производства P1, P2, Р3, нормы расхода их на единицу готовой продукции и наличие каждого ресурса. В качестве критерия оптимальности принята прибыль на единицу каждого вида продукции. Численная информация задачи представлена в табл.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-мпоставщиком; bj — общее количество продукции, необходимой j-му потребителю; сij —расстояние(или тариф) перевозок продукции от i-гo поставщика до j-го потребителя; xij — количество продукции, перевозимой от i-гопоставщика к j-му потребителю.
Пользуясь принятыми обозначениями, условия транспортной задачи общего вида можно выразить следующим образом.
1. Каждый поставщик может отправить потребителям столько продукции, сколько он имеет, т. е. сумма поставок по каждой строке должна быть равна запасам по этой строке:
(1.5)
или
(1.5′)
2. Каждому потребителю необходимо получить столько продукции, сколько ему требуется, т. е. сумма поставок по каждому столбцу должна быть равна потребностям по этому столбцу:
(1.6)
или
(1.6′)
3. С учетом этих условий требуется составить такой план перевозок, при котором объем транспортной работы характеризовался бы наименьшей величиной. Для любого варианта плана перевозок объем транспортной работы получается суммированием произведений каждой поставки на соответствующие им расстояния.
Так как результатом решения задачи является составление плана перевозок, имеющего минимальный объем транспортной работы, то этот объем можно представить в таком виде:
или
(1.7)
4. Запасы и потребности должны удовлетворять условиям неотрицательности:
(1.8)
(1.9)
5. Условиям неотрицательности должны удовлетворять и неизвестные величины
(1.10)
Перечисленные параметры являются известными величинами (аi , bj, сij). Целевая функция - транспортная работа, является критерием оптимальности, выражается в тоннокилометрах.
Поскольку решение задачи заключается в поиске такого плана перевозок, который обеспечивал бы в принятых условиях наименьшую транспортную работу, неизвестными (изменяемыми) принимаются величины xij — количество продукции, перевозимой от i-гопоставщика к j-му потребителю.