В данной работе автор публикует задачи теории оптимизации, которые предлагает решить, используя механизм “Поиск решения” в электронных таблицах Excel и традиционный математический способ – через нахождение производной.
Для активизации процедуры “Поиска решения” в Excel необходимо выполнить команду: главное меню “Сервис” —> “Надстройки” —> “Поиск решения” —> “ОК”. В случае если “Поиск решения” не устанавливается, то необходимо обратиться к системному администратору для установки надстройки.
Введение
С древних времен человека интересовали задачи
связанные с отысканием наименьших и наибольших
величин. Бурный рост промышленности в XVII-XVIII
веках привел к необходимости исследования более
сложных задач на экстремум. Однако лишь в XX веке
при огромном размахе производства и осознании
ограниченности ресурсов Земли стала актуальной
задача оптимального использования энергии,
материалов, рабочего времени. Большую
актуальность приобрели вопросы наилучшего
управления различными процессами физики,
техники, экономики, управления и др. Сюда
относятся:
Существует несколько основных алгоритмов решения задач оптимизации: метод перебора, нахождение производной, симплекс-метод (решение экстремальных уравнений или неравенств), позволяющий просчитывать и находить решение для сотен и тысяч уравнений (неравенств). Многие задачи оптимизации сводятся к отысканию наименьшего или наибольшего значения некоторой функции, которую принято называть целевой функцией или критерием качества. Задачи оптимизации могут быть успешно решены с помощью ЭВМ. Транспортная задача является классической задачей исследования операций. Множество задач распределения ресурсов сводится именно к этой задаче. Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса возникают тогда, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью решения задачи, является отыскание такого распределения ресурсов по работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход. В самых простых задачах на оптимизацию мы имеем дело с двумя величинами, одна из которых зависит от другой, причем надо найти такое значение второй величины, при котором первая принимает свое наименьшее или наибольшее (наилучшее в данных условиях) значение.
Задачи на оптимизацию решают по обычной схеме – в виде трех этапов математического моделирования: составление математической модели, работа с моделью, ответ на вопрос задачи.
1. Задача об оптимальных перевозках (на скорейшее достижение точки назначения)
Условие задачи. Бригаде рабочих, находящейся в поле, необходимо как можно скорее эвакуировать неисправную технику в город. Попасть в город можно тремя путями:
- по кратчайшему пути от точки Б (бригада) до точки Г (город), при этом скорость эвакуатора будет равна скорости движения по полю, Vполя = 25 км/ч;
- сначала по кратчайшему пути на дорогу от точки Б до точки Д (дорога), со скоростью Vполя = 25 км/ч, потом по дороге от точки Д до точки Г со скоростью Vдор = 80 км/ч;
- сначала в некоторую точку Е на дороге, со скоростью Vполя, а потом по дороге до точки Г со скоростью Vдор.
Решить задачу – значит найти оптимальный путь, при котором время, затраченное на доставку неисправной техники, будет наименьшим.
Математической модель.
1) Оптимизируемая величина – время движения, т.к. в задаче требуется выяснить, когда время будет наименьшим. Обозначим время буквой t, а маршрут движения – буквами БЕГ.
2) Время зависит от расстояния, поэтому обозначим расстояние ДЕ=х.
Тогда ЕГ=ДГ-ЕГ=25-х (км), т.к. по т. Пифагора БД
=
(км).
Т.о., реальные границы изменения независимой
переменной 0< х< 25.
3) Для вычисления tдвижения также
найдем по теореме Пифагора расстояние БЕ=
(км),
тогда 
(ч), хI [ а;в] .
Работа с составленной моделью.
На этом этапе для функции 
(ч), хI [ а;в] нужно
найти tнаим. Для этого найдем
производную 
. Для нахождения критической точки
решим уравнение t'=0, т.е. 
т.к.
Найдя t(0) 
0,97582, t(10) 0,942), t(25)1,2 и
сравнив их, получим tнаим= t(5,455447).
Данную задачу предлагается решить средствами электронных таблиц Excel. Для этого необходимо заполнить таблицу в соответствии с условием задачи:
| A | B | C | D | |
| 1 | ДГ= | 2500 | м | Заполняем ячейки А1:С4 исходя из условия задачи |
| 2 | БГ= | 3000 | м | |
| 3 | Vполя= | 25,0 | км/ч | |
| 4 | Vдороги= | 130 | км/ч | |
| 5 | ДЕ=Х | 1000 | м | Вводим изначально любое число, <= 2500 м |
| 6 | БГ2-ДГ2= | 2750000 | м2 | По т. Пифагора квадрат В6=(В2)2–(В1)2 |
| 7 | БД= | 1658,312 | м | БД= корень(В6) |
| 8 | БЕ2= | 3750000 | м2 | Вводим формулу: = (В7)2+(В5)2 |
| 9 | БЕ= | 1936,492 | м | В9=корень(В8) |
| 10 | t= | 77,46 | мин | Время = Расстояние/Скорость,
поэтому вводим формулы: В10=В9/В3 и В11=(В1–В5)/В4 |
| 11 | tег= | 11,53846 | мин | |
| 12 | tобщ= | 89,00 | мин | В12=В11+В10 и В12 в итоге должна быть минимальной |
Заполнив таблицу, выделяем ячейку В12 и выполняем команду: “Сервис” —> “Поиск решения”.
В появившемся диалоговом окне “Поиск решения” устанавливаем целевую ячейку $B$12 равную минимальному значению. Изменяя ячейку $B$5, добавляем ограничения: $B$5<=$B$1 и $B$5>=0.
После указания всех ограничений, задаем Параметры поиска решения: Линейная модель, Неотрицательные значения, ОК. После этого нажимаем команду “Выполнить”, предоставляя компьютеру ПК самостоятельно найти решение.
В результате решение задачи выглядит следующим
образом: Для транспортировки неисправной
техники в город эвакуатор должен попасть сначала
в некоторую точку Е на дороге, удаленную от точки
Д на 545,5447 метров, со скоростью 25
км/ч, а потом по дороге со скоростью 80 км/ч. При
этом бригада рабочих проделает путь: БЕ+ЕГ = 
=37 км, а время, затраченное на
доставку неисправной техники, будет наименьшим tобщее=0,94 мин.
| А | В | С | |
| 1 | ДГ= | 25 | км |
| 2 | БГ= | 30 | км |
| 3 | Vполя= | 25 | км/ч |
| 4 | Vдороги= | 80 | км/ч |
| 5 | ДЕ=Х | 5,455447 | км |
| 6 | БГ2-ДГ2= | 275 | км2 |
| 7 | БД= | 16,58312 | км |
| 8 | БЕ2= | 304,7619 | км2 |
| 9 | БЕ= | 17,45743 | км |
| 10 | tполя= | 0,70 | ч |
| 11 | tдороги= | 0,244307 | ч |
| 12 | tобщ= | 0,94 | ч |
| 13 | БЕГ | 37,00 | км |
2. Производственная задача теории оптимизации
В автосервисе “Восток” в бригаде №1 работают трое рабочих: Федор (токарь), Петр (электрик), Ришат (сборщик). За месяц Федор способен отработать 400 ч, Петр - 200 ч, Ришат - 500 ч. Фирма на имеющемся у нее оборудовании способна оказывать четыре вида услуг: “А”, “Б”, “В”, “Г”. Известно, что услуга “А” принесет прибыль в размере 4 $, услуга “Б” - 2$, услуга “В” - 5$, услуга “Г” - 8$. Решить задачу – это значит выяснить какие услуги нужно оказать, чтобы общая прибыль фирмы была максимальной. Заполняем таблицу в соответствии с условием задачи: на первом этапе объем услуг берем произвольным: В13=5, С13=6, D13=7, E13=8.
В15: = В13*В7
С15: = С13*С7
D15: = D13*D7
E15: = Е13*Е7
F15: = СУММ(В13:Е13)
G15: = F15 / В22
В18: = B$13*B4
копируем формулу до Е20
F18: = СУММ(B18:E18)
копируем формулу до F20
G18: = F4-F18
копируем формулу до G20
Выделяем ячейку F15, выполняем команду: “Сервис” —> “Поиск решения...” Устанавливаем целевую ячейку $F$15 равной максимальному значению, изменяя ячейки: $B$13: $E$13. После указания всех ограничений, задаем Параметры поиска решения: Линейная модель, Неотрицательные значения. Возвращаемся в окно “Поиск решения” и при помощи кнопки Применить, находим оптимальное решение транспортной задачи методом линейного программирования.
Решением задачи является нахождение объема производства и суммарной прибыли, равной 964800 руб.
Эта прибыль будет наибольшей, если предприятие будет оказывать услуги вида “А” и “Г”.
3. Транспортная задача
Дано семь наименований различного оборудования: станки, трубы, буровое оборудование, отделочный камень, промышленные электромоторы, кабель. Из таблицы известны количество и вес груза. Оборудование развозится на трёх грузовиках марки Краз-256, грузоподъёмностью 28 тонн.
| A | B | C | D | E | F | G | |
| 1 | Наименование оборудования | Количество (по плану) | Вес единицы груза, кг | Первый грузовик | Второй грузовик | Третий грузовик | Количество (по факту) |
| 2 | Станки (штуки) | 11 | 850 | 0 | 0 | 0 | 0 |
| 3 | Трубы (упаковка) | 4 | 1930 | 0 | 0 | 0 | 0 |
| 4 | Буровое оборудование (ящики) | 2 | 1700 | 0 | 0 | 0 | 0 |
| 5 | Отделочный камень (ящики) | 4 | 12500 | 0 | 0 | 0 | 0 |
| 6 | Промышленные электромоторы (штуки) | 7 | 730 | 0 | 0 | 0 | 0 |
| 7 | Кабель (бухты) | 5 | 1100 | 0 | 0 | 0 | 0 |
| 8 | Итого: | 0 | 0 | 0 | |||
| 9 | |||||||
| 10 | ЦФ | 27026,66667 |
В столбцах D, E и F должны находиться числа, определяющие, сколько единиц данного груза берёт соответствующей грузовик – это и будет решением транспортной задачи по распределению грузов.
Ячейки интервала D2:F7 заполняем нулями.
В ячейке G2 должна стоять формула: =D2+E2+F2, в ячейке G3: =D3+E3+F3, в ячейке G4: =D4+E4+F4, в ячейке G5: =D5+E5+F5, в ячейке G6: =D6+E6+F6, в ячейке G7: =D7+E7+F7, так как важно, чтобы количество по плану совпадало с количеством по факту. Перед тем как начинать распределение груза, необходимо заполнить формулами ячейки D8, E8, F8.
D8: =$C$2*D2+$C$3*D3+$C$4*D4+$C$5*D5+$C$6*D6+$C$7*D7
E8: =$C$2*E2+$C$3*E3+$C$4*E4+$C$5*E5+$C$6*E6+$C$7*E7
F8: =$C$2*F2+$C$3*F3+$C$4*F4+$C$5*F5+$C$6*F6+$C$7*F7
E10: =(B2*C2+B3*C3+B4*C4+B5*C5+B6*C6+B7*C7)/3, которая контролирует грузоподъёмность (Е10 - целевая функция)
Главное в задаче - таким образом распределить товары, чтобы загрузка каждой автомашины не превышала 27 тонн более чем на 100 кг.
После заполнения формулами всех ячеек таблицы, переходим к поиску решения.
Выделяем ячейку Е10, и выполним команду: Сервис, Поиск решения...
Устанавливаем целевую ячейку: $E$10, равной максимальному значению, Изменяя ячейки: $D$2:$F$7, добавляем ограничения:
$D$2:$F$7=целое, $D$2:$F$7>=0, $D$8<=27100, $F$8<=27100, $D$8<=27100, $F$8<=27100, $G$2=11, $G$3=4, $G$4=2, $G$5=4, $G$6=7, $G$7=5.
После указания всех ограничений, задаем Параметры поиска решения: Линейная модель, Неотрицательные значения. Возвращаемся в окно “Поиск решения” и при помощи кнопки Применить, находим оптимальное решение транспортной задачи методом линейного программирования. Решением задачи является распределение оборудования по трем грузовикам
Данная задача может быть решена несколько раз, при этом мы будем получать все новое и новое решение, т.е. оборудование можно распределить и по-разному, не нарушив при этом ограничения по грузоподъемности. Для этого необходимо несколько раз выполнить процедуру “Поиск решения”.
| A | B | C | D | E | F | G | |
| 1 | Наименование оборудования | Количество (по плану) | Вес единицы груза, кг | Первый грузовик | Второй грузовик | Третий грузовик | Количество (по факту) |
| 2 | Станки (штуки) | 11 | 850 | 4 | 1 | 6 | 11 |
| 3 | Трубы (упаковка) | 4 | 1930 | 1 | 0 | 3 | 4 |
| 4 | Буровое оборудование (ящики) | 2 | 1700 | 2 | 0 | 0 | 2 |
| 5 | Отделочный камень (ящики) | 4 | 12500 | 1 | 2 | 1 | 4 |
| 6 | Промышленные электромоторы (штуки) | 7 | 730 | 2 | 0 | 5 | 7 |
| 7 | Кабель (бухты) | 5 | 1100 | 4 | 1 | 0 | 5 |
| 8 | Итого: | 27090 | 26950 | 27040 | |||
| 9 | |||||||
| 10 | ЦФ | 27026,66667 |
Заключение
Представленные в данной статье параметрические задачи успешно решены средствами компьютерной программы Ms Excel.
Механизм “Поиск решения” позволяет за короткое время найти целевую функцию, т.е. за секунды компьютер просчитывает оптимальный вариант решения. Описанные в статье задачи теории оптимизации и методы их решения – только отдельный пример огромного множества задач линейного программирования.
Цель транспортной задачи – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д. Цель производственной задачи – нахождение оптимального плана, при котором производство будет давать наибольший доход.
Цель задачи об оптимальных перевозках – найти минимальный путь, при котором время, затраченное на дорогу, будет минимальным.