Линейное программирование в excel поиск решения. Решение задачи линейного программирования в Excel

Рассмотрим линейное программирование в Excel на примере задачи, ранее решенной .

Задача. Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно. Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд. На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц. Необходимо определить количество единиц продуктов А и В, которые Николай доложен производить в следующем месяце для максимизации маржинальной прибыли.

Скачать заметку в формате , пример в формате

1. Воспользуемся математической моделью построенной . Вот эта модель:

Максимизировать: Z = 2500 * х 1 + 3500 *х 2

При условии, что: 3 * х 1 + 10 * х 2 ≤ 330

16 * х 1 + 4 * х 2 ≤ 400

6 * х 1 + 6 * х 2 ≤ 240

2. Создадим экранную форму и введем в нее исходные данные (рис. 1).

Рис. 1. Экранная форма для ввода данных задачи линейного программирования

Обратите внимание на формулу в ячейке С7. Это формула целевой функции. Аналогично, в ячейки С16:С18 введены формулы для расчета левой части ограничений.

3. Проверьте, если у вас установлена надстройка «Поиск решения» (рис. 2), пропустите этот пункт.

Рис. 2. Надстройка Поиск решения установлена; вкладка «Данные», группа «Анализ»

Если надстройки «Поиск решения» вы на ленте Excel не обнаружили, щелкните на кнопку Microsoft Office, а затем Параметры Excel (рис. 3).

Рис. 3. Параметры Excel

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

Рис. 4. Надстройки Excel

В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (рис. 5). (Если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее.)

Рис. 5. Активация надстройки «Поиск решения»

После загрузки надстройки для поиска решения в группе Анализ на вкладке Данные становится доступна команда Поиск решения (рис. 2).

4. Следующим этапом заполняем окно Excel «Поиск решения» (рис. 6)

Рис. 6. Заполнение окна «Поиск решения»

В поле «Установить целевую ячейку» выбираем ячейку со значением целевой функции – $C$7. Выбираем, максимизировать или минимизировать целевую функцию. В поле «Изменяя ячейки» выбираем ячейки со значениями искомых переменных $C$4:$D$4 (пока в них нули или пусто). В области «Ограничения» с помощью кнопки «Добавить» размещаем все ограничения нашей модели. Жмем «Выполнить». В появившемся окне «Результат поиска решения» выбираем все три типа отчета (рис. 7) и жмем Ok. Эти отчеты нужны для анализа полученного решения. Подробнее о данных, представленных в отчетах, можно почитать .

Рис. 7. Выбор типов отчета

На основном листе появились значения максимизированной целевой функции – 130 000 руб. и изменяемых параметров х 1 = 10 и х 2 = 30. Таким образом, для максимизации маржинального дохода Николаю в следующем месяце следует произвести 10 единиц продукта А и 30 единиц продукта В.

Если вместо окна «Результат поиска решения» появилось что-то иное, Excel`ю найти решение не удалось. Проверьте правильность заполнения окна «Поиск решения». И еще одна маленькая хитрость. Попробуйте уменьшить точность поиска решения. Для этого в окне «Поиск решения» щелкните на Параметры (рис. 8.) и увеличьте погрешность вычисления, например, до 0,001. Иногда из-за высокой точности Excel не успевает за 100 итераций найти решение. Подробнее о параметрах поиска решения можно почитать .

Рис. 8. Увеличение погрешности вычислений

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

Если данная надстройка установлена, то Поиск реше­ния запускается из меню Сервис . Если такого пункта нет, следует выполнить команду Сервис → Надстройки... и вы­ставить флажок против надстройки
Поиск решения (рис.2.1).

Команда Сервис → Поиск решения открывает диалоговое окно «Поиск решения» .

В окне Поиск решения имеются следующие поля:

Установить целевую ячейку – служит для указания целевой ячейки, значение которой необходимо максими­зировать, минимизировать или установить равным за­данному числу. Эта ячейка должна содержать формулу .

Равной – служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или Подбор заданного числа). Чтобы установить число, введите его в поле.

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

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

Ограничения – служит для отображения списка граничных условий поставленной задачи.

Добавить - служит для отображения диалогового окна Добавить ограничение.

Изменить - Служит для отображения диалоговое окна Изменить ограничение.

Удалить - Служит для снятия указанного ограничения.

Выполнить – Служит для запуска поиска решения поставленной задачи.

Закрыть – Служит для выхода из окна диалога без запус­ка поиска решения поставленной задачи.

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

Восстановить – Служит для очистки полей окна диалога и восстановления значений параметров поиска ре­шения, используемых по умолчанию.

Для решения задачи оптимизации выполните следующие действия.

1. В меню Сервис выберите команду Поиск решения.

2. В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

3. Чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению.

Чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите, переключатель в положение
минимальному значению.

Чтобы установить значение в целевой ячейке равным некоторому числу путем изменения значений влияющих ячеек, установите переключатель в положение значению и введите в соответствующее поле требуемое число.

4. В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.

5. В поле Ограничения введите все ограничения, накладываемые на поиск решения.

6. Нажмите кнопку Выполнить.

Чтобы восстановить исходные данные, установите переключатель в положение

Этап С. Анализ найденного решения задачи оптимизации.

Для вывода итогового сообщения о результате решения используется диалоговое окно Результаты поиска решения.

Диалоговое окно Результаты поиска решения содержит следующие поля:

Восстановить исходные значения – служит для восста­новления исходных значений влияющих ячеек моде­ли.

Отчеты – служит для указания типа отчета, размещаемого на отдельном листе книги.

Результаты. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.

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

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

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

2.4 Задача о планировании производства

Постановка задачи. Предприятие должно производить изделия n видов: и 1 ,и 2 ,...и п , причем количество каждого выпускаемого изделия не должно превысить спрос β 1 , β 2 ,..., β n и одновременно не должно быть меньше запланированных величин b 1 ,b 2 ,...,b n соответственно. На изготовление изделий идет m видов сырья s l ,s 2 ,...,s m , запасы которых ограничены соответственно величинами γ 1 , γ 2 ,..., γ m . Известно, что на изготовление i -го изделия идет а ij единиц j -го сырья. Прибыль, получаемая от реализации изделий u 1 , ,и 2 ,...и п равна соответственно с 1 ,с 2 ,...,с п. Требуется так спланировать производство изделий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.

Математическая модель. Обозначим за х 1 ,х 2 ,...х n количества единиц изделий u 1 , ,и 2 ,...и п, выпускаемых предприятием. Прибыль, приносимая планом (целевая функция), будет равна:

z = z(x 1 ,x 2 ,...,x n) = с 1 x 1 + c 2 x 2 + ...+c n x n → max. Ограничения на выполнение плана запишется в виде: х i ≥β i для i = 1,2,...,n Чтобы не превысить спрос, надо ограничить выпуск изделий: x i ≤β i для i = 1,2,...n. И, наконец, ограничения на сырье запишутся в виде системы неравенств:

α 11 x 1 + α 12 x 2 +...+ α 1n x n ≤b 1

α 21 x 1 + α 22 x 2 +...+ α 2n x n ≤b 2

................................................

α m1 x 1 + α m2 x 2 +...+ α mn x n ≤b m

при условии, что х 1 ,х 2 ,...х п неотрицательны.

Пример 2.1:

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

Условие задачи. Предприятие выпускает два вида железобетонных изделий: лестничные марши и балконные плиты. Для производства одного лестничного марша требуется израсходовать 3,5 куб.м. бетона и 1 упаковку арматуры, а для производства плиты - 1 куб.м. бетона и 2 упаковки арматуры. На каждую единицу продукции при­ходится 1 человеко-день трудозатрат. Прибыль от прода­жи 1 лестничного марша составляет 200 руб., а одной плиты - 100 руб. На предприятии работает 150 человек, причем известно, что в день предприятие производит не более 350 куб.м. бетона и завозится не более 240 упаковок арматуры. Требуется составить такой производственный план, чтобы прибыль от производимой продукции была максимальной.

Решение.

1. На листе рабочей книги MS Excel заполните таблицу параметров задачи (рис. 2.2).

2. Создайте модель задачи и заполните ячейки для значений переменных (первоначально ячейки х { и х г заполняются произвольными числовыми значениями, например, значением 10), целевой функции (ячейка содержит формулу) и ограничений (ячейки содержат формулы)
(рис. 2.2)

3. Выполните команду Сервис Поиск решения и установите необходимые значения в полях диалогового окна Поиск решения, добавляя ограничения в окне Добавление ограничений.

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

4. Нажмите на кнопку Выполнить и установите параметры в окне Результаты поиска решения (переключатель Сохранить найденное решение или Восстановить исходные значения и Тип отчета).

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

5. В результате в ячейках с переменными задачи по­явятся значения, соответствующие оптимальному плану (80 лестничных маршей и 70 плит перекрытия в день), а в ячейке для целевой функции - значение прибыли (23 000 руб.), соответствующее данному плану (рис. 2.3)

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

Упражнение:

Упр. 2.1. Предприятие выпускает телевизоры, стереосистемы и акустические системы, используя общий склад комплектующих. Запасы шасси на складе составляют 450 шт., кинескопов – 250 шт., динамиков – 800 шт., блоков питания – 450 шт., плат – 600 шт. На каждое изделие расходуется количество комплектующих, указанное в таблице:

Прибыль от производства одного телевизора составляет 90 у.е, одной стереосистемы – 50 и аудиосистемы – 45. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.

Для решения задач линейного программирования симплекс-методом в среде MS Excel заполняются ячейки исходными данными в режиме чисел и формулами математической модели.

MS Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств целевой функции.

Решим задачу о выпускаемых изделиях симплекс-методом применяя надстройку «Поиск решения» в MS Excel.

1. Заполните таблицу Excel в режиме чисел (рис.1)

2. Заполните таблицу Excel в режиме формул (рис.2)

Рис.1 Таблица в режиме чисел

Рис.1 Таблица в режиме формул

Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида);

В6:С6 – коэффициенты целевой функции;

В10 – значение целевой функции;

В3:С5 – коэффициенты ограничений;

D12:D14 – правая часть ограничений;

B12:B14 – вычисляемые (фактические) значения левой части ограничений.

Решим задачу с помощью команды Данные/Поиск решения. На экране появляется диалоговое окно Поиск решения.

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

В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем до следующего ограничения. После ввода всех ограничений нажимаем ОК.

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

Устанавливаем флажок Сделать переменные без ограничений неотрицательными и выбрать Метод решения Поиск решения линеных задач симплекс-методом. Щёлкаем на кнопке Найти решение.

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

Если вычисления оказались успешными, Excel предъявит следующее окно итогов. Их можно сохранить или отказаться. Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность.

После найденного решения, в ячейках В9:С9 появится оптимальное количество изделий каждого вида.

При сохранении отчета выберите – Отчет по результатам (рис.3).

Из отчета видно, что ресурс 1 не используется полностью на 150 кг, а ресурс 2 и 3 используется полностью.

В результате получен оптимальный план, при котором изделий 1 вида необходимо выпустить в количестве 58 шт., а изделий 2 вида в количестве 42 шт. При этом прибыль от их реализации максимальная и составляет 4660 тыс.руб.

Рис.3 Отчет по результатам

1. Со станции формирования ежедневно отправляются пассажирские и скорые поезда, составленные из плацкартных, купейных и мягких вагонов. Число мест в плацкартном вагоне – 54, в купейном – 36, в мягком – 18. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.

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

Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.

	b 1	b 2	…	b k	…	b g
a 1	}