Решение задач математического

Решение задач математического

Программирования в среде

Табличного процессора 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. Пособие рассчитано на тех, кто уже имеет опыт работы с данным табличным процессором и знаком с основами математического программирования.

 

 

Пример оптимизационной задачи

 

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

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

Для решения такой задачи необходима следующая информация:

n площадь земли, отводимая под посевы;

n наличие трудовых ресурсов, выделяемых для производства овощей как в течение всего года, так и в наиболее напряженный период (в период сбора урожая);

n затраты труда на каждую культуру (всего и в напряженный /особый/ период);

n урожайность каждой из рассматриваемых культур;

n заказ на каждую культуру и предельные объемы сбыта;

n прибыль от производства каждой культуры;

n критерий оптимальности, определяющий, какое решение считается наилучшим.

Допустим, что при решении нашей задачи используются следующие исходные данные:

а) выращиваемые культуры:

n капуста;

n огурцы;

n помидоры;

n свекла;

n другие виды овощей.

Для каждой культуры полагаются известными:

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

n заказ и предельный спрос на культуру (в центнерах).

б) площадь используемых земель равна 313 га.

в) трудовые ресурсы для производства овощей в течение года равны 45000 человеко-дней, в том числе в напряженный период - 8600 человеко-дней.

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

Все необходимые для решения задачи исходные (колонки с A по G) и вспомогательные данные приведены на рисунке 1, где показано их расположение на листе электронной таблицы с именем “Пользователь”.

 

 

Рис. 1. Исходные данные для решения задачи и их расположение на листе электронной таблицы.

 

 

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

 

Организация решения задачи

 

Прежде всего, присвойте одному из листов электронной таблицы имя “Пользователь” и сформируйте на нем электронный документ, показанный на рисунке 1 (в колонки I, J и K числовые значения заносить не нужно!).

Затем сформируйте все необходимые компоненты модели (переменные, целевую функцию, ограничения).

В качестве переменных задачи определите диапазон клеток K5:K9 и первоначально занесите в них нулевые значения.

В клетку I5 занесите формулу “=K5*10” и скопируйте ее в клетки диапазона K6:K9. В этих клетках будут отображаться площади посевов каждой культуры.

В клетку J5 занесите формулу “=I5*D5” и скопируйте ее в клетки диапазона J6: J9. Здесь отображаются урожаи каждой культуры, соответствующие площади посевов.

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

=СУММПРОИЗВ(G5: G9; I5: I9)

Значение этой формулы есть значение целевой функции задачи.

Одному из листов электронной таблицы присвойте имя “Модель”. На этом листе будут размещены формулы, соответствующие левым частям ограничений модели. Поскольку значения ограничений при поиске решения наблюдать не обязательно, они размещаются в том месте, где они не видны пользователю, например, на другом листе. Пояснительные тексты и формулы, размещаемые на листе “Модель”, показаны на рисунке 2.

Примечание: в некоторых версиях табличного процессора Excel все сведения, относящиеся к модели, должны размещаться на одном и том же листе.

 

 

Рис. 2. Пояснительные тексты и формулы, размещаемые на листе электронной таблицы с именем “Модель”.

 

 

Для формирования условий оптимизационной задачи и поиска оптимального решения необходимо инициировать работу оптимизационного блока Excel с помощью команды меню “Сервис, Поиск решения...”. В результате на экране появится окно “Поиск решения”.

Далее необходимо проделать следующее. В поле окна “Установить целевую ячейку” указать адрес ячейки, значение которой используется в качестве критерия оптимизации - в нашем случае это ячейка J11. Имя ячейки можно ввести вручную или же, сделав описываемое поле активным, указать мышкой нужную ячейку электронной таблицы. Необходимое условие - целевая ячейка обязательно должна содержать формулу, значение которой зависит от изменяемых ячеек, соответствующих переменным задачи. Рядом с целевой ячейкой необходимо установить признак вида оптимизации (максимум или минимум целевой функции или ее равенство некоторому значению, которое в этом случае требуется указать).

В поле “Изменяя ячейки” необходимо указать область ячеек, соответствующих переменным задачи. В нашем случае этой областью будет диапазон K5:K9. При нажатии кнопки “Предположить” в рассматриваемом поле будут указаны все ячейки, связанные с формированием значения целевой функции, что не всегда удобно (например, в нашем случае вместе с клетками K5:K9 будут указаны клетки G5:G9, соответствующие коэффициентам целевой функции, считающимся константами в ходе поиска решения).

Замечание: ссылки на ячейки в полях окна “Поиск решения” автоматически становятся абсолютными.

Ограничения задачи указываются в поле “Ограничения”. Для задания ограничения требуется указать ячейку, соответствующую левой части ограничения, тип ограничения - “не больше”, “не меньше”, “равно”, “целое” (последнее только по отношению к ячейкам переменных), и ячейку или числовое значение левой части ограничения.

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

 

Для рассматриваемой нами задачи необходимо определить 14 ограничений, приводимых ниже:

 

1. $K$5: $K$9 = целое

2. Модель!$A$3 <= $D$11      Ограничение на площадь посевов

3. Модель!$A$5 <= $D$12      Ограничения на трудовые ресурсы

4. Модель!$A$7 <= $D$13      Ограничение на трудовые ресурсы в напряжен- ный период

5. $J$5 >= $B$5                        Группа ограничений на объемы производства

6. $J$6 >= $B$6                        продукции (не менее, не более)

7. $J$7 >= $B$7

8. $J$8 >= $B$8

9. $J$9 >= $B$9

10. $J$5 <= $C$5

11. $J$6 <= $C$6

12. $J$7 <= $C$7

13. $J$8 <= $C$8

14. $J$9 <= $C$9

 

При нажатии кнопки “Добавить” в окне “Добавить ограничение” сформированное ограничение будет добавлено к условиям задачи и станет возможным задание следующего без возврата в окно “Поиск решения”.

Сформировав все параметры задачи, выполните ее решение, нажав на кнопку “Выполнить”. Согласно требованиям Excel изменяемые в процессе поиска оптимального решения ячейки (соответствующие переменным задачи) обязательно должны располагаться на активном листе электронной таблицы. Поэтому в момент нажатия кнопки “Выполнить” текущим должен быть лист “Пользователь”.

Сравните полученное решение с оптимальным, которое приведено на рис. 1. Если они совпадают, значит, Вы все сделали правильно.

 

Параметры поиска решения

 

Иногда, после формирования модели, приходится уточнять параметры метода решения задачи. Для получения такой возможности следует нажать кнопку “Параметры...”, в результате чего открывается окно “Параметры поиска решения”.

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

Тем не менее дадим краткие пояснения смысла некоторых параметров.

“Максимальное время” определяет предельное время поиска решения (не более 32767 секунд). Если в течение указанного времени оптимальное решение не будет найдено, процесс поиска прерывается и следует запрос о необходимости продолжить или прекратить решение задачи. В последнем случае Вы получите некоторое промежуточное, возможно, недопустимое решение.

“Итерации”. Процесс поиска оптимального решения носит пошаговый, итеративный характер (не более 32767 итераций). Решение, получаемое в ходе очередной итерации, основывается на полученном при выполнении предыдущей. При исчерпании числа итераций процесс поиска решения прерывается (см. предыдущий пункт).

 

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

“Относительная погрешность”. Данное поле должно содержать число из интервала (0, 1). Точность определяет близость полученного значения целевой функции оптимальному. Чем больше точность (т.е. чем ближе указанное число к нулю), тем большее число итераций и большее время требуется для поиска оптимального решения.

“Допустимое отклонение” определяет допуск на отклонение от оптимального решения, если на переменные наложено условие целочисленности.

Из остальных возможностей стоит отметить лишь пункт “Линейная модель” - линейность всегда стоит указывать явно, поскольку это позволяет в несколько раз сократить время решения задачи и, скорее всего, получить более точный ответ.

Кнопки “Сохранить модель...” и “Загрузить модель...” позволяют сохранять параметры сформированной модели в какой-либо области электронной таблицы.

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

 

Задание: обнулите значения переменных (клетки K5:K9), установите признак линейности и снова выполните поиск решения. Теперь он займет гораздо меньше времени.

 

5. Задания для самостоятельной работы

 

Предлагаемые ниже задания подобраны таким образом, чтобы при их выполнении требовалось как знание ряда классических задач математического программирования, так и некоторых специальных приемов, используемых при построении математических моделей, относящихся к задачам линейного (ЛП) и смешанного целочисленного программирования (СЦЛП). Все задания подобраны таким образом, чтобы при построении модели была возможность остаться в рамках задач ЛП или СЦЛП (для этих классов задач математического программирования разработаны и используются наиболее эффективные методы решения). Поэтому все построенные Вами модели должны относиться к задачам указанных классов.

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

 

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

n перечень использованных обозначений с пояснениями смысла каждого обозначения;

n модель задачи в общем виде с пояснениями смысла каждого соотношения;

n модель задачи, сформулированная на основе тех конкретных исходных данных, которые указаны в задании. Все соотношения модели должны быть записаны в развернутом виде и иметь пояснения;

n результат решения задачи с конкретными исходными данными (значения переменных и целевой функции).

 

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

 

Задача о передаче данных

Список использованной литературы

 

1. Фратер Г. Excel 5.0: Пер. с нем. Киев: Торгово-издательское бюро BHV, 1995. 560 с.

2. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. СПб.: BHV-Санкт-Петербург, 1997. 384 с.

3. Поляков В.В., Карпов А.В., Кузнецов В.А. Решение оптимизационных задач в среде табличного процессора Quattro Pro: Методические указания. Петрозаводск: Изд-во ПетрГУ, 1994. 37 с.

 

 

Владимир Витальевич Поляков

 

Сергей Тимофеевич Коржов

 

Александр Вениаминович Карпов

 

Решение задач математического программирования

в среде табличного процессора Excel

 

Методические указания

 

 

Редактор Л.П.Соколова

 

 

 

Подписано к печати 10.10.98. Формат 60x841/16. 

Бумага типографская. Офсетная печать. 1,1 уч.-изд. л. 

7 усл. кр.-отт. л. Тираж 150 экз. Изд. № 135 “С”.

 

Издательство Петрозаводского государственного

университета

 

185640, г. Петрозаводск, пр. Ленина, 33

 

 

 

Решение задач математического

Программирования в среде

Табличного процессора 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. Пособие рассчитано на тех, кто уже имеет опыт работы с данным табличным процессором и знаком с основами математического программирования.

 

 

Пример оптимизационной задачи

 

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

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

Для решения такой задачи необходима следующая информация:

n площадь земли, отводимая под посевы;

n наличие трудовых ресурсов, выделяемых для производства овощей как в течение всего года, так и в наиболее напряженный период (в период сбора урожая);

n затраты труда на каждую культуру (всего и в напряженный /особый/ период);

n урожайность каждой из рассматриваемых культур;

n заказ на каждую культуру и предельные объемы сбыта;

n прибыль от производства каждой культуры;

n критерий оптимальности, определяющий, какое решение считается наилучшим.

Допустим, что при решении нашей задачи используются следующие исходные данные:

а) выращиваемые культуры:

n капуста;

n огурцы;

n помидоры;

n свекла;

n другие виды овощей.

Для каждой культуры полагаются известными:

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

n заказ и предельный спрос на культуру (в центнерах).

б) площадь используемых земель равна 313 га.

в) трудовые ресурсы для производства овощей в течение года равны 45000 человеко-дней, в том числе в напряженный период - 8600 человеко-дней.

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

Все необходимые для решения задачи исходные (колонки с A по G) и вспомогательные данные приведены на рисунке 1, где показано их расположение на листе электронной таблицы с именем “Пользователь”.

 

 

Рис. 1. Исходные данные для решения задачи и их расположение на листе электронной таблицы.

 

 

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