Svinkovod.ru

Бытовая техника
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Пример задачи линейного программирования в Excel

Теперь данную задачу для решения запишем в Excel

отображение формул

В ячейке E4 вставим формулу
=A4*A5+B4*B5+C4*C5+D4*D5

Для ячейки E7, E8 и E9 формула будет иметь вид

=$A$4*A7+$B$4*B7+$C$4*C7+$D$4*D7
=$A$4*A8+$B$4*B8+$C$4*C8+$D$4*D8
=$A$4*A9+$B$4*B9+$C$4*C9+$D$4*D9

Также можно воспользоваться формулой:
=СУММПРОИЗВ(A4:D4;A7:D7)

На вкладке данные переходим в Поиск решения

Выбираем ячейку с целевой функцией, ставим галочку максимум, далее выбираем ячейки изменяемых переменных ($A$4:$D$4) и добавляем ограничения при помощи кнопки Добавить. Также ставим галочку переменные без ограничений неотрицательные, выбираем, выбираем метод решения – симплекс-метод решения линейных задач.

симплекс-метода в Excel поиск решения линейной задачи

Ограничения больше меньше или равно ExcelОграничения для целых чисел Excel

Можно также перейти в параметры и настроить точность.

Параметры точности симплекс метода

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

Результат поиска решения Excel

В итоги получили решения задачи

Z=2015
x1=19; x2=42; x3=0; x4=15

Результат решения задачи симплекс методом в Excel

Насколько публикация полезна?

Нажмите на звезду, чтобы оценить!

Средняя оценка 5 / 5. Количество оценок: 7

Оценок пока нет. Поставьте оценку первым.

5038

Линейное программирование в Excel

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:


Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel , необходимо выполнить следующие действия:
1. Ввести условие задачи:
a) создать экранную форму для ввода условия задачи:
· переменных,
· целевой функции (ЦФ),
· ограничений,
· граничных условий;
b) ввести исходные данные в экранную форму:
· коэффициенты ЦФ,
· коэффициенты при переменных в ограничениях,
· правые части ограничений;
c) ввести зависимости из математической модели в экранную форму:
· формулу для расчета ЦФ,
· формулы для расчета значений левых частей ограничений;
d) задать ЦФ (в окне «Поиск решения» ):
· целевую ячейку,
· направление оптимизации ЦФ;
e) ввести ограничения и граничные условия (в окне «Поиск решения» ):
· ячейки со значениями переменных,
· граничные условия для допустимых значений переменных,
· соотношения между правыми и левыми частями ограничений.
2. Решить задачу:
a) установить параметры решения задачи (в окне «Поиск решения» );
b) запустить задачу на решение (в окне «Поиск решения» );
c) выбрать формат вывода решения (в окне «Результаты поиска решения» ).

Рассмотрим подробно использование MS Excel на примере решения следующей задачи.

Фабрика «GRM pic» выпускает два вида каш для завтрака — «Crunchy» и «Chewy». Используемые для производства обоих продуктов ингредиенты в основ­ном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.

Управляющему производством Джою Дисону необходимо разработать план производства на месяц. В приведенной ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т продукта.

ЦехНеобходимый фонд рабочего времени
чел.-ч/т
Общий фонд рабочего времени
чел.-ч. в месяц
«Crunchy»«Chewy»
А. Производство1041000
В. Добавка приправ32360
С. Упаковка25600

Доход от производства 1 т «Crunchy» составляет 150 ф. ст., а от производства «Chewy» — 75 ф, ст. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.

а) Сформулировать модель линейного программирования, максимизи­рующую общий доход фабрики за месяц.

б) Решить ее c помощью MS Excel.

Ввод исходных данных
Создание экранной формы и ввод исходных данных

Читайте так же:
Можно ли в повер поинте вставить видео

Экранная форма для решения в MS Excel представлена на рисунке 1.

В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (x1), C4 (x2), коэффициентам ЦФ соответствуют ячейки B6 (c1=150), C6 (c2=75), правым частям ограничений соответствуют ячейки D18 (b1=1000), D19 (b2=360), D20 (b3=600) и т.д.

Ввод зависимостей из формальной постановки задачи в экранную форму

Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ , которая вычисляет сумму попарных произведений двух или более массивов.

Одним из самых простых способов определения функций в MS Excel является использование режима «Вставка функций» , который можно вызвать из меню «Вставка» или при нажатии кнопки fx (рисунок 2) на стандартной панели инструментов.

Рисунок 2

Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:
· курсор в поле D6;
· нажав кнопку fx , вызовите окно «Мастер функций — шаг 1 из 2»;
· выберите в окне «Категория» категорию «Математические»;
· в окне «Функция» выберите функцию СУММПРОИЗВ (рис. 3);

Рисунок 3
· в появившемся окне «СУММПРОИЗВ» в строку «Массив 1» введите выражение B$4:C$4 , а в строку «Массив 2» — выражение B6:C6 (рис. 4);

Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи ( B3, C3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения ( B13, C13 — 1-е ограничение; B14, С14 — 2-е ограничение и B15, С15 — 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Таблица 1.

Формулы, описывающие ограничения модели (1)

Левая часть ограниченияФормула Excel
10x1+4x2 или B3×B13+C3×C13=СУММПРОИЗВ(B4:C4;B13:C13))
3x1+2x2 или B3×B14+C3×C14=СУММПРОИЗВ(B4:C4;B14:C14))
2x1+5x2 или B3×B15+C3×C15=СУММПРОИЗВ(B4:C4;B15:C15)

Дальнейшие действия производятся в окне «Поиск решения» , которое вызывается из меню «Сервис» (рис.5):

· поставьте курсор в поле «Установить целевую ячейку» ;

· введите адрес целевой ячейки $D$6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;

· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке «максимальному значению».

Ввод ограничений и граничных условий
Задание ячеек переменных

В окно «Поиск решения» в поле «Изменяя ячейки» впишите адреса $B$4:$С$4 . Необходимые адреса можно вносить в поле «Изменяя ячейки» и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных

В нашем случае на значения переменных накладывается только граничное условие неотрицательности, то есть их нижняя граница должна быть равна нулю (см. рис. 1).
· Нажмите кнопку «Добавить» , после чего появится окно «Добавление ограничения» (рис.6).
· В поле «Ссылка на ячейку» введите адреса ячеек переменных $B$4:$С$4 . Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.
· В поле знака откройте список предлагаемых знаков и выберите ≥ .
· В поле «Ограничение» введите 0.

Рис.6 — Добавление условия неотрицательности переменных задачи (1)

Читайте так же:
Как вернуть старый интерфейс гугл хром

Задание знаков ограничений ≤ , ≥ , = .
· Нажмите кнопку «Добавить» в окне «Добавление ограничения» .
· В поле «Ссылка на ячейку» введите адрес ячейки левой части конкретного ограничения, например $B$18 . Это можно сделать как с клавиатуры, так и путем выделения мышью нужной ячейки непосредственно в экранной форме.
· В соответствии с условием задачи (1) выбрать в поле знака необходимый знак, например, ≤ .
· В поле «Ограничение» введите адрес ячейки правой части рассматриваемого ограничения, например $D$18 .
· Аналогично введите ограничения: $B$19<=$D$19 , $B$20<=$D$20 .
· Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK .

Окно «Поиск решения» после ввода всех необходимых данных задачи (1) представлено на рис. 5.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки «Изменить» или «Удалить» (см. рис. 5).

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

Задача запускается на решение в окне «Поиск решения» . Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку «Параметры» и заполнить некоторые поля окна «Параметры поиска решения» (рис. 7).

Рис. 7 — Параметры поиска решения, подходящие для большинства задач ЛП

Параметр «Максимальное время» служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр «Предельное число итераций» служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр «Относительная погрешность» служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр «Допустимое отклонение» служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр «Сходимость» применяется только при решении нелинейных задач.Установка флажка «Линейная модель» обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Подтвердите установленные параметры нажатием кнопки «OK» .

Запуск задачи на решение
Запуск задачи на решение производится из окна «Поиск решения» путем нажатия кнопки «Выполнить» .

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

Рис. 8 -. Сообщение об успешном решении задачи

Появление иного сообщения свидетельствует не о характере оптимального решения задачи, а о том, что при вводе условий задачи в MS Excel были допущены ошибки, не позволяющие MS Excel найти оптимальное решение, которое в действительности существует.
Если при заполнении полей окна «Поиск решения» были допущены ошибки, не позволяющие MS Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра «Относительная погрешность» не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.
В окне «Результаты поиска решения» представлены названия трех типов отчетов: «Результаты», «Устойчивость», «Пределы» . Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку «OK» . После этого в экранной форме появляется оптимальное решение задачи (рис. 9).

Читайте так же:
Как вернуть в ворде исходный документ

Метод поиска решения в excel

MS Excel содержит модуль «Поиск решения» позволяющий осуществлять поиск оптимальных решений, в том числе решение задач линейного, целочисленного, нелинейного и стохастического программирования.

Для подключения этого модуля необходимо перейти Сервис/Надстройки,

и в появившемся окне

поставить галочку рядом с надписью "Поиск решения", нажать ОК .
Дальше вставьте диск, с которого устанавливалась программа Excel и нажмите ОК

Постановка задачи осуществляется посредством задания ячеек для переменных и записи формул с использованием этих ячеек для целевой функции и системы ограничений. Например, на рис. 1.1 приведена постановка задачи линейного программирования с целочисленным решением.

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

S = 60*x1+70*x2+120*x3+130*x4 → max

4*x1+6*x2+10*x3+13*x4 ≤ 150

x1, x2, x3, x4 ≥ 0 — целые

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

Рис.1.1. Модуль «Поиск решения» программы MS Excel

Рис.1.1. Модуль «Поиск решения» программы MS Excel

Далее, переходим к решению. Выбираем в меню «Сервис | Поиск решения». Открывается диалоговое окно «Поиск решения». Здесь указывается ячейки целевой функции, переменных и устанавливаются ограничения исходя из системы ограничений. Можно начать решение, или установить «параметры» решения (рис.1.2).

Рис.1.2. Окно «Параметры поиска решения» модуля «Поиск решения»

Рис.1.2. Окно «Параметры поиска решения» модуля «Поиск решения»

Здесь устанавливаем «параметры» задачи — выбираем «линейная модель», «неотрицательные значения» и «показывать результаты итераций».

«Линейная модель» — служит для ускорения поиска решения линейной задачи оптимизации. «Показывать результаты итераций» — служит для приостановки поиска решения для просмотра результатов отдельных итераций.

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

«Метод Ньютона» — реализация квазиньютоновского метода, в котором запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов.

«Метод сопряженных градиентов» — реализация метода сопряженных градиентов, в котором запрашивается меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях.

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

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

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

Функция Microsoft Excel: поиск решения

Поиск решения в Microsoft Excel

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

Читайте так же:
Меню сервис в excel 2007

Включение функции

Можно долго искать на ленте, где находится Поиск решения, но так и не найти данный инструмент. Просто, для активации данной функции, нужно её включить в настройках программы.

Для того, чтобы произвести активацию Поиска решений в программе Microsoft Excel 2010 года, и более поздних версий, переходим во вкладку «Файл». Для версии 2007 года, следует нажать на кнопку Microsoft Office в левом верхнем углу окна. В открывшемся окне, переходим в раздел «Параметры».

Переход в раздел Параметры в Microsoft Excel

В окне параметров кликаем по пункту «Надстройки». После перехода, в нижней части окна, напротив параметра «Управление» выбираем значение «Надстройки Excel», и кликаем по кнопке «Перейти».

Переход в надстройки в Microsoft Excel

Открывается окно с надстройками. Ставим галочку напротив наименования нужной нам надстройки – «Поиск решения». Жмем на кнопку «OK».

Активация функции Поиск решения в Microsoft Excel

После этого, кнопка для запуска функции Поиска решений появится на ленте Excel во вкладке «Данные».

Функция поиск решения активирована в Microsoft Excel

Подготовка таблицы

Теперь, после того, как мы активировали функцию, давайте разберемся, как она работает. Легче всего это представить на конкретном примере. Итак, у нас есть таблица заработной платы работников предприятия. Нам следует рассчитать премию каждого работника, которая является произведением заработной платы, указанной в отдельном столбце, на определенный коэффициент. При этом, общая сумма денежных средств, выделяемых на премию, равна 30000 рублей. Ячейка, в которой находится данная сумма, имеет название целевой, так как наша цель подобрать данные именно под это число.

Целевая ячейка в Microsoft Excel

Коэффициент, который применяется для расчета суммы премии, нам предстоит вычислить с помощью функции Поиска решений. Ячейка, в которой он располагается, называется искомой.

Искомая ячейка в Microsoft Excel

Целевая и искомая ячейка должны быть связанны друг с другом с помощью формулы. В нашем конкретном случае, формула располагается в целевой ячейке, и имеет следующий вид: «=C10*$G$3», где $G$3 – абсолютный адрес искомой ячейки, а «C10» — общая сумма заработной платы, от которой производится расчет премии работникам предприятия.

Связующая формула в Microsoft Excel

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

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

Запуск поиска решений в Microsoft Excel

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

Переход к вводу целевой ячейки в Microsoft Excel

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

Выбор целевой ячейки в Microsoft Excel

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

Установка значения целевой ячейки в Microsoft Excel

Ниже расположено поле «Изменяя ячейки переменных». Тут нужно указать адрес искомой ячейки, где, как мы помним, находится коэффициент, умножением на который основной заработной платы будет рассчитана величина премии. Адрес можно прописать теми же способами, как мы это делали для целевой ячейки.

Читайте так же:
Генерация случайных чисел в excel 2016

Установка искомой ячейки в Microsoft Excel

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

Добавление ограничения в Microsoft Excel

После этого, открывается окно добавления ограничения. В поле «Ссылка на ячейки» прописываем адрес ячеек, относительно которых вводится ограничение. В нашем случае, это искомая ячейка с коэффициентом. Далее проставляем нужный знак: «меньше или равно», «больше или равно», «равно», «целое число», «бинарное», и т.д. В нашем случае, мы выберем знак «больше или равно», чтобы сделать коэффициент положительным числом. Соответственно, в поле «Ограничение» указываем число 0. Если мы хотим настроить ещё одно ограничение, то жмем на кнопку «Добавить». В обратном случае, жмем на кнопку «OK», чтобы сохранить введенные ограничения.

Параметры ограничения в Microsoft Excel

Как видим, после этого, ограничение появляется в соответствующем поле окна параметров поиска решения. Также, сделать переменные неотрицательными, можно установив галочку около соответствующего параметра чуть ниже. Желательно, чтобы установленный тут параметр не противоречил тем, которые вы прописали в ограничениях, иначе, может возникнуть конфликт.

Установка неотрицательных значений в Microsoft Excel

Дополнительные настройки можно задать, кликнув по кнопке «Параметры».

Переход к параметрам поиска решений в Microsoft Excel

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

Параметры Поиска решения в Microsoft Excel

После того, как все настройки установлены, жмем на кнопку «Найти решение».

Переход к поиску решения в Microsoft Excel

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

Результаты поиска решений в Microsoft Excel

Если по какой-либо причине результаты поиска решений вас не удовлетворяют, или при их подсчете программа выдаёт ошибку, то, в таком случае, возвращаемся, описанным выше способом, в диалоговое окно параметров. Пересматриваем все введенные данные, так как возможно где-то была допущена ошибка. В случае, если ошибка найдена не была, то переходим к параметру «Выберите метод решения». Тут предоставляется возможность выбора одного из трех способов расчета: «Поиск решения нелинейных задач методом ОПГ», «Поиск решения линейных задач симплекс-методом», и «Эволюционный поиск решения». По умолчанию, используется первый метод. Пробуем решить поставленную задачу, выбрав любой другой метод. В случае неудачи, повторяем попытку, с использованием последнего метода. Алгоритм действий всё тот же, который мы описывали выше.

Выбор метода решения в Microsoft Excel

Как видим, функция Поиск решения представляет собой довольно интересный инструмент, который, при правильном использовании, может значительно сэкономить время пользователя на различных подсчетах. К сожалению, далеко не каждый пользователь знает о его существовании, не говоря о том, чтобы правильно уметь работать с этой надстройкой. В чем-то данный инструмент напоминает функцию «Подбор параметра…», но в то же время, имеет и существенные различия с ним.

ЗакрытьМы рады, что смогли помочь Вам в решении проблемы.

Помимо этой статьи, на сайте еще 12447 инструкций.
Добавьте сайт Lumpics.ru в закладки (CTRL+D) и мы точно еще пригодимся вам.

Отблагодарите автора, поделитесь статьей в социальных сетях.

ЗакрытьОпишите, что у вас не получилось. Наши специалисты постараются ответить максимально быстро.

голоса
Рейтинг статьи
Ссылка на основную публикацию
Adblock
detector