Методические указания Петрозаводск Издательство Петрозаводского университета 1998 (стр. 1 из 4)
Петрозаводский государственный университет
Решение задач математического
программирования в среде
табличного процессора Excel
Методические указания
Петрозаводск
Издательство Петрозаводского университета
1998
Печатаются по решению редакционно-издательского совета
Петрозаводского государственного университета
Составители: к.т.н., доцент Поляков В.В.,
к.т.н., доцент Коржов С.Т.
к.э.н., доцент Карпов А.В.
Рецензент: к.т.н., доцент Богоявленский Ю.А.
Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. Пример оптимизационной задачи . . . . . . . . . . . . . . . . 5
2. Математическая модель задачи . . . . . . . . . . . . . . . . . . 6
3. Организация решения задачи . . . . . . . . . . . . . . . . . . . 8
4. Параметры поиска решения . . . . . . . . . . . . . . . . . . . . . 10
5. Задания для самостоятельной работы . . . . . . . . . . . . . 11
5.1. Задача оптимального распределения ресурсов . . 12
5.2. Задача выбора оптимального состава смеси . . . . 13
5.3. Задача оптимального раскроя бумажного
полотна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.4. Задача о передаче данных в
информационно-вычислительной сети . . . . . . . . 15
Список использованной литературы . . . . . . . . . . . . . . . . 17
Введение
Табличные процессоры в настоящее время являются одними из самых популярных программных продуктов, особенно для персональных компьютеров. Удобная форма представления данных, возможности практически мгновенного расчета одних данных на основе других позволяют решать различные задачи, связанные как с большим объемом относительно несложных расчетов, так и с прогнозированием поведения сложных систем. Простейший способ прогнозирования - решение задач методом “Что будет, если ...?”, при котором задаются различные наборы значений некоторых исходных параметров системы и оцениваются значения расчетных. Многократные расчеты позволяют оценить, как реагирует изучаемая система, описанная в виде математических соотношений, на те или иные изменения в условиях ее функционирования и выбрать то решение, которое более всего удовлетворяет предъявляемым требованиям, - оптимальное решение.
Однако в задачах прогнозирования число возможных вариантов действий зачастую настолько велико, что вручную перебрать все невозможно. Интуиция в подобных случаях оказывается плохим помощником. В таких ситуациях целесообразно использование специальных математических методов. С этой целью в современные табличные процессоры включаются мощные математические блоки, позволяющие проводить статистическую обработку данных, решать отдельные уравнения и системы уравнений, а также задачи математического программирования (оптимизационные задачи).
Данное пособие имеет целью познакомить читателя с возможностями поиска оптимальных решений средствами широко распространенного табличного процессора Excel. Пособие рассчитано на тех, кто уже имеет опыт работы с данным табличным процессором и знаком с основами математического программирования.
1. Пример оптимизационной задачи
В качестве примера задачи, связанной с поиском наилучшего решения, рассмотрим задачу выбора оптимальной структуры посевных площадей нескольких сельскохозяйственных культур. Эта задача является типичным примером задачи оптимального распределения ресурсов, часто возникающей при производстве различной продукции.
Описание задачи: в овощеводческом хозяйстве набор выращиваемых культур и объемы их производства определяются наличием пригодных для использования земель, допустимых затрат труда, заказами на отдельные виды культур, спросом на них, а также экономической эффективностью производства. При определении структуры посевных площадей необходимо обеспечить максимальную экономическую эффективность, исходя из имеющихся ресурсов.
Для решения такой задачи необходима следующая информация:
- площадь земли, отводимая под посевы;
- наличие трудовых ресурсов, выделяемых для производства овощей как в течение всего года, так и в наиболее напряженный период (в период сбора урожая);
- затраты труда на каждую культуру (всего и в напряженный /особый/ период);
- урожайность каждой из рассматриваемых культур;
- заказ на каждую культуру и предельные объемы сбыта;
- прибыль от производства каждой культуры;
- критерий оптимальности, определяющий, какое решение считается наилучшим.
Допустим, что при решении нашей задачи используются следующие исходные данные:
а) выращиваемые культуры:
- капуста;
- огурцы;
- помидоры;
- свекла;
- другие виды овощей.
Для каждой культуры полагаются известными:
- затраты труда (человеко-дней на гектар) на выращивание культуры на единице площади всего и, отдельно, в напряженный период (например, в период сбора урожая);
- заказ и предельный спрос на культуру (в центнерах).
б) площадь используемых земель равна 313 га.
в) трудовые ресурсы для производства овощей в течение года равны 45000 человеко-дней, в том числе в напряженный период - 8600 человеко-дней.
г) в качестве критерия оптимальности принимается максимум получаемой от производства овощей прибыли.
Все необходимые для решения задачи исходные (колонки с A по G) и вспомогательные данные приведены на рисунке 1, где показано их расположение на листе электронной таблицы с именем “Пользователь”.
Рис. 1. Исходные данные для решения задачи и их расположение на листе электронной таблицы.
Помимо ранее указанных требований для удобства реализации решения площадь посевов под каждую культуру будем определять с точностью до десятков гектаров (вряд ли реально выполнить задачу выращивания огурцов на площади в точности, например, 103,673 га).
2. Математическая модель задачи
Для того, чтобы найти решение задачи, необходимо сформулировать математическую модель. Прежде всего, запишем ее в общем виде, используя следующие обозначения:
N – множество выращиваемых культур, jÎN;
M – множество ресурсов (площадь земли, трудовые ресурсы и т.п.), которые можно распределять между различными видами культур, iÎM;
Aij – затраты i-го ресурса на 1 га посевов i-й культуры;
Bi – объем производственных ресурсов i-го вида;
Cj – прибыль, получаемая с 1 га посева j-й культуры;
dj – объем заказов на j-ю культуру;
Dj – предельный спрос на j-ю культуру;
Uj – урожайность j-й культуры.
Переменные задачи (управляемые, искомые величины):
Xj – площадь, выделяемая под посев j-й культуры, уменьшенная в 10 раз.
Модель задачи в общем виде выглядит следующим образом.
Целевая функция:
å 10 * Cj * Xj - max
jÎN
Ограничения на объемы используемых ресурсов:
å 10 * Ajj * Xj £ Bi " iÎM
jÎN
Ограничения на объемы производства культур:
dj £ å 10 * Uj * Xj £ Dj " jÎN
jÎN
Чтобы в процессе решения получить результаты в нужном виде – округленными до десятков значениями оптимальных посевов площадей, введем в модель дополнительное ограничение, связанное с условием целочисленности значений переменных:
Xj Î Z " jÎN
Отметим, что сформулированная математическая модель задачи включает только линейные ограничения и, следовательно, является задачей смешанного целочисленного линейного программирования (СЦЛП).
Пользуясь математической моделью общего вида, нетрудно получить конкретную модель, на основе которой и будет решаться наша задача.
Переменные:
X1 – площадь (га), выделяемая под посев капусты;
X2 – площадь (га), выделяемая под посев огурцов;
X3 – площадь (га), выделяемая под посев помидоров;
X4 – площадь (га), выделяемая под посев свеклы;
X5 – площадь (га), выделяемая под посев других овощей.
Примечание: имеются в виду уменьшенные в 10 раз значения площадей.
Целевая функция:
690*X1 + 390*X2 + 380*X3 + 140*X4 + 100*X5 - max
Ограничения:
- на общую площадь посевов:
10 * (X1 + X2 + X3 + X4 + X5) £ 313
- на общий объем трудовых ресурсов:
750*X1 + 1380*X2 + 3460*X3 + 1580*X4 + 910*X5 £ 45000
- на объем ресурсов в напряженный период:
260*X1 + 220*X2 + 350*X3 + 340*X4 + 400*X5 £ 8600
- по заказам на каждую культуру:
3250 * X1 ³ 31000
920 * X2 ³ 4500
1760 * X3 ³ 6500
2060 * X4 ³ 5900
520 * X5 ³ 1500
- по предельному спросу на каждую культуру:
3250 * X1 £ 45000
920 * X2 £ 7000
1760 * X3 £ 10000
2060 * X4 £ 9500
520 * X5 £ 8000
- на целочисленность значений:
X1 , X2 , X3 , X4 , X5 - целые.
3. Организация решения задачи
Прежде всего, присвойте одному из листов электронной таблицы имя “Пользователь” и сформируйте на нем электронный документ, показанный на рисунке 1 (в колонки I, J и K числовые значения заносить не нужно!).
Затем сформируйте все необходимые компоненты модели (переменные, целевую функцию, ограничения).
В качестве переменных задачи определите диапазон клеток K5:K9 и первоначально занесите в них нулевые значения.
В клетку I5 занесите формулу “=K5*10” и скопируйте ее в клетки диапазона K6:K9. В этих клетках будут отображаться площади посевов каждой культуры.
В клетку J5 занесите формулу “=I5*D5” и скопируйте ее в клетки диапазона J6 : J9. Здесь отображаются урожаи каждой культуры, соответствующие площади посевов.