Лабораторная работа №8¹

МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ:

информационная технология «Поиск решения»

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

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

Имеются переменные и некоторая функция Z, зависящая от этих переменных: Z=f(), которая называется целевой функцией. Ставится задача найти максимум или минимум целевой функции Z при условии, что переменные x принадлежат некоторой области, имеющей ограничения. Таким образом, модель линейного программирования состоит из двух частей:

1. системы ограничений;

2. целевой функции.

В общем виде выглядит следующим образом:

_.

Задача состоит в отыскании неизвестных минимизирующих или максимизирующих значение целевой функции. Различают два вида решений: допустимое и оптимальное.

Допустимое решение – это значения переменных удовлетворяющих ограничениям задачи.

Оптимальное решение – это значения переменных , при которых целевая функция принимает свое экстремальное значение (min/max).

Основные этапы решения задач линейного программирования:

1. Постановка задачи и обоснование критерия оптимальности.

2. Выбор базовой модели.

В линейном программировании имеется две основные базовые модели:

• модель симплексного метода;

• модель распределительного метода (или транспортной задачи).

3. Построение развернутой матрицы.

Реализация симплексного метода в MS Excel

Пример.

Производственное предприятие выпускает 2 вида продукции: А и В. Трудозатраты на производство 1 т продукции А составляют 20 часов, а продукции В – 10 часов. На предприятии работают 10 рабочих по 40 часов в неделю. Оборудование позволяет производить в неделю не более 15 т продукции А и 30 т продукции В. Прибыль от реализации 1 т продукции А составляет 50 ден.ед, а 1 т продукции В – 40 ден.ед. Сколько продукции каждого вида следует выпускать для получения максимальной прибыли?

Решение

Введем обозначения:

x₁ – объем производства продукции А;

x₂ – объем производства продукции В.

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

1 – по объему рабочего времени;

2 – по мощности оборудования на производство продукции А;

3 – по мощности оборудования на производство продукции В;

4 – условие неотрицательности переменных.

Составим систему ограничений:

Решим задачу с помощью инструмента «ПОИСК РЕШЕНИЯ» электронных таблиц MS Excel. Составим экономико-математическую модель задачи:

Рисунок 4.1 – Шаблон динамической модели

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

Для решения задачи линейного программирования следует открыть вкладку ДАННЫЕ и нажать пиктограмму . При этом на экране появится окно надстройки «ПОИСК РЕШЕНИЯ», в котором необходимо установить ссылку на ячейку целевой функции, указать и указать, к чему стремится целевая функция (max/min).

Рисунок 4.2 – Ввод ограничений (шаг 1)

Для добавления ограничений необходимо щелкнуть кнопку ДОБАВИТЬ.

После этого на экране появится следующее диалоговое окно (см.рис.4.3), в котором следует указать ссылки на соответствующие диапазоны ячеек.

Рисунок 4.3 – Ввод ограничений (шаг 2)

По окончании нажать кнопку ОК. При этом окно примет вид:

Рисунок 4.4 – Определение параметров

Для задания условия неотрицательности переменных необходимо щелкнуть кнопку «ПАРАМЕТРЫ». При этом в появившемся окне необходимо установить флажок в поле «неотрицательные переменные»:

Рисунок 4.5 – Настройка параметров

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

Рисунок 4.6 – Итерация 1

Рисунок 4.7 – Итерация 2

Рисунок 4.8 – Итерация 3

Ответ: х₁=5, х₂=30, Прибыль = 1450 ден.ед.

1 Методы и инструменты принятия решений [Текст] : учеб. пособие / Л.А. Сафонова, Г.Н. Смоловик; Сиб.гос. ун-т телекоммуникаций и информатики. - Новосибирск, 2012. - 299с.