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

РЕШЕНИЕ задач линейного программирования С ПОМОЩЬЮ MS EXCEL

1. ЦЕЛЬ РАБОТЫ: приобрести навыки решения оптимизационных задач линейного программирования с использованием MS Excel. Познакомить учащихся с применением компьютеров в качестве помощников при решении уравнений.

СОДЕРЖАНИЕ РАБОТЫ

2.1 Ознакомиться с теоретическими предпосылками изложенными в данной лабораторной работе, углубить знания с использованием дополнительной литературы

2.2 Изучить и разобрать пример расчета.

2.3 Для исходных данных индивидуального задания выполнить расчеты.

2.4. Выполнить анализ результатов и сделать выводы

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

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

Рис. 1.

Если в версии Excel, установленной на Вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения» (рис. 2).

Рассмотрим на примере использование данной надстройки. Решим с её помощью задачу, математическая модель которой строилась в примере Математическая модель задачи имеет вид:

Составим шаблон в редакторе Excel, как показано на рис. 3.

Рис. 3. Шаблон оформления задачи.

Теперь занесём данную в задаче числовую информацию (рис. 4).

Рис. 4. Исходные данные задачи

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

Ячейки B4 – С4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., изменяя их Поиск решения будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).

Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение можно рассматривать как произведение вектора (3,2) на вектор .

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку Е4 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это В5:С5) и ячеек, в которые в результате решения будут помещены значения (ячейки В4:С4) (рис. 5). Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение (для первого ограничения ) будем рассматривать как произведение вектора коэффициентов (1,2) и вектора пока переменных .

Рис. 5. Вызов функции СУММПРОИЗВ.

В ячейке, отведенной для формулы левой части первого ограничения (D9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов В9:С9 и адрес значений переменных В4:С4 (рис. 6).

Рис. 6

В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введёнными формулами показан на рис.7.

Рис. 7

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

В меню Сервис выбираем Поиск решения. В появившемся окне задаём следующую информацию:

1. в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции Е4;

2. «флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае, целевая функция дохода подлежит максимизации;

3. в качестве изменяемых ячеек заносится адрес строки значений переменных В4:С4;

справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (рис. 8)

Рис.8. Форма для занесения одного ограничения ЗЛП.

в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения D9, выбирается требуемый знак неравенства (в нашем случае, <=), в поле «Ограничение» заносится ссылка на правую часть ограничения F9 (рис. 9.9).

Рис.9. Занесение первого ограничения задачи.

Аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Таким образом, окно «Поиск решения» с занесенной информацией выглядит следующим образом (рис. 10):

Рис. 10.

Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (рис.11).

Рис. 11. Установка параметров

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения (рис.12).

Рис. 12. Окно результата решения

Если в результате всех действий получено окно с сообщением «Решение найдено», то Вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи из примера 1.1. (рис.13).

Рис.13. Результат применения «Поиска решения»

Если в результате решения задачи выдано окно с сообщением о невозможности нахождения решения (рис.9.14), это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок» максимизации/минимизации и т.д.).

Рис.14. Сообщение об ошибке

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

Например, можно установить условие на целочисленность некоторых переменных.

Анализ отчётов по результатам, пределам и устойчивости

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

Для получения отчётов в диалоговом окне «Результаты поиска решения» (см. рис. 8.12) в окне «Тип отчёта» следует выбрать соответствующий отчёт «Результаты», «Устойчивость», «Пределы». После нажатия на кнопку «OK» отчёты будут представлены на отдельных листах с соответствующими названиями.

При анализе отчёта по результатам следует обратить внимание на колонку «Статус». Если статус имеет значение «связанное», то это говорит о том, что ресурс, который соответствует ограничению, был использован полностью. Т.е. этот ресурс является дефицитным.

При анализе отчёта по устойчивости следует обратить внимание на следующее.

Нормированная стоимость (часто, редуцированная стоимость, от английского: cost reduction – уменьшение затрат) показывает, насколько по модулю уменьшится целевая функция при принудительном выпуске единицы данной продукции. Т.е., если нормированная стоимость положительна, то увеличение соответствующей переменной приведёт к уменьшению целевой функции. Другими словами, выпуск продукта, соответствующего рассматриваемой переменной, является нерентабельным (неприбыльным).

Допустимое увеличение показывает, насколько максимально можно увеличить коэффициент целевой функции (цену продукта), чтобы структура оптимального плана осталась прежней. Допустимое уменьшение, наоборот, показывает, насколько можно максимально уменьшить коэффициент ЦФ, чтобы осталась прежней структура оптимального плана.

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

В отчёте по устойчивости указаны значения целевой функции при значении переменных на нижнем и верхнем пределах.

3. МЕТОДИЧЕСКОЕ И МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

3.1. Методические указания по выполнению лабораторной работы – по числу студентов, присутствующих на занятиях.

3.2. Раздаточный материал (индивидуальные исходные данные, персональный компьютер для выполнения вычислений с использованием EXCEL) — по числу студентов.