Цель работы:изучение современных программных средств решения задачи линейного программирования; практическое решение задач линейного программирования графическим методом, симплекс-методом и средствами программыMicrosoftExcel; программная реализация симплекс-метода на языке программирования высокого уровня.
1. Теоретическая часть
Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения, обращение к которой производится из меню Сервис.
Если команда Поиск решения отсутствует в меню Сервис, то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки, которая открывает диалоговое окно, показанное на рис. 1.
Далее в этом окне устанавливается флажок той надстройки, которую необходимо загрузить, и нажимается кнопка OK.
Покажем использование надстройки «Поиск решения» на примере решения следующей задачи.
Решение задачи о распределении ресурсов с помощью Поиска решений
Постановка задачи
Предприятие изготавливает и реализует три вида продукции – P1, Р2 и Р3. Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.
Расходы ресурсов на 1 ед. продукции
Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P1, Р2 и Р3 соответственно.
Требуется определить производственную программу предприятия таким образом, чтобы прибыль от реализации продукции была максимальной.
Математическая модель задачи
Обозначим переменными x1, x2 и x3 искомые объемы производства продукции видов P1, Р2 и Р2, а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.
Определить значения переменных x1, x2 и x3, для которых достигается максимум целевой функции
F = 240 x1 + 210 х2 + 180 x3
Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия
Порядок оптимального решения задачи
Примерные действия, необходимые для решения задачи линейного программирования средствами программы Excel, представим в виде последовательности шагов.
Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.
Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.
Решение задач оптимального планирования в Microsoft Excel
Шаг 2. В ячейку E3 вводится формула
для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.
Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.
Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения, которая открывает диалоговое окно, приведенное на рис. 3.
В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).
Затем в этом окне (рис. 3) заполняются следующие поля этого окна:
— в поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);
— в поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);
— в поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить. В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.
В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).
Следует заметить, что заполнение полей Ссылка на ячейку и Ограничение в окне «Добавление ограничения» можно выполнить выделением соответствующих ячеек рабочего листа электронной таблицы.
Затем выбирается вид отношения, связывающего левую и правую части ограничения, что показано на рис. 5.
После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.
Замечание. В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).
Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.
В этом окне требуется установить флажки Линейная модель для решения задачи линейного программирования и Неотрицательные значения, если такое условие накладываются на все переменные задачи.
Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.
Шаг 6. Задав необходимые параметры в окне «Параметры поиска решения», следует нажать на кнопку Выполнить для поиска решения задачи (рис. 3) в окне «Поиск решения». Если решение найдено, то на экран выводится окно с соответствующим сообщением (рис. 7).
Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных — в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.
Таким образом, получено оптимальное решение исходной задачи в виде вектора 
, где
,
и
, для которого значение целевой функцииF максимально и составляет F* = 129825.
Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам, Отчет по устойчивости и Отчет по пределам. Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.
Отчет по результатам для рассмотренной задачи показан на рис. 9.
В данном отчете представлены оптимальное решение задачи линейного программирования и его расположение в области допустимых решений. В графах Результат выводятся оптимальные значения целевой функции F* и переменных задачи 
Состояние ограничений (графа Статус) характеризует расположение точки 
в области допустимых решений. ГрафаРазница показывает разности между значениями левых и правых частей ограничений (невязки). Для связанного ограничения невязка равна нулю, что свидетельствует о расположение точки 
на границе области допустимых решений, которая задается этим ограничением. Если ограничение являются не связанным, то оно не влияет на оптимальное решение.
Замечание. В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами.
Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.
В отчете по устойчивости (рис. 10) приведены границы устойчивости переменных задачи (графы Допустимое увеличение и Допустимое уменьшение коэффициентов целевой функции), а также границы устойчивости теневых цен (т.е. переменных двойственной задачи), в пределах которых оптимальное решение не изменяется. Большие значения пределов (1Е+30) означают фактическое отсутствие соответствующих границ, т.е. переменная может изменяться до бесконечности.
В графе Нормированная стоимость элемент во второй строке (-150) показывает, на сколько уменьшится значение функции, если в решении переменную x2 увеличить на единицу. С другой стороны, при допустимом увеличении коэффициента функции при неизвестной x2 на 150 единиц значение этой переменной не изменится, т.е. неизвестная x2 будет равна нулю, а если выйти за пределы допустимого увеличения (коэффициент при x2 увеличить более чем на 150), то неизвестная x2 в решении будет больше нуля.
В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат) при этих изменениях. В частности, если x1 = 0, а x2 и x3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x3 = 0 и неизменных x1 и x2 получим F = 240397,5 + 2100 + 1800 = 95400.
Источник: studfile.net
Ищем оптимальное решение задачи с неизвестными параметрами в Excel
«Поиск решений» — функция Excel, которую используют для оптимизации параметров: прибыли, плана продаж, схемы доставки грузов, маркетингового бюджета или рентабельности. Она помогает составить расписание сотрудников, распределить расходы в бизнес-плане или инвестиционные вложения. Знание этой функции экономит много времени и сил. Рассказываем, как освоить функцию поиска решений.
Основные параметры поиска решений
Найти решение задачи можно тремя способами. Во-первых, вручную перебирать параметры, пока не найдется оптимальное соотношение. Во-вторых, составить уравнение с большим количеством неизвестных. В-третьих, вбить данные в Excel и использовать «Поиск решений». Последний способ самый быстрый и покажет максимально точное решение, если знать, как использовать функцию.
Итак, мы решаем задачу с помощью поиска решений в Excel и начинаем с математической модели. В ней четыре типа данных: константы, изменяемые ячейки, целевая функция и ограничения. К поиску решения вернемся чуть позже, а сейчас разберемся, что входит в каждый из этих типов:
Константы — исходная информация. К ней относится удельная маржинальная прибыль, стоимость каждой перевозки, нормы расхода товарно-материальных ценностей. В нашем случае — производительность работников, их оплата и норма в 1000 изделий. Также константа отражает ограничения и условия математической модели: например, только неотрицательные или целые значения. Мы вносим константы в таблицу цифрами или с помощью элементарных формул (СУММ, СРЗНАЧ).
Изменяемые ячейки — переменные, которые в итоге нужно найти. В задаче это распределение 1000 изделий между работниками с минимальными затратами. В разных случаях бывает одна изменяемая ячейка или диапазон. При заполнении функции «Поиск решений» важно оставить ячейки пустыми — программа сама найдет значения.
Целевая функция — результирующий показатель, для которого Excel подбирает наилучшие показатели. Чтобы программа понимала, какие данные наилучшие, мы задаем функцию в виде формулы. Эту формулу мы отображаем в отдельной ячейке. Результирующий показатель может принимать максимальное или минимальное значения, а также быть конкретным числом.
Ограничения — условия, которые необходимо учесть при оптимизации функции, называющейся целевой. К ним относятся размеры инвестирования, срок реализации проекта или объем покупательского спроса. В нашем случае — количество дней и число работников.
Пример использования поиска решений
Теперь перейдем к самой функции.
1) Чтобы включить «Поиск решений», выполните следующие шаги:
- нажмите «Параметры Excel», а затем выберите категорию «Надстройки»;
- в поле «Управление» выберите значение «Надстройки Excel» и нажмите кнопку «Перейти»;
- в поле «Доступные надстройки» установите флажок рядом с пунктом «Поиск решения» и нажмите кнопку ОК.
2) Теперь упорядочим данные в виде таблицы, отражающей связи между ячейками. Советуем использовать цветовые обозначения: на примере красным выделена целевая функция, бежевым — ограничения, а желтым — изменяемые ячейки.
Не забудьте ввести формулы. Стоимость заказа рассчитывается как «Оплата труда за 1 изделие» умножить на «Число заготовок, передаваемых в работу». Для того, чтобы узнать «Время на выполнение заказа», нужно «Число заготовок, передаваемых в работу» разделить на «Производительность».
3) Выделите целевую ячейку, которая должна показать максимум, минимум или определенное значение при заданных условиях. Для этого на панели нажмите «Данные» и выберете функцию «Поиск решений» (обычно она в верхнем правом углу).
4) Заполните параметры «Поиска решений» и нажмите «Найти решение».
Совокупная стоимость 1000 изделий рассчитывается как сумма стоимостей количества изделий от каждого работника. Данная ячейка (Е13) — это целевая функция. D9:D12 — изменяемые ячейки. «Поиск решений» определяет их оптимальные значения, чтобы целевая функция достигла минимума при заданных ограничениях.
В нашем примере следующие ограничения:
- общее количество изделий 1000 штук ($D$13 = $D$3);
- число заготовок, передаваемых в работу — целое и больше нуля либо равно нулю ($D$9:$D$12 = целое, $D$9:$D$12 > = 0);
- количество дней меньше либо равно 30 ($F$9:$F$12 < = $D$6, либо как в примере в ячейке F13 задать функцию МАКС(F9:F12) и поставить ограничение $F$13 < = $D$6).
5) В конце проверьте полученные данные на соответствие заданному целевому значению. Если что-то не сходится — нужно пересмотреть исходные данные, введенные формулы и ограничения.
Хотите научиться решать задачи в Excel, как это делают в компаниях-лидерах? Приходите на наш онлайн-курс, на котором вы освоите этот инструмент на уровне профи. Вашими преподавателями будут эксперты-практики, а после обучения вы сможете дополнить резюме весомой строчкой. Регистрируйтесь!
Теги
Получите карьерную поддержку
Если вы не знаете, с чего начать карьеру, зашли в тупик или считаете, что совершили какие-то ошибки, спросите совета у специалистов. Заполните заявку и консультанты Changellenge >> окажут вам помощь. Это отличный шанс вместе экспертом проработать проблемные вопросы и составить карьерный план.
Подписаться на карьерную рассылку
Подписывайтесь на рассылку и получайте карьерные советы — от выбора индустрии и компании до лайфхаков по самоорганизации и развитию коммуникативных навыков.
Младший менеджер проектов в Облако
Стажер в команду внутренних коммуникаций
Sales Intern Ural Federal District
Специалист по кадровому администрированию
Стажер отдела продаж
Стажер отдела маркетинга
Источник: changellenge.com
Excel задания с решениями. Скачать примеры
В этом уроке мы постараемся закрепить то, что прошли на предыдущих. Рассмотрим несколько заданий с примерами решения.
Задание 1
Ниже на рисунке изображена таблица автоматически вычисляющая объем прямоугольной канистры. Даны ее размеры. Это самое простое задание, с которого мы начнем. Для начала постарайтесь добиться решения самостоятельно.
Решение задания
Первое, что необходимо сделать это заполнить ячейки словами «дано», «ширина», «высота» и так далее. Обратите внимание на то, что слово «метра» я вписал один раз, а потом автозаполнением заполнил оставшиеся 2 ячейки. Для того, чтобы отформатировать текст (сделать жирным слова «дано» и «Вычислено» выберите ячейку и воспользуйтесь инструментом Ж (полужирный) на панели вверху в закладке Главная.
После того как вы создали внешний вид таблицы (т.е. вписали в ячейки все кроме цифр) переходим к решению самой задачи. У меня в примере ячейка J5 содержит формулу для вычисления объема. Сама по себе формула просто, чтобы вычислить объем прямоугольного параллелипипеда надо перемножить длины всех его 3 сторон.
В нашем примере значение ширины, высоты и длины содержится в ячейках E5, E6, E7. Как раз их нам надо и перемножить и результат записать в ячейку J5, для этого в ячейке J5 пишем формулу =E5*E6*E7. и жмем Enter.