Тема 5. Решение задач линейного программирования (ЛП)

 

В задаче ЛП все ограничения и целевая функция линейны. Ее можно представить в таком виде:

x_j ≥ 0, j =  .

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

    Пример 1.Для изготовления трех видов изделий фирма расходует три вида ограниченных ресурсов (сырье, оборудование и труд) в количествах, приведенных в таблице 1. Так же указаны нормы расхода ресурсов и удельная прибыль (прибыль от реализации одного изделия каждого вида продукции). Предполагается, что расход ресурсов и величина прибыли являются линейными функциями от объемов выпускаемой продукции. Цель производства – получение макисмальной прибыли от продажи выпущенных изделий. Требуется найти оптимальный план выпуска и оценки ресурсов.

Таблица 1 – Исходная информация к задаче

Вид ресурса	Нормы расхода ресурсов			Наличие ресурса
	Изделие 1	Изделие 2	Изделие 3
Сырье (в кг)	5	6	4	400
Оборудование (в станко-ч)	4	7	6	350
Труд (в чел.-ч)	6	8	5	480
Удельная прибыль (в руб.)	25	40	30

 

Создание математической модели

 

    В задаче необходимо определить план выпуска продукции. Поэтому математическая модель должна содержать три переменные: х₁, х₂ и х₃, где х_j – объем выпуска изделия j (j= ). Весь план выпуска изделий можно записать в виде вектора х = (х₁,х₂,х₃). Этот план можно выполнить лишь тогда, когда он будет обеспечен необходимым количеством ресурсов. Поэтому модель должна включать для каждого ресурса, используемого в производстве, ограничение вида

расход ресурса ≤ наличие ресурса.

    Чтобы определить его аналитический вид, необходимо вычислить затраты сырья на выпуск плана х. Так как зависимость затрат от объема выпуска линейна, для выпуска x₁единиц изделия 1 нужно затратить сырья 5x₁ (кг). Учет затрат сырья на изделия 2 и 3 показывает, что общий расход сырья равен 5x₁+6x₂+4x₃. Так как его наличный запас равен 400 (кг), то ограничение по сырью имеет вид

5x₁+6x₂+4x₃ ≤ 400(сырье).

    Ограничения по остальным ресурсам выглядят так:

4x₁+7x₂+6x₃ ≤ 350(оборудование),

6x₁+8x₂+5x₃ ≤ 480(труд).

    Кроме ресурсных ограничений должны выполняться условия неотрицательности переменных. Предполагается, что объемы выпуска могут принимать как целые, так и дробные значения. Тогда любой неотрицательный вектор х = (х₁,х₂,х₃), удовлетворяющий ресурсным ограничениям, определяет допустимый план выпуска.

    Пусть х = (х₁,х₂,х₃) – некоторый вектор выпуска. Прибыль F от продажи этой продукции вычисляется по формуле:

F(x) = 25x₁ + 40x₂ + 30x₃.

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

    Таким образом, математическая модель задачи фирмы имеет следующий вид:

F(x) = 25x₁ + 40x₂ + 30x₃ max,  (1)

5x₁+6x₂+4x₃ ≤ 400,                      (2)

4x₁+7x₂+6x₃ ≤ 350,                      (3)

6x₁+8x₂+5x₃ ≤ 480,                      (4)

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0.                    (5)

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

Решение задачи в Excel

    Процесс решения оптимизационной задачи в Excel включает несколько этапов:

· подготовка исходных данных,

· формирование модели,

· настройка параметров расчетов,

· нахождение оптимального решения,

· сохранение полученных результатов.

Подготовка исходных данных

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

Рисунок 2. Исходные данные для расчетов

    Ячейки B10:D10 – изменяемые ячейки. Диапазон E5:E7 отведен под левые части ресурсных ограничений. Он будет содержать формулы, подсчитывающие расход ресурсов. Ячейка В11 – целевая. В ней будет находиться формула, задающая правило вычисления целевой функции.

Ввод формул целевой функции и ограничений

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

= СУММПРОИЗВ (В8:D8; B10:D10).

    В самой ячейке на рабочем листе появится число 0 – значение целевой функции при нулевых значениях переменных (пустые значения в ячейках Excel при вычислениях значений формул интерпретирует как нулевые).

    Затем следует ввести формулы, описывающие расход ресурсов при выполнении планового задания. Требуемые для этого объемы ресурсов задаются функциями, расположенными в левой части ресурсных ограничений (2)-(4).

    Для соответствующих формул отведен диапазон ячеек Е5:Е7. Сначала следует ввести в ячейку Е5 формулу, задающую расход сырья. Для этого снова применяется функция СУММПРОИЗВ. В качестве первого массива в окне матера функций выбирается диапазон В5:D5 (нормы затрат сырья), а в качестве второго массива – диапазон B10:D10, и формула в ячейке Е5 примет следующий вид:

= СУММПРОИЗВ(B8:D8;B10:D10).

    Теперь нужно скопировать эту формулу в ячейки Е6 и Е7.

Формирование модели для расчетов

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

Рисунок 3. Создание модели в окне Поиск решения

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

В поле, отведенном под целевую ячейку, должна находиться ссылка на нее в виде адреса или имени (на рисунке $B$11). Также необходимо указать тип экстремума (в рассматриваемом случае ищется максимальное значение целевой функции). В поле Изменяя ячейкидолжна содержаться ссылка на диапазон изменяемых ячеек (в данном случае изменяются ячейки Выпуск, заданные диапазоном В10:D10).

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

Рисунок 4. Окно Добавление ограничения

    Правая часть ограничения задается в правом поле Ограничение в виде числа или ссылки на ячейку рабочего листа. Задав ограничение, можно либо щелкнуть по кнопке Ок и вернуться в окно Поиск решения, либо щелкнуть по кнопке Добавить и задать новое ограничение.

Настройка параметров расчета

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

Рисунок 5. Окно Параметры поиска решения

        Если ранее в разделе Ограниченияне было введено условие неотрицательности переменных, то его можно задать здесь, установив флажок в поле Неотрицательные значения. Значения остальных параметров менять не нужно.

Нахождение оптимального решения

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

· получено оптимально решение или решение, близкое к оптимальному;

· ППР не может найти оптимальное решение из-за противоречивости условий (отсутствия решений, удовлетворяющих всем ограничениям);

· ППР не может найти оптимальное решение из-за неограниченности значений целевой функции.

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

Рисунок 6. Результаты решения задачи

Сохранение полученных результатов

После завершения работы ППР на экран выводится диалоговое окно Результаты поиска решения (рисунок 7). В нем содержится сообщение о том, что оптимальное решение найдено, и предлагается сохранить его на рабочем листе. Если принять это предложение (нажать Ок), то в изменяемых ячейках будут сохранены оптимальные значения переменных задачи. Также будут сохранены и значения в ячейках, которые содержат формулы, зависящие от изменяемых ячеек. Если же будет выбран пункт Восстановить исходные значения или нажата кнопка Отмена, то будут восстановлены исходные значения изменяемых, а также зависящих от них ячеек.

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

 

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

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

В третьей таблице приводится информация об ограничениях в оптимальном плане. В столбце Значение содержатся сведения о затратах ресурсов (значения левой части ограничений). В столбце Разница даны значения остатков каждого ресурса, которые равны разности между его наличием (значением правой части ограничения) и затратами. Столбец Статус содержит информацию о состоянии ограничения. Если ресурс используется в оптимальном плане полностью, то соответствующее ограничение является связанным; если же ресурс недоиспользуется, то ограничение – несвязанное.

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

---

Дата добавления: 2018-02-28; просмотров: 412; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!