Поиск решения - это надстройка Microsoft Excel, с помощью которой можно найти оптимальное решение задачи с учетом заданных пользователем ограничений.
Поиск решения будем рассматривать в (эта надстройка претерпела некоторые изменения по сравнению с предыдущей версией в .
В этой статье рассмотрим:
Команда Поиск решения находится в группе Анализ на вкладке Данные .
Если команда Поиск решения
в группе Анализ
недоступна, то необходимо включить одноименную надстройку.
Для этого:
Примечание . Окно Надстройки также доступно на вкладке Разработчик . Как включить эту вкладку .
После нажатия кнопки Поиск решения в группе Анализ, откроется его диалоговое окно.
При частом использовании Поиска решения его удобнее запускать с Панели быстрого доступа, а не из вкладки Данные. Чтобы поместить кнопку на Панель, кликните на ней правой клавишей мыши и выберите пункт Добавить на панель быстрого доступа .
Этот раздел для тех, кто только знакомится с понятием Оптимизационная модель.
Совет . Перед использованием Поиска решения настоятельно рекомендуем изучить литературу по решению оптимизационных задач и построению моделей.
Ниже приведен небольшой ликбез по этой теме.
Надстройка Поиск решения помогает определить лучший способ сделать что-то :
Вот некоторые типичные примеры оптимизационных задач:
Для формализации поставленной задачи требуется создать модель, которая бы отражала существенные характеристики предметной области (и не включала бы незначительные детали). Следует учесть, что модель оптимизируется Поиском решения
только по одному показателю
(этот оптимизируемый показатель называется целевой функцией
).
В MS EXCEL модель представляет собой совокупность связанных между собой формул, которые в качестве аргументов используют переменные. Как правило, эти переменные могут принимать только допустимые значения с учетом заданных пользователем ограничений.
Поиск решения
подбирает такие значения этих переменных (с учетом заданных ограничений), чтобы целевая функция была максимальной (минимальной) или была равна заданному числовому значению.
Примечание
. В простейшем случае модель может быть описана с помощью одной формулы. Некоторые из таких моделей могут быть оптимизированы с помощью инструмента . Перед первым знакомством с Поиском решения
имеет смысл сначала детально разобраться с родственным ему инструментом .
Основные отличия Подбора параметра
от Поиска решения
:
Поиск решения
оптимизирует значение целевой функции. Под целевой функцией подразумевается формула, возвращающая единственное значение в ячейку. Результат формулы должен зависеть от переменных модели (не обязательно напрямую, можно через результат вычисления других формул).
Ограничения модели могут быть наложены как на диапазон варьирования самих переменных, так и на результаты вычисления других формул модели, зависящих от этих переменных.
Все ячейки, содержащие переменные и ограничения модели должны быть расположены только на одном листе книги. Ввод параметров в диалоговом окне Поиска решения
возможен только с этого листа.
Целевая функция (ячейка) также должна быть расположена на этом листе. Но, промежуточные вычисления (формулы) могут быть размещены на других листах.
Совет . Организуйте данные модели так, чтобы на одном листе MS EXCEL располагалась только одна модель. В противном случае, для выполнения расчетов придется постоянно сохранять и загружать настройки Поиска решения (см. ниже).
Приведем алгоритм работы с Поиском решения , который советуют сами разработчики (www.solver.com ):
Проделаем все эти шаги на простом примере.
Необходимо загрузить контейнер товарами, чтобы вес контейнера был максимальным. Контейнер имеет объем 32 куб.м. Товары содержатся в коробках и ящиках. Каждая коробка с товаром весит 20кг, ее объем составляет 0,15м3. Ящик - 80кг и 0,5м3 соответственно. Необходимо, чтобы общее количество тары было не меньше 110 штук.
Данные модели организуем следующим образом (см. файл примера ).
Переменные модели (количество каждого вида тары) выделены зеленым.
Целевая функция (общий вес всех коробок и ящиков) – красным.
Ограничения модели: по минимальному количеству тары (>=110) и по общему объему (<=32) – синим.
Целевая функция рассчитывается по формуле =СУММПРОИЗВ(B8:C8;B6:C6)
– это общий вес всех коробок и ящиков, загруженных в контейнер.
Аналогично рассчитываем общий объем - =СУММПРОИЗВ(B7:C7;B8:C8)
. Эта формула нужна, чтобы задать ограничение на общий объем коробок и ящиков (<=32).
Также для задания ограничения модели рассчитаем общее количество тары =СУММ(B8:C8)
.
Теперь с помощью диалогового окна Поиск решения
введем ссылки на ячейки содержащие переменные, целевую функцию, формулы для ограничений и сами значения ограничений (или ссылки на соответствующие ячейки).
Понятно, что количество коробок и ящиков должно быть целым числом – это еще одно ограничение модели.
После нажатия кнопки Найти решение будут найдены такие количества коробок и ящиков, при котором общий их вес (целевая функция) максимален, и при этом выполнены все заданные ограничения.
На самом деле, основной проблемой при решении оптимизационных задач с помощью Поиска решения
является отнюдь не тонкости настройки этого инструмента анализа, а правильность построения модели, адекватной поставленной задаче. Поэтому в других статьях сконцентрируемся именно на построении моделей, ведь «кривая» модель часто является причиной невозможности найти решение с помощью Поиска решения
.
Зачастую проще просмотреть несколько типовых задач, найти среди них похожую, а затем адаптировать эту модель под свою задачу.
Решение классических оптимизационных задач с помощью Поиска решения
рассмотрено .
Это сообщение появляется, когда Поиск решения
не смог найти сочетаний значений переменных, которые одновременно удовлетворяют всем ограничениям.
Если вы используете Симплекс метод решения линейных задач
, то можно быть уверенным, что решения действительно не существует.
Если вы используете метод решения нелинейных задач, который всегда начинается с начальных значений переменных, то это может также означать, что допустимое решение далеко от этих начальных значений. Если вы запустите Поиск решения
с другими начальными значениями переменных, то, возможно, решение будет найдено.
Представим, что при решении задачи нелинейным методом, ячейки с переменными были оставлены не заполненными (т.е. начальные значения равны 0), и Поиск решения
не нашел решения. Это не означает, что решения действительно не существует (хотя это может быть и так). Теперь, основываясь на результатах некой экспертной оценки, в ячейки с переменными введем другой набор значений, который, по Вашему мнению, близок к оптимальному (искомому). В этом случае, Поиск решения
может найти решение (если оно действительно существует).
Примечание . О влиянии нелинейности модели на результаты расчетов можно прочитать в последнем разделе статьи .
В любом случае (линейном или нелинейном), Вы должны сначала проанализировать модель на непротиворечивость ограничений, то есть условий, которые не могут быть удовлетворены одновременно. Чаще всего это связано с неправильным выбором соотношения (например, <= вместо >=) или граничного значения.
Если, например, в рассмотренном выше примере, значение максимального объема установить 16 м3 вместо 32 м3, то это ограничение станет противоречить ограничению по минимальному количеству мест (110), т.к. минимальному количеству мест соответствует объем равный 16,5 м3 (110*0,15, где 0,15 – объем коробки, т.е. самой маленькой тары). Установив в качестве ограничения максимального объема 16 м3, Поиск решения
не найдет решения.
При ограничении 17 м3 Поиск решения найдет решение.
Метод решения
Рассмотренная выше модель является линейной, т.е. целевая функция (M – общий вес, который может быть максимален) выражена следующим уравнением M=a1*x1+a2*x2, где x1 и x2 – это переменные модели (количество коробок и ящиков), а1 и а2 – их веса. В линейной модели ограничения также должны быть линейными функциями от переменных. В нашем случае ограничение по объему V=b1*x1+b2*x2 также выражается линейной зависимостью. Очевидно, что другое ограничение - Максимальное количество тары (n) – также линейно x1+x2
В этом случае необходимо выбрать метод для решения нелинейной задачи. Примеры нелинейных зависимостей: V=b1*x1*x1; V=b1*x1^0,9; V=b1*x1*x2, где x – переменная, а V – целевая функция.
Кнопки Добавить, Изменить, Удалить
Эти кнопки позволяют добавлять, изменять и удалять ограничения модели.
Кнопка Сбросить
Чтобы удалить все настройки Поиска решения
нажмите кнопку Сбросить
– диалоговое окно очистится.
Точность
При создании модели исследователь изначально имеет некую оценку диапазонов варьирования целевой функции и переменных. Принимая во внимание вычислений в MS EXCEL, рекомендуется, чтобы эти диапазоны варьирования были значительно выше точности вычисления (она обычно устанавливается от 0,001 до 0,000001). Как правило, данные в модели нормируют так, чтобы диапазоны варьирования целевой функции и переменных были в пределах 0,1 – 100 000. Конечно, все зависит от конкретной модели, но если ваши переменные изменяются более чем на 5-6 порядков, то возможно следует «загрубить» модель, например, с помощью операции логарифмирования.
Оптимизационные модели используются, чтобы найти ответы на вопросы типа:
Скачать заметку в формате или , примеры в формате
Целью оптимизации всегда является «максимизация» или «минимизация». Самая распространенная и понятная форма математической оптимизации - это линейное программирование, секретная разработка советских инженеров конца 1930-х годов, ставшая популярной в ходе Второй мировой войны. Кстати, слово «программирование» в данном словосочетании является пережитком военной терминологии того времени и не имеет ничего общего с компьютерным программированием.
Начнем с любимого примера экономистов - пушек и масла. Идет 1941-й год, вы – хозяин французской молочной фермы. Днем вы доите коров и производите сливочное масло, ночью – собираете автоматы. Ваша цель – максимальная прибыль, чтобы как можно дольше производить автоматы. От посредника из Сопротивления вы получаете за каждый автомат по 195 денежных единиц (чтобы не напрягать Excel несуществующими франками, допустим, что это доллары). За каждую бочку масла на рынке вам платят по $150.
Условия и ограничения. Себестоимость одной бочки масла – $100, а одного автомата – $150. Месячный бюджет на производство - $1800. Вы храните продукцию в 21-кубометровом подвале. Автомат занимает ½ м 3 , бочка масла 1½ м 3 . Сколько автоматов и бочек масла вам нужно продать за месяц, чтобы получить максимальную прибыль?
Линейная программа определяется как набор решений, необходимый для оптимизации объекта в свете некоторых условий, где и объект, и условия линейны. Вы можете складывать, вычитать, умножать на константы, но не можете применять для решения нелинейные функции, например, перемножение переменных (нельзя автоматы умножить на масло), возведение в квадрат или логические циклы, такие как ЕСЛИ.
Представим области допустимых значений графически. Во-первых, количество пушек и бочек масла должно быть неотрицательным. Во-вторых, максимально можно произвести $1800/$150 = 12 автоматов или $1800/$100 = 18 бочек масла (рис. 1). Общее название этого треугольника – политоп – фигура с плоскими сторонами (например, бриллиант). В-третьих, подвал может вместить не более 21/(½) = 42 автоматов или 21/(1½) = 14 бочек масла (рис. 2).
Чтобы найти идеальное соотношение автоматов и бочек введем в задачу понятие линии уровня функции . Такая линия в оптимизационной модели включает значения, приносящие одинаковую прибыль. Линию уровня можно задать уравнением:
(195 – 150) * N автоматов + (150 – 100) * N бочек масла = С,
где С – константа.
Например, при С = 450, линия будет проходить через координаты (0;10) и (9;0). Графически идея максимизации прибыли реализуется перемещением линии уровня параллельно самой себе в направлении увеличения значений по осям Х и Y (рис. 3). Любопытно, что для политопа оптимум всегда лежит в одной из вершин (или единственного решения не существует вовсе). На этом свойстве основан алгоритм симплексного метода. Решение задачи в Excel начинают с создания области модели (рис. 4). Формула целевой функции в ячейке В1 =СУММПРОИЗВ(C4:D4;C10:D10).
Рис. 3. Линия уровня и функция для оптимизации прибыли: а) некое произвольное начальное положение; б) линия уровня в оптимальном положении
У вас всё готово, чтобы нажать кнопку ДАННЫЕ –> Поиск решения . (Если вы не видите этой кнопки, установите надстройку Поиск решения; см. , глава 1). В открывшемся окне Параметры поиска решения задайте выделенные опции и нажмите Найти решение .
Рис. 5. Окно Поиск решения
Excel обновит лист и внесет на него результаты расчета (рис. 6).
Что произойдет, если добавить нелинейность? Допустим ваш посредник предлагает $500, если число автоматов в месяц будет более 5. Просто добавьте функцию ЕСЛИ в ячейку с прибылью (В1). Теперь целевая функция выглядит так: =СУММПРОИЗВ(C4:D4;C10:D10)+ЕСЛИ(C4>5;500;0). Жмем Поиск решения . Неудача, Excel сообщает об ошибке – условия линейности не выполнены (рис. 7).
Можно попробовать эволюционный алгоритм, лучше всего работающий с нелинейными моделями, и практически не ограничивающий вас в выборе функций. Работа эволюционного алгоритма в чем-то повторяет принципы работы биологической эволюции:
К сожалению, с эволюционным алгоритмом все же возникают некоторые проблемы:
Принимая во внимание последний пункт, для решения задачи с автоматами и маслом вам нужно добавить ограничение, согласно которому оба решения не должны быть больше 25 (рис. 8). Установив основные параметры модели, кликните на кнопку Параметры . Проработав около минуты, эволюционный алгоритм выдал ожидаемое решение – 6 автоматов и 9 бочек масла. Поскольку без бонуса оптимально сделать лишь три автомата, а бонус выплачивается при производстве более 5 автоматов, очевидно, что оптимальным будет выбор 6 автоматов.
Рассмотрим теперь более сложный пример. Вы работаете в компании, которая производит апельсиновый сок, смешивая натуральные соки разных сортов (рис. 9). Чтобы ваш сок отвечал самым изысканным требованиям:
Шеф сообщил вам, что на январь и февраль он ожидает спросу на уровне 600 000 галлонов сока в месяц, а в марте – 700 000 галлонов. И еще, имеется договор со штатом Флорида, предоставляющий налоговые льготы при условии, что компания покупает не менее 40% сока каждый месяц у фермеров, выращивающих сорт Valencia . Договор следует соблюсти.
Рис. 9. Список характеристик для производства свежевыжатого апельсинового сока (чтобы увеличить изображение, кликните на нем правой кнопкой мыши, и выберите Открыть картинку в новой вкладке )
Создайте оптимизационную модель (рис. 10). Формулы можно изучить на соответствующем листе, приложенного Excel-файла. Кликните Поиск решения , и введите параметры (рис. 11). Нажмите Найти решение .
Рис. 11. Заполненное окно Поиск решения для задачи смешивания
Запустив Поиск решения , вы находите оптимальную стоимость закупок - $1,23 млн. (рис. 12). Обратите внимание, что заказ флоридской Valencia проходит по нижней границе условия. Очевидно, эта сделка - не лучший вариант, но приходится смириться. Второй по популярности сорт - это Verna из Мексики, которая чертовски дешева, но ровно настолько же ужасна.
Вы представляете результаты расчета шефу, но он остается недоволен, и говорит о том, что не хочет выходить за бюджет $1,17 млн. Вы возвращаетесь к компьютеру и начинаете понимать, что стоимость перестала быть целевой функцией. Теперь это условие! А какова цель? Вы можете снизить стоимость закупок только смягчив требования к качеству. Вы решаете сформулировать их в терминах процентного сокращения, и делаете новую модель (рис. 13).
Обратите внимание, что в ячейках В26:29 и F26:F29 теперь не константы, а формулы. Ваша новая цель – минимизация процента снижения качества в ячейках G26:G29. Точнее, вы бы хотели минимизировать максимальное из значений в ячейках G26:G29. Однако, если в ячейку D2 поместить формулу =МАКС(G26:G29), модель не будет работать. Напоминаю, функция МАКС не является линейной. Здесь доступна маленькая хитрость – можно внести дополнительное условие в модель: $G$26:$G$29<=$D$2 (рис. 14), а ячейку D2 оставить пустой. Т.е., ячейка D2 будет оптимизироваться не благодаря наличию в ней формулы, а последовательными циклами, запускаемыми этим дополнительным условием.
Нажмите Найти решение . Симплексный алгоритм будет пытаться приблизить D2 к 0 как целевую функцию модели, в то время как ограничения по вкусу и цвету будут пытаться увеличить ее насколько возможно, чтобы получить пригодную для работы смесь. Где же остановится значение D2? Самое меньшее из возможных значений - максимальный процент из четырех сниженных в диапазоне G26:G29. Мы видим (рис. 15, ячейки С26:Е29), что снижение расходов на 5% потребовало выйти за ограничения качества по всем четырем параметрам.
Вы представили данные шефу, который увидел, что сокращение расходов на 5% не стоит снижения качества сока, поэтому он согласовал ваш первый вариант. Но, когда вы принесли его в отдел снабжения, сотрудники возмутились. Как можно было так раздробить поставки!? Снабженцы настаивают, чтобы вы укрупнили партии: не более 4 поставщиков ежемесячно! И вы садитесь за новую модель. К сожалению, использовать функции ЕСЛИ или СЧЁТ вы не можете, так как хотите остаться в рамках линейной модели. Поэтому вам снова приходится прибегнуть к ухищрениям (рис. 16). Вы добавляете в модель область С33:Е43, которую определяете, как бинарную (значения в ней могут быть только 0 или 1), и оставляете ее пустой. А также область F33:H43, где каждая ячейка равна произведению значения из областей С33:Е43 на G5:G15. В параметры Поиск решения (рис. 17) вы добавляете еще одно условие $С$15:$Е$15 <= $F$33:$H$43 и еще одну область переменных – $C$33:$E$43.
Как в этом случае будет работать оптимизационный алгоритм? Когда он стартует все значения в областях С5:Е15, С33:Е43 и F33:H43 равны нулю. Допустим, что алгоритм пытается в ячейку С7 поместить значение 240. Сработает условие С7 <= F35, которое приведет к увеличению значения в F35, которое, в свою очередь, определяется формулой F35 = C35*$G7. Поскольку G7 – константа, а С35 – бинарная переменная, последней присваивается значение 1. Условие С7 <= F35 выполнено, т.к., 240 <= 1200. Таким образом вы моделируете неудобное условие «если… то»: «если заказ сделан, то бинарная переменная включается».
Нажмите Найти решение . Вы заметите, что решение задачи требует больше времени из-за добавления бинарных переменных. Если по какой-то причине Поиск решения слишком затянул свой поиск, вы всегда можете нажать ESC и увидеть лучшее из найденных решений на данный момент.
В принципе, вы уже довольно продвинутый специалист в области линейного программирования. Но, если вы вошли во вкус, и вам нравится разбираться с моделями всё возрастающей сложности, вот вам еще два зубодробительных примера.
Инженеры сообщили, что на производстве появились новые «снижатели кислотности». Данная технология способна нейтрализовать 20% кислоты в соке, протекающем через прибор. Это не только снижает процент кислоты, но и повышает индекс Брикс/кислотность на 25%. Но для «снижателя» нужна энергия и расходные материалы стоимостью $20 за 1000 галлонов сока. Не весь сок, поступающий от поставщиков, нужно прогонять через этот процесс, однако, если поставка по какому-нибудь заказу прогоняется через ионообменник, то должен быть обработан весь ее объем. Постройте модель с участием ионообменника для снижения стоимости.
Проблема с новым правилом заключается в том, что естественный способ его моделирования - нелинейный, что приведет к использованию медленного алгоритма оптимизации. Но, как и в предыдущем примере, можно ввести бинарную переменную в области С25:Е35, которая бы «включалась» при необходимости понизить кислотность партии (рис. 18). Поскольку, нельзя использовать произведение «индикатор понижения кислотности (бинарный) * объем партии», вы создаете область С37:Е47, которая вам пригодятся для уравнивания объемов, подлежащих снижению кислотности, без прямого участия в формулах самих этих объемов. Итак, области С25:Е35 и С37:Е47 не содержат формул. В области G25:I35 используются формулы =С25:Е35*G5:G15 (это ограничение партии общим доступным объемом сока), а в области К25:М35 =Е5:E15-GG5:15*(1-Е25:E35). Это условие заработает только если партия подлежит снижению кислотности.
Также в модели со «снижателем кислотности» были изменены формулы в ячейках С16:Е16 (теперь они учитывают затраты на снижение кислотности по формуле «индикатор (бинарный) * объем партии * $20) и в ячейках С50:Е51 (теперь они учитывают повышение коэффициента Брикс/кислотность на 25% и снижение кислотности на 20% для обработанных партий). В параметрах Поиска решения появились новые переменные и дополнительные условие (рис. 19). К сожалению, нажав кнопку Найти решение , вы узнаете, что надстройка Поиск решения не может справиться с задачей (рис. 20). Модель стали слишком сложной.
Рис. 19. Параметры Поиска решения в модели со «снижателем кислотности»
Рис. 20. Поиск решения не справляется с задачей
Вам нужно загрузить и установить OpenSolver (как это сделать см. , глава 1). OpenSolver «подхватит» установки, введенные только что в окне Поиск решения . Поэтому просто нажмите кнопку Solver . Полученное решение – $1 235 927 более чем на $ 100 000 лучше предыдущего минимума – $1 338 913.
До сих пор мы считали, что поставляемая продукция имеет точно указанные параметры. Резонно предположить, что эти параметры подвержены вариации, характеризуемой среднеквадратичным отклонением (рис. 21; подробнее см. ). Самое известное и широко используемое распределение случайной величины - это нормальное распределение, иначе называемое «колоколообразной кривой». Скажем, в случае с соком из Египта среднее значение отношения Брикс/кислотность будет 13, а среднеквадратичное отклонение (также называемой стандартным отклонением) - 0,9 (рис. 21). В данном примере 13 - это центр распределения вероятности, 68% заказов будут в пределах ±0,9 от 13, а 95% будут в пределах ±1,8 от 13.
Ваша цель - предложить план смешивания стоимостью меньше $1,25 миллиона, который наилучшим образом соответствует ожиданиям по качеству в свете вариабельности поставок.
Мы используем среднее и среднеквадратичное отклонение характеристик, чтобы применить имитационное моделирование по методу Монте-Карло (если вы слышите это название впервые, рекомендую ). В этом методе вместо включения параметров распределения (среднего значения и среднеквадратичного отклонения) в модель напрямую, создается большое число сценариев, основанных на этих самых параметрах распределения.
Сценарий - это один из возможных ответов на вопрос: «Если это - распределения, основанные на статистике, на что же будет похож конкретный заказ?» Каждый сценарий включает сорок параметров десяти сортов сока (рис. 22). Чтобы получить один такой параметр, воспользуйтесь функцией НОРМ.ОБР (подробнее о функции см. ). Например, в ячейке В33 отношение Брикс/кислотность для сорта Hamlin определяется формулой =НОРМ.ОБР(СЛЧИС();H5;N5). Введите аналогичные формулы в область В33:СW76, сгенерировав 100 сценариев. Поиск решения не сможет работать с этими формулами, так как они нелинейны, поэтому скопируйте их в буфер и вставьте, но уже, как значения.
Цель минимизировать значение в ячейке D2. Т.е., найти решение, которое менее всего снижает границы качества для 100 сценариев. Как и в примерах на рис. 13–15, в ячейке D2 нет формулы. Оптимизация выполняется заданием параметров в окне Поиск решения. Все, что нужно - это поместить во все сценарии границы качества, а не просто ожидаемые значения характеристик. Таким образом, в отношение Брикс/кислотность вы добавляете условия B78:CW80 >= B26 и =< F26, затем проделываете то же самое с кислотностью, вяжущей составляющей вкуса и цветом (рис. 24). Нажмите Найти решение . Решение найдется довольно быстро. Если вы генерировали случайные значения сами, а не использовали те, что находятся в файле для загрузки, ваше решение может отличаться. Для моей сотни сценариев наилучшим показателем, который мне удалось получить, является изменение качества на 133%.
Рис. 24. Настройка Поиска решения для модели с вариабельностью характеристик
Если вы хотите расширить свои знания в области линейного программирования, рекомендую книгу The AIMMS optimization modeling book . Не пропустите две главы про трюки и подсказки – они поистине гениальны.
Написано по материалам книги Джона Формана . – М.: Альпина Паблишер, 2016. – С. 129–186. Насчет секретности разработки и Второй мировой – это, похоже, личное мнение автора книги. См. Википедию . – Прим. Багузина .
#ЭМММ #Excel #Матпрограммирование #ПоискРешения #Easyhelp
.
- Простая задача линейного программирования №3. Симплекс-метод для поиска минимума.
- Решение задачи линейного программирования алгоритмом двойственного симплекс-метода
- Решения прямой, двойственной задач ЛП, построение двойственной задачи ЛП.
- Решение задачи линейного программирования с неоднотипными неравенствами симплекс-методом
- Задача линейного программирования с системой уравнений
#Excel #матпрограммирование #easyhelp
Решение лабораторных работ в Excel на заказ
Как и обещал в ходе изложения материала, ссылка на первый видеоурок из серии задач о раскрое материалов:
В нашей подборке вы также можете найти больше видеоуроков по решению прикладных задач в Excel
Больше других обучающих видеоуроков вы сможете найти на нашем сайте
#excel #матпрограммирование #ТранспортнаяЗадача #ЛинейноеПрограммирование #ПоискРешения #easyhelp #АнализУстойчивости
Простая задача линейного программирования №1. Симплекс-метод для поиска минимума.
- Простая задача линейного программирования №2. Симплекс-метод для поиска максимума.
- Решение задачи линейного программирования алгоритмом двойственного симплекс-метода
- Решения прямой, двойственной задач ЛП, построение двойственной задачи ЛП.
- Решение задачи линейного программирования с неоднотипными неравенствами симплекс-методом
- Задача линейного программирования с системой уравнений
Если данное видео принесло вам реальную пользу и вы хотите отблагодарить автора:
WMR: R370550256930
WMZ: Z939960413056
В нашей подборке вы можете найти больше видеоуроков по работе с электронными таблицами Microsoft Excel:
Еще больше других обучающих видеоуроков вы сможете найти на нашем сайте.
В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel , нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel » внизу окна:
Далее в открывшемся списке нужно выбрать Надстройки
, затем установить курсор на пункт Поиск решения
, нажать кнопку Перейти
и в следующем окне включить пакет анализа.
Заполните данные
Значение переменных X i может различаться, но целевая функция F(x) должна иметь такое же значение.
Иногда задание звучит следующим образом: расчеты осуществить на ЭВМ, привести распечатку полученных результатов.
MS Excel позволяет представить результаты поиска решения в форме отчета. Существует три типа таких отчетов:
Пример . В библиотеке работают 6 пожилых уборщиц. Каждая из них по своим физическим возможностям и состоянию здоровья может выполнять только определенные виды работ, причем с определенной производительностью. Площадь каждой из работ известна. Нужно добиться минимума времени на уборку помещений.
ПРОИЗВОДИТЕЛЬНОСТЬ БАБУШЕК м 2 . /мин |
|||||||
| Баба Аня | Белла Петровна | Баба Варя | Баба Галя | Домна Ивановна | Евгения Карловна | Площадь работ | |
| Мытье окон | 2 | 0 | 0 | 1 | 0 | 0 | 46 |
| Мытье полов | 0 | 1 | 0 | 0 | 0 | 0 | 300 |
| Протирка столов | 0 | 0 | 2 | 0 | 0.2 | 1 | 50 |
| Чистка дорожек | 0 | 0 | 0 | 2 | 0 | 4 | 100 |
Пример
.На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
Найти оптимальное соотношение количества кормов и численности поголовья лис и песцов.
1. Преобразовываем неравенства в равенства
2. Находим начальное допустимое базисное решение
3. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, то процесс закончен.
4. На основе условия допустимости выбираем исключаемая переменная
5. Вычисляем элементы новой ведущей строки
новая ведущая строка = текущая строка/ведущий элемент
6. Вычисляем элементы остальных строк, включая z-строку
новая строка = текущая строка – ее коэффициенты в ведущем столбце * новую ведущую строку
Переходим к шагу 3.
Для удобства записи итерационного процесса все значения записываем в Симплекс-таблицу.
Для многих задач оптимизации удобно применять модель линейного программирования. Суть задачи заключается в составлении системы неравенств, описывающих соответствующие ограничения задачи и задания функции оптимизации.
Для нахождения решения в подобных моделях, можно использовать средство MS EXCEL – ПОИСК РЕШЕНИЯ.
Рассмотрим, как составить модель линейного программирования и найти ее решение на примере.
На трех станках обрабатываются детали двух видов (А и Б), причем каждая деталь проходит обработку на всех станках. Известно время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль от продажи одной детали каждого вида (данные в таблице). Составить план производства, обеспечивающий наибольшую прибыль.
Обозначим через х 1 и х 2 количество единиц деталей видов А и Б, планируемое к выпуску. Тогда время обработки х 1 деталей вида А на первом станке составляет 1* х 1 ; х 2 деталей вида Б соответственно 2*х 2 . Суммарное время работы станка I для изготовления планируемого количества деталей равно х 1 +2*х 2 , оно ограничено 16 часами работы этого станка в течение одного цикла производства. Поэтому должно выполняться неравенство:
х 1 +2*х 2 <=16;
Аналогично для станков II и III получаем неравенства соответственно:
х 1 + х 2 <=10;
3*х 1 + х 2 <=24;
Кроме того, по смыслу определения веденных величин х 1 и х 2 , должны выполняться условия: х 1 >=0; х 2 >=0;
Таким образом, получаем систему неравенств, называемую системой ограничений задачи:
Любое решение (х 1 ; х 2) системы ограничений называется планом выпуска продукции или допустимым планом задачи.
Прибыль от реализации х 1 единиц деталей вида А равна 4 . х 1 , а прибыль от реализации х 2 единиц деталей вида Б равна 2х 2. Суммарная прибыль от реализации продукции, выпущенной согласно плану (х 1 ; х 2) равна:
F (х 1 ; х 2 )=4х 1 +2х 2 (тыс. руб).
Линейная функция F (х 1 ; х 2 ) называется целевой функцией задачи.
По условию задачи требуется найти такой план (х 1 ; х 2) при котором прибыль была бы максимальной.
Таким образом, построена математическая модель задачи как задачи линейного программирования:
F (х 1 ; х 2 )=4х 1 +2х 2 → max
