Задачи линейного программирования

1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ  1.1. Постановка  задачи  Линейное программирование (ЛП) – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т. е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения. Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции. Примером решения задачи является разработка оптимального плана деповского ремонта грузовых вагонов. В настоящее время этот вид ремонта выполняется в ремонтных вагонных депо, входящих в департамент ОАО «РЖД» по ремонту грузового вагонного парка. Программа ремонта по количеству и типам вагонов для каждого депо в отдельности устанавливается департаментом исходя из потребностей в ремонте, производственных  мощностей депо и имеющихся в наличии производственных ресурсов. С учетом того, что в настоящее время неуклонно возрастает вагонный парк других собственников, а также предстоящим акционированием департамента возникает проблема определения оптимальной производственной программы депо, обеспечивающей максимальную прибыль предприятию. Такая задача может быть сформулирована следующим образом. Имеем: хj – объем ремонта вагонов j-го типа; j = 1, 2, … n; bi – объем, имеющихся в наличии производственных ресурсов i-го вида; i = 1, 2, … m; aij – расход i-го вида ресурсов на ремонт одного вагона j-го типа; Cj – прибыль, получаемая предприятием за один отремонтированный вагон j-го типа. Решение задачи осуществляется на основе следующей экономико-ма­тематической модели. Найти совокупность переменных хj, максимизирующих целевую функцию F:  ,                 (1.1) при наложенных ограничениях (система m линейных уравнений и неравенств с n переменными):   ,                  (1.2) xj, j = 1….n,                                              (1.3) где aij, bi, сj – заданные постоянные величины Линейную функцию (1.1), для которой ищется экстремальное значение, принято называть целевой функцией. Условия (1.2) называются функциональными, а (1.3) – прямыми ограничениями задачи. Виды задач ЛП: 1) задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте); 2) задача на максимум выпуска продукции при заданном ассортименте; 3) задача о смесях (рационе, диете); 4) транспортная задача; 5) задача о рациональном использовании имеющихся мощностей; 6) задача о назначениях. Для решения ЗЛП необходимо построить экономико-математическую модель исследуемого экономического процесса.  1.2. Решение задач линейного программирования с помощью надстройки MS Excel «Поиск решения» Рассматриваемая модель относится к классу экономико-мате­ма­ти­че­ских моделей линейного программирования. Решение задач, описываемых экономико-математическими моделями линейного программирования, как правило, осуществляется универсальным симплексным методом. Он достаточно трудоемок. Поэтому выполнение расчетов рекомендуется в среде MS Excel. Технологию решения задач линейного программирования в среде MS Excel продемонстрируем на следующем примере. Вагоноремонтное депо имеет в своем распоряжении определенное количество ресурсов: рабочую силу, материалы, запасные части, оборудование, производственные площади и т. п. Допустим, например, имеются ресурсы четырех видов: рабочая сила, материалы, специальные запасные части и фонд времени вагоноремонтных позиций. Депо может ремонтировать вагоны четырех типов. Информация о количестве единиц каждого ресурса, необходимого для ремонта одного вагона каждого типа, их объеме и получаемой прибыли приведена в табл. 1.1.  Таблица 1.1– Исходные данные Ресурсы Нормы расхода ресурсов на один вагон Наличие ресурсов полувагон крытый платформа хопер-дозатор Раб. сила, чел.-ч 180 205 160 336 650 000 Материалы, тыс. руб. 28 27 26 54 100 000 Фонд времени,ч 17 18 16 30 125 000 Специальные  запчасти, тыс. руб. 15 5000 Прибыль на 1 вагон, тыс. руб. 7,3 7,5 6,5 15     Требуется найти такой план ремонта вагонов, при котором будет максимальной общая прибыль предприятия. Обозначим через х1, х2, х3, х4 количество вагонов каждого типа. Сформулируем экономико-математическую модель задачи:  F = 7,3х1 + 7,5х2 + 6,5х3 + 15х4 → max; 180х1 + 205х2 + 160х3 + 336х4 ≤ 650 000; 28х1 + 27x2 + 26х3 + 54х4 ≤ 100 000; 17х1 + 18х2 + 16х3 + 30х 4 ≤ 125 000;                      (1.4) 15 ∙ х4 ≤ 5000; x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0.   Решение задач линейного программирования в среде MS Excel осуществляется с помощью надстройки «Поиск решения». Если в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервиса Надстройки и активизируйте надстройку «Поиск решения». Если же этой надстройки нет в диалоговом окне «Надстройки», то необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки MS Excel (или Office) установить надстройку «Поиск решения». Для решения задачи необходимо: 1) создать форму для ввода условий задачи; 2) указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки); 3) ввести исходные данные; 4) ввести зависимость для целевой функции; 5) ввести зависимости для ограничений; 6) указать назначение целевой функции (установить целевую ячейку); 7) ввести ограничения; 8) ввести параметры для решения задачи линейного программирования. Для рассматриваемого примера продемонстрируем технологию решения задачи оптимального использования ресурсов. 1.  Подготовим форму для ввода условий задачи (рис. 1.1). Рис. 1.1. Форма для ввода условий задачи 2. В задаче оптимальные значения вектора X = (х1, х2 х3, х4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции – в ячейке F4. 3. Введем исходные данные в созданную форму. Получим результат, показанный на рис. 1.2.       Переменные           Х1 Х2 Х3 Х4       Значение         ЦФ     коэф. в ЦФ 7,3 7,5 6,5 15         Ограничения         Вид ресурсов         Левая часть Знак Правая часть Труд 180 205 160 336   <= 650 000 Материалы 28 27 26 54   <= 100 000 Фонд времени 17 18 16 30   <= 125 000 Спец. запчасти 15   <= 5000   Рис. 1.2. Введённые данные 4. Введем зависимость для целевой функции. •         Курсор в F4. •         Курсор на кнопку Мастер функций. M1 (Обозначим через М1 следующее действие – «один щелчок левой кнопкой мыши»). На экране диалоговое окно Мастер функций шаг 1 из 2. •         Курсор в окно Категория на категорию Математические. •         M1. •         Курсор в окно Функции на СУММПРОИЗВ. •      M1. •         В массив 1 ввести В$3:Е$3. •         В массив 2 ввести В4:Е4. •         Готово. На экране: в F4 введена функция, как показано на рис. 1.3.    Рис. 1.3. Вычисление целевой функции    5. Введем зависимость для левых частей ограничений. •         Курсор в F4. •         Копировать в буфер. •         Курсор в F7. •         Вставить из буфера. •         Курсор в F8. •         Вставить из буфера. •         Курсор в F9. •         Вставить из буфера. На этом ввод зависимостей закончен. Запуск «Поиска решения». После выбора команд Сервис => Поиск решения появится диалоговое окно «Поиск решения» (рис. 1.4).    Рис. 1.4. Ввод данных в диалоговое окно «Поиск решения»    В диалоговом окне «Поиск решения» есть три основных параметра: •      Установить целевую ячейку. •      Изменяя ячейки. •      Ограничения. Сначала нужно заполнить поле «Установить целевую ячейку». Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение. Второй важный параметр средства Поиск решения – это параметр. Изменяемые ячейки – это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования: они не должны содержать формул и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек. Третий параметр, который нужно вводить для Поиска решения – это Ограничения. 6. Назначение целевой функции (установить целевую ячейку). •      Курсор в поле «Установить целевую ячейку». •      Ввести адрес $F$4. •      Ввести направление целевой функции: Максимальному значению. •      Ввести адреса искомых переменных: •      Курсор в поле «Изменяя ячейки». •      Ввести адреса В$3:Е$3. 7.  Ввод ограничений. •     Курсор в поле «Добавить». Появится диалоговое окно «Добавление ограничения» (рис. 1.5). Рис. 1.5. Диалоговое окно «Добавление ограничения» •     В поле «Ссылка на ячейку» ввести адрес $F$7. •     Ввести знак ограничения ≤. •     Курсор в правое окно. •     Ввести адрес $Н$7. •     Добавить. На экране опять диалоговое окно «Добавление ограничения». •     Ввести остальные ограничения. •     После ввода последнего ограничения ввести ОК. На экране появится диалоговое окно «Поиск решения» с введенными условиями (рис. 1.5). 8. Ввод параметров для решения ЗЛП (рис. 1.6). •     Открыть окно «Параметры поиска решения». •     Установить флажок Линейная модель, что обеспечивает применение симплекс-метода. •     Установить флажок Неотрицательные значения. •     ОК.   Рис. 1.6. Параметры «Поиск решения»   Полученное решение (рис. 1.7, 1.8) означает, что максимальную прибыль 26 537,7 тыс. руб. депо может получить при выпуске из ремонта 2595,5 полувагонов, 345,4 крытых вагонов, 333,3 вагонов-хопперов. При этом ремонт платформ в оптимальном плане производства отсутствует. Ресурсы – рабочее время, материалы, специальные запасные части – будут использованы полностью, а из 125 тыс. ч фонда времени вагоноремонтных позиций будет использовано только 60,3 тыс. ч. Рис. 1.7. Результаты «Поиска решения»     Microsoft Excel 10.0 Отчет по результатам       Рабочий лист: [Методичк.ОПТ.ВАГ.xls]Лист1       Отчет создан: 26.02.2011 14:23:00                                     Целевая ячейка (Максимум)           Ячейка Имя Исходное значение Результат       $F$4 коэф.в ЦФ ЦФ 26537,72727                                 Изменяемые ячейки           Ячейка Имя Исходное значение Результат       $B$3 Значение Х1 2595,454545       $C$3 Значение Х2 345,4545455       $D$3 Значение Х3       $E$3 Значение Х4 333,3333333                                 Ограничения           Ячейка Имя Значение Формула Статус Разница   $F$8 Материалы Левая часть 100000 $F$8<=$H$8 связанное   $F$7 Труд Левая часть 650000 $F$7<=$H$7 связанное   $F$9 Фонд времени Левая часть 60340,909 $F$9<=$H$9 не связанное 64659,09   $F$10 Спец. Запчасти Левая часть 5000 $F$10<=$H$10 связанное  Рис. 1.8. Отчет по результатам MS Excel позволяет представить результаты поиска решения в форме отчета (см. рис. 1.8). Существует три типа таких отчетов. Результаты (Answer). В отчет включаются исходные и конечные значе­ния целевой и влияющих ячеек, дополнительные сведения об ограничениях. Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений. Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений. В отчете по результатам содержатся оптимальные значения переменных x1, х2, х3, х4, значение целевой функции, а также левые части ограничений. В выводе указать (см. рис. 1.7.): 1) максимальную величину прибыли; 2) количество вагонов какого типа следует отремонтировать, чтобы прибыль была максимальной; 3) оценить качество использования ресурсов предприятия.  1.3. Исходные данные  Задача формулируется для вагоноремонтных депо, которые в состоянии ремонтировать пять типов вагонов: полувагоны, крытые, платформы, вагоны-хопперы и цистерны. Предположим, что в производственном процессе используется пять видов ресурсов: рабочая сила, материалы, фонд времени ремонтных позиций, специальные запасные части и электроэнергия. Нормы расхода ресурсов на ремонт одного вагона по типам единые для всех вариантов задания представлены в табл. 1.2. Таблица 1.2 - Исходные данные Ресурсы Нормы расхода ресурсов на один вагон Полувагон Крытый Платформа Хопер-дозатор Цистерна Раб. сила, чел.-ч 180 205 160 336 170 Материалы, тыс. руб. 28 27 26 54 27 Фонд времени, ч 17 18 16 30 17 Специальные запчасти, тыс. руб. 15 10 Электроэнергия, тыс. кВт∙ч 1,5 1,4 0,9 1,6 1,2  Данные о размерах прибыли на 1 отремонтированный вагон и объемах ресурсов на предприятии приведены по вариантам в табл. 1.3 и 1.4. Таблица 1.3 - Размер прибыли на один отремонтированный вагон Номер варианта Прибыль на 1 вагон, тыс. руб. Полувагон Крытый Платформа Хопер-дозатор Цистерна 1 7,3 7,5 6,5 15,0 7,1 2 7,5 7,7 6,0 14,2 7,3 3 7,7 7,9 6,4 15,4 7,6 4 8,0 8,4 6,3 15,7 7,9 5 7,1 8.1 7,0 15,5 6,8 Таблица 1.4 - Объемы ресурсов на предприятии Номер  варианта Объемы ресурсов Рабочая сила Материалы Фонд времени Специальные запчасти Электроэнергия 1 650 000 100 000 125 000 5000 6300 2 590 000 98 000 80 000 6000 7000 3 680 000 120 000 90 000 7000 6500 4 700 000 125 000 75 000 8000 6900 5 750 000 130 000 88 000 9000 7000 6 690 000 133 000 74 000 7800 7400 7 800 000 129 000 95 000 10 000 9200 8 790 000 130 000 80 000 9600 8400 9 770 000 115 000 92 000 8100 7500 10 710 000 120 000 79 000 7900 7800   1.4. Последовательность решения задачи  1. По данным табл. 1.3 и 1.4 определяются номера вариантов исходных данных. Для этого две последние цифры номера зачетной книжки студента делятся с остатком на количество вариантов, представленных в таблицах. К остатку от деления прибавляется единица. Полученное число является номером варианта для информации соответствующего вида. Например, считываем из зачетной книжки число 89. Норму прибыли на вагон определяем по данным табл. 1.3. Для этого число 89 делим на 5. Получаем 17 и 4 в остатке. Прибавляем к остатку единицу, получаем вариант 5. Если остаток 0, вариант 1. По такой же схеме находим объемы ресурсов. 2. Для соответствующих исходных данных составляется экономико-математическая модель. 3. С использованием надстройки «Поиск решения» пакета EXCEL решается задача с выдачей отчета «Результаты». 4. Полученное решение анализируется, и делаются выводы, в которых дается характеристика найденному оптимальному варианту производственной программы вагоноремонтного предприятия и эффективности использования производственных ресурсов.