Решение задач оптимизации с помощью MS Excel

Решение задач оптимизации в Microsoft Excel производится с помощью надстройки «Поиск решения».

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

При этом принципы построения схемы задачи в таблице Excel и ее решения практически совпадают как для линейного, так и для нелинейного программирования.

Рассмотрим процесс решения задач оптимизации на прмерах двух задач: задачи планирования производства, и транспортной задачи, используя возможности таблиц Excel.

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

Рассмотрим задачу, приведенную в примере 6.2.

Математическая модель этой задачи, как описано выше имеет вид:

при ограничениях

Последовательность действий:

1. Подготовим таблицу как показано на рис.6.15. Ячейки, содержащие целевую функцию (А10) и изменяемые ячейки (проектные параметры x₁, x₂) В10: С10 тонируем. Для контроля счета в ячейки В10: С10 введем единицы. Значения проектных параметров х₁=1 и х₂=1 можно рассматривать как начальное приближение решения задачи.

2. Систему ограничений (6.12) запишем в виде, как показано на рис.6.15, т.е.:

a_i x₁ + b_i x₂ - d_i ≥ 0, i=1, 2, 3, 4, 5.

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

3. В ячейки В3: D7 введем коэффициенты системы ограничений.

Рис.6.15. Расчетная схема для примера 6.2

4. В ячейку E3 введем формулу для вычисления левой части 1-го ограничения, т.е.

E3=СУММПРОИЗВ($B$10: $C$10; B3: C3)+D3,

и после ввода скопируем ее вниз до конца таблицы. Будет не лишним проверить результаты счета для заданных значений х₁=1 и х₂=1.

5. Формулу для целевой функции запишем в ячейке A10:

A10=1-В10-С10.

6. Выберем команду меню Данные\Поиск решения и в появившемся окне сделаем соответствующие установки (рис.6.16). Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает окно Добавление ограничения для ввода этих ограничений (см. рис. 6.16).

 

 

Рис.6.16. Окно «Поиск решения»

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

Рис.6.17. Результаты решения примера 6.2

Результаты можно сохранить или отказаться от них (восстановив исходные значения). Можно получить один из видов отчетов (Результаты, Устойчивость, Пределы). Отчет можно оформить на отдельном листе Книги с соответствующим именем.

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

Рассмотрим задачу, приведенную в примере 6.8.

В качестве проектных параметров были приняты - x_ij (i=1, 2, 3, 4,; j=1, 2, 3) - количество цемента, перевозимого с i-го завода на j-ый ЖБК.

Известна Cij - стоимость перевозки единицы продукта с i -го завода на j-ый ЖБК.

Целевая функция:

Z_min =3x₁₁+5x₁₂+7х₁₃+11х₁₄+

+x₂₁+4x₂₂+6x₂₃+3x₂₄+

+5x₃₁+8x₃₂+12x₃₃+7x₃₄ (6.32)

 

Ограничения:

x₁₁ +x₁₂ +х₁₃+х₁₄ = 150,

x₂₁ +x₂₂ +x₂₃+x₂₄ = 130,

x₁₁ +x₂₁ +х₃₁ = 150, (6.33)

x₁₂ +x₂₂ +x₃₂ = 120,

x₁₃ +x₂₃.+x₃₃ = 80,

x₁₄ +x₂₄.+x₃₄ = 50,

x_ij³ 0 (i=1, 2, 3; j=1, 2, 3, 4).

Последовательность действий:

1. Подготовим таблицу, как показано на рис.6.17. Ячейки, содержащие целевую функцию I10 и изменяемые ячейки (проектные параметры x_ij, i=1, 2, j=1, 2, 3) D4: D6, F4: F6; Н4: Н6, J4: J6, тонированы. Для контроля счета в изменяемые ячейки введем какие-либо числа, например единицы. Эти значения проектных параметров можно рассматривать как начальное приближение решения.

2. Введем исходные данные (цены перевозок) из таблицы примера 6.8 в соответствующие ячейки рис.6.17.

3. В ячейку I10 введем целевую функцию:

I10 = СУММПРОИЗВ(C4: C6; D4: D6) +

+СУММПРОИЗВ(E4: E6; F4: F6)+

+СУММПРОИЗВ(G4: G6; Н4: Н6; )+

+СУММПРОИЗВ(I4: I6; J4: J6)

4. Подготовим таблицу ограничений. Для этого в ячейку D10 введем формулу: D10=D4+F4+H4+J4-B4, а затем скопируем ее вниз на две строки.

5. Для ввода следующих четырех ограничений воспользуемся автосуммированием. Например: D13=СУММ(D4: D6)-D7, аналогичные формулы запишем в ячейки D15: D17.

Рис.6.17. Схема решения транспортной задачи

6. Последнюю строку ограничений добавим непосредственно в окне «Поиск решения».

7. Выделим ячейку I10 (целевая ячейка) и выберем команду меню Данные\Поиск решения. В появившемся окне «Поиск решения» сделаем установки, как показано на рис.6.18. Для ввода ограничений используем кнопку Добавить.

Рис.6.18. Окно «Поиск решения»

Результат счета приведен на рис.6.19, минимальная стоимость перевозок составляет 2040 у.е.

Рис.6.19. Результаты решения транспортной задачи

Контрольные вопросы

1. Математическая постановка задач оптимизации в строительстве.

2. Классификация задач математического программирования.

3. Общая постановка задачи линейного программирования.

4. Геометрический метод решения задач линейного программирования.

5. В чем заключается идея Симплекс-метод решения задач линейного программирования.

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

Литература

1. Антонов В.И., Копелевич Ф.И. Элементарная математика для первокурсника. 1-е изд., - СПб.: Лань, 2013. – 112с.

2. Вержбицкий В.М. Вычислительная и линейная алгебра. - М.: Высшая школа, 2009. - 351с.

3. Вержбицкий В.М. Основы численных методов. - М.: Высшая школа, 2009. - 840с.

4. Гельфанд И.М. Лекции по линейной алгебре. М.: Добросвет, 2009. – 320с.

5. Горлач Б.А. Линейная алгебра: учебное пособие. – СПб.: Лань, 2012. - 480с.

6. Демидович Б.П., Марон И.А. Основы вычислительной математики. СПб.: Лань, 2007.-664с.

7. Золотов А.Б., Акимов П.А., Сидоров В.Н., Мозгалева М.Л. Информатика в строительстве (с основами численного моделирования). – М.: Архитектура – С, 2010. – 336с.

8. Кашеварова Г.Г., Пермякова Т.Б. Численные методы решения задач строительства на ЭВМ. – Пермь: ПГТУ, 2007. – 352с.

9. Киреев В.И., Пантелеев А.В. Численные методы в примерах и задачах — М.: Высш. шк., 2008. — 480с.

10. Попов А. EXCEL. Практическое руководство. МГУТА, 2007. - 301с.

11. Самарский А. А. Введение в численные методы. Учебное пособие для вузов. 3-е изд., стер. — СПб.: Издательство «Лань», 2005. — 288с.

12. Турчак Л.И. Плотников П.В. Основы численных методов: Учебное пособие. 2-е изд. – М.: Физматлит, 2002. – 304с.

13. Щипачев В.С. Высшая математика. – СПб.: Лань, 2013. – 384с.

 

Оглавление

Предисловие. 3

Введение. 6

Глава 1.Основные понятия матричного исчисления. 16

1.1. Матрицы и векторы. 16

1.2. Матрицы специального вида. 18

1.3. Действия над матрицами. 21

1.4. Нормы матрицы и вектора. 23

1.5. Функции MS Excel для операций над матрицами. 25

Глава 2.Численные методы решения нелинейных уравнений.. 27

2.1. Первый этап. Отделение корней. 29

2.2. Второй этап. Этап уточнения корня. 33

2.2.1.Метод половинного деления (бисекции) 34

2.2.2.Метод хорд. 37

2.2.3.Метод Ньютона (метод касательных) 40

2.2.4.Модифицированный метод Ньютона. 43

2.3.Реализация численных методов решения нелинейных уравнений средствами приложения MS Excel 44

2.3.1. Решение нелинейных уравнений с использованием надстройки «Подбор параметра» 47

Глава 3.Численные методы решения систем линейных алгебраических уравнений 50

3.1. Системы линейных алгебраических уравнений. 50

3.2. Прямые методы решения систем линейных алгебраических уравнений 53

3.2.1. Метод Гаусса. 53

3.2.2. Метод прогонки. 58

3.3. Итерационные методы решения систем линейных алгебраических уравнений 60

3.3.1. Метод Якоби (простых итераций) 60

3.3.2. Метод Гаусса – Зейделя. 65

3.3.3. Условия сходимости итерационного процесса. 67

3.5. Устойчивость решения СЛАУ относительно исходных данных. 70

3.6. Примеры решения СЛАУ с использованием электронных таблиц MS Excel 74

3.6.1. Реализация метода Гаусса. 74

3.6.2. Решение СЛАУ с помощью надстройки «Поиск решения». 76

3.6.3. Реализация метода Якоби средствами приложения Excel 79

3.6.4. Реализация метода прогонки средствами приложения Excel 82

 

Глава 4.Численное интегрирование. 85

4.1. Квадратурные формулы прямоугольников. 88

4.2. Квадратурная формула трапеций. 91

4.3. Квадратурная формула Симпсона. 92

4.4. Реализация методов численного интегрирования средствами приложения MS Excel 95

Глава 5.Аппроксимация. 99

5.1. Задачи аппроксимации. 99

5.2. Интерполирование функций. 100

5.2.1. Постановка задачи интерполирования. 100

5.2.2. Интерполяционная формула Лагранжа. 102

5.3. Среднеквадратичное приближение функций. 105

5.3.1. Постановка задачи. 105

5.3.2. Метод наименьших квадратов. 109

5.3.3. Линейная эмпирическая формула. 110

(линейная регрессия) 110

5.3.4. Коэффициент корреляции. 113

5.3.5. Квадратичное (параболическое) приближение. 114

5.3.6. Эмпирические формулы с двумя параметрами (метод выравнивания) 115

5.4. Решение задач аппроксимации с помощью электронных таблиц Excel 118

5.4.1. Построение уравнений регрессии методом наименьших квадратов с использованием надстройки «Поиск решения» 118

5.4.2. Построение линейной эмпирической формулы с использованием встроенных функций ЛИНЕЙН и ТЕНДЕНЦИЯ 122

Глава 6.Численные методы оптимизации.. 125

6.1.Общие сведения. 126

6.1.1. Математическая модель задачи оптимизации. 126

6.1.2. Классификация задач математического программирования. 130

6.2. Постановка задачи оптимального проектирования. 132

6.3.Задачи линейного программирования. 134

6.3.1.Общая постановка задачи. 135

6.3.2.Геометрический смысл системы линейных неравенств. 137

6.3.3.Геометрический метод решения задач линейного программирования 141

6.3.4.Симплекс-метод решения задач линейного программирования.... 148

6.4. Примеры задач линейного программирования в сфере проектирования и управления строительным производством 151

6.4.1. Задача об оптимальном плане выпуска продукции 154

6.4.2. Задача об оптимальном раскрое материалов (о минимизации отходов) 157

6.4.3. Задача о планировании смен на предприятии 160

6.4.4. Задача о покрытии местности при строительстве объектов 160

Транспортная задача 161

6.4.6. Задача о назначениях (проблема выбора) 165

6.4.7. Задача о назначениях (проблема выбора) 167

6.5. Решение задач оптимизации с помощью MS Excel 163

6.5.1.Решение задачи планирования производства. 163

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

Литература171

 

1 Ведущий (главный) элемент – элемент, стоящий на главной диагонали.

* - данная запись означает, что в ячейку А7 вводится формула, начинающаяся со знака «=» (равно).

 

⇐ Предыдущая9101112131415161718

Поделиться:

Популярное:

1. I I. Цели, задачи, результаты выполнения индивидуального проекта
2. I. Автоматизации функциональных задач в государственном и региональном управлении.
3. II. Основные задачи управления персоналом.
4. II. Решить следующие ниже финансовые задачи на листе “Задачи”.
5. II. Цели, задачи и предмет деятельности
6. III ГЛАВА. ИНТЕРЬЕР И АРХИТЕКТУРНО – ПРОЕКТИРОВОЧНОЕ РЕШЕНИЕ ШКОЛЫ БУДУЩЕГО
7. III. Задачи, решаемые организацией с помощью ИСУ и ИТУ.
8. III. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ РАЙОННОЙ ОРГАНИЗАЦИИ ПРОФСОЮЗА
9. III. Экономико-управленческие задачи производственной практики
10. IV. Решить следующую задачу.
11. Microsoft Windows, Word, Excel
12. MS Excel. Знак, указывающий что число не вмещается в ячейку