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

ТЕМА. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

 

1. Задача об оптимальном использовании ресурсов.

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

Пример. Для изготовления двух видов продукции используются четыре вида ресурсов: В₁, В₂, В₃, В₄. Максимально возможные запасы ресурсов различных видов, а также затраты на изготовление единицы каждого из двух видов продукции приведены в таблице 1.

Таблица 1

Вид ресурса	Запас ресурса	Число    единиц    ресурсов,    затрачиваемых    на изготовление единицы продукции
		Первый вид продукции продукции	Второй вид продукции
В1	36	1	3
В2	32	2	1
В3	10	-	1
В4	42	3	-

На производство единицы продукции I-го и II-го видов используется 
различное количество ресурсов. Так, например, на производство единицы 
продукции I-го вида используется только одна единица ресурса В₁, а на 
производство единицы продукции II-го вида используется 3 единицы ресурса В₁. В то же время на производство продукции I-го вида ресурс В₃ вообще не 
используется (Табл.  1). 

Выручка, получаемая предприятием от продажи единицы продукции первого  и второго видов, составляет соответственно 4 руб. и 6 руб.

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

Составим экономико-математическую модель задачи.

Пусть – число единиц продукции первого вида, которое запланировано к производству; – число единиц продукции второго вида, которое запланировано к производству.

На их изготовление предприятию требуется:

– единиц ресурса В₁;

– единиц ресурса В₂;

 – единиц ресурса В₃;

– единиц ресурса В₄.

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

 (2.1)                                         

По смыслу задачи:

                                  ,                                                (2.2)

так как количество выпускаемой продукции, как первого, так и второго вида не может быть отрицательным.

Выручка от реализации продукции первого  вида составит , а от реализации второго вида продукции – , таким образом, суммарная выручка от реализации обоих видов продукции составит:

                                        .                                     (2.3)

Математическая постановка задачи: Требуется найти матрицу , которая удовлетворяла бы ограничениям (2.1) и (2.2) и при которой целевая функция F (2.3) принимала бы максимальное значение.

Обобщим эту задачу на п видов продукции и т видов ресурсов. Обозначим через:

– число единиц j-го вида продукции , запланированной к производству;

– запас i-го ресурса ;

– число единиц i-го ресурса, затрачиваемого на изготовление единицы продукции j-го вида ( часто называют технологическими коэффициентами);

– прибыль от реализации единицы продукции j-го вида (или цена продукции j-го вида) .

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

 (2.4)

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

 (2.5)

 

РЕШЕНИЕ ЗАДАЧИ СРЕДСТВАМИ MS EXCEL

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

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

Вид ресурса	Запас ресурса	Число    единиц    ресурсов,    затрачиваемых    на изготовление единицы продукции
		Первый вид продукции продукции	Второй вид продукции
В1	36	1	3
В2	32	2	1
В3	10	-	1
В4	42	3	-

Определить  оптимальный план производства продукции, при котором затраты на производство продукции были бы в пределах возможного максимального ресурсного обеспечения, а выручка фирмы – наибольшей, если цена единицы продукции I вида – 4 ден. ед., а II вида – 6 ден. ед.

Решение:  1. Математическая модель:

- план производства продукции j-того вида.

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

Граничные условия:         ,       

Целевая функция:            .                                        

2. Ввод исходных данных:

Создание экранной формы и ввод условия задачи:

Экранная  форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рис. 2.1.

Рис. 2.1. Экранная форма задачи.

В экранной форме на рис. 2.1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel:

• Матрица переменных соответствует ячейкам (А1:В1).
• Технологическая матрица соответствует массиву (А2:В5).
• Правым частям ограничений соответствуют ячейки (D2:D5).
• Значениям целевой функции – ячейки (А6:В6).

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

Для ввода  зависимостей используем формулу СУММПРОИЗВ(массив1; массив 2) (рис. 2.2):

Рис. 2.2. Аргументы функции СУММПРОИЗВ.

Данная  формула вводится в ячейки (С2:С6). Символ $ перед номером строки 1 означает абсолютную ссылку на переменные матрицы Х, следовательно, при копировании этой формулы в другие места листа Excel номер строки 1 не изменится.

На рис. 2.3 представлен общий вид листа  Excel после ввода зависимостей математической модели.

Рис. 2.3. Экранная форма задачи после ввода всех необходимых формул.

Целевая функция  в ячейке С6.

Диалоговое окно «Поиск решения»

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

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

• введите  адрес целевой ячейки $С$6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме;

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

Рис. 2.4. Окно «Поиск решения».

Задание ячеек переменных

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

Ввод ограничений и граничных условий

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

Рис. 2.5. Диалоговое окно Добавление ограничений.

• В поле «Ссылка на ячейку» введите адреса ячеек левой части ограничений $С$2. Так как условие соотношения между правыми и левыми частями в нашей задаче одинаково, то в качестве ссылки на ячейку можно задать массив ($С$2:$С$5).
• В поле знака откройте список предлагаемых знаков и выберите .
• В поле «Ограничение» введите адреса ячеек правой части ограничений, то есть $D$2:$D$5. Их также можно ввести путем выделения мышью непосредственно в экранной форме.

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

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

Ввести  это ограничение можно с помощью диалогового окна Добавление ограничения или используя диалоговое окно Параметры поиска решения (пиктограмма Параметры на рис. 2.4) (рис. 2.6).

Рис. 2.6. Диалоговое окно Параметры поиска решения.

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

Окно «Поиск решения» после ввода всех необходимых данных задачи  представлено на рис. 2.4.

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

3. Решение задачи

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

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

Параметр «Максимальное время» служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).

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

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

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

Параметр «Сходимость» применяется только при решении нелинейных задач.

Установка флажка «Линейная модель» обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.

Подтвердите установленные параметры нажатием кнопки «OK».

Запуск задачи на решение

Запуск  задачи на решение производится из окна «Поиск решения» путем нажатия кнопки «Выполнить». После запуска на решение задачи ЛП на экране появляется окно «Результаты поиска решения» с одним из сообщений, представленных на рис. 2.7, 2.8 и 2.9:

 

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

 

Рис. 2.8. Сообщение при несовместной системе ограничений задачи.

Рис. 2.9. Сообщение при неограниченности целевой функции в требуемом направлении.

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

Если  при заполнении полей окна «Поиск решения» были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра «Относительная погрешность» не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне «Результаты поиска решения» представлены названия трех типов отчетов: «Результаты», «Устойчивость», «Пределы». Они необходимы при анализе полученного решения на чувствительность (см. ниже подразд. 2.2.1-2.2.2). Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку «OK».