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

Лекция 1. Задачи линейного программирования Поиск решения - это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Ecли, в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту над­стройку. Выберите команду Сервис Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с по­мощью программы установки Excel (или Office) установить надстройку Поиск решения. После выбора команд Сервис  Поиск решения появится диалоговое окно Поиск решения. В диалоговом окне Поиск решения есть три основных параметра: • Установить целевую ячейку • Изменяя ячейки • Ограничения Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же уста­новить конкретное значение. Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячей­ки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в це­левой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении резуль­тата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек. Третий параметр, который нужно вводить, для Поиска решения – это ограничения. Для решения задачи необходимо: 1) Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). 2) Ввести исходные данные. 3) Ввести зависимость для целевой функции 4) Ввести зависимости для ограничений. Запустить Поиск решений. 5) Назначение целевой функции (установить целевую ячейку). 6) Ввод ограничений. 7) Ввод параметров для решения ЗЛП. Задача № 1 (Задача о костюмах). Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов. Сформулируем экономико-математическую модель задачи. Введем следующие обозначения: х1 - число женских костюмов; x2 - число мужских костюмов. Прибыль от реализации женских костюмов составляет 10х1, а от реализации мужских 20х2, т.е. необходимо максимизировать целевую функцию f(x) = 10 х1 + 20 х2 -> max. Ограничения задачи имеют вид: х1 + х2  150 - ограничение по труду 2 х1 + 0.5 х2  240 - ограничение по лавсану х1 + 3.5 х2  350 - ограничение по шерсти х2  60 - ограничение по костюмам х1  0 Решение. 1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначьте через Х1, Х2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2) будут помещены в ячейках A2:B2, оптимальное значение целевой функции в ячейке C3. 2. Ввести исходные данные. Введите исходные данные задачи, как показано на рис. 5. Рис. 5. 3. Ввести зависимость для целевой функции •Курсор в ячейку «С3». •Курсор на кнопку «Мастер функций», расположенную на панели инструментов. • На экране появляется диалоговое окно «Мастер функций шаг 1 из 2» • Курсор в окно «Категория» на категорию «Математические». • Курсор в окно «Функции» на «СУММПРОИЗВ» (рис. 6). Рис. 6. На экране появляется диалоговое окно «СУММПРОИЗВ» (рис. 7) Рис. 7. • В строку «Массив 1»1 ввести А2:В2 • В строку «Массив 2» ввести А3:В3. Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку2. На экране: в ячейку С3 введена функция (рис. 8). Рис. 8. 4. Ввести зависимости для ограничений. • Курсор в ячейку «С3». • На панели инструментов кнопка «Копировать в буфер». • Курсор в ячейку «С4». • На панели инструментов кнопка «Вставить из буфера». • Курсор в ячейку «С5». • На панели инструментов кнопка «Вставить из буфера». • Курсор в ячейку «С6». • На панели инструментов кнопка «Вставить из буфера». • Курсор в ячейку «С7». • На панели инструментов кнопка «Вставить из буфера». Рис. 9. Примечание. Содержимое ячеек С4 – С7 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис. 9 (в качестве примера представлено содержимое ячейки С5 рис. 10). Рис. 11. В строке «Меню» указатель мышки на имя «Сервис». В развернутом меню команда «Поиск решения». Появляется диалоговое окно «Поиск решения» (рис. 12). Рис. 12. 5. Назначить целевую функцию (установить целевую ячейку), указать адреса изменяемых ячеек. • Курсор в строку «Установить целевую ячейку». • Введите адрес ячейки «$С$3». • Введите направление целевой функции в зависимости от условия вашей задачи: «Максимальному значению» («Минимальному значению»). • Курсор в строку «Изменяя ячейки». • Ввести адреса искомых переменных А$2:В$2. (Рис. 13) Рис. 13. 6. Ввести ограничения • Указатель мышки на кнопку «Добавить. Появляется диалоговое окно «Добавление ограничения» • В строке «Ссылка на ячейку» введите адрес $С$4. • Ввести знак ограничения ≤. • В строке «Ограничение» введите адрес $D$4 (рис. 14). Рис. 14 • Указатель мышки на кнопку «Добавить». На экране вновь диалоговое окно «Добавление ограничения». • Введите остальные ограничения задачи, по выше описанному алгоритму • После введения последнего ограничения кнопка «ОК». На экране появится диалоговое окно «Поиск решения» с введенными условиями (рис. 15). Рис. 15. 7. Ввести параметры для решения ЗЛП • В диалоговом окне указатель мышки на кнопку «Параметры». На экране появляется диалоговое окно «Параметры поиска решения» (рис. 16). Рис. 16. • Установите флажки в окнах «Линейная модель» (это обеспечит применение симплекс - метода) и «Неотрицательные значения». • Указатель мышки на кнопку «ОК». На экране диалоговое окно «Поиск решения». • Указатель мышки на кнопку «Выполнить». Через непродолжительное время появится диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками А3:В3 для значений Хi и ячейка С3 с максимальным значением целевой функции (рис. 17). Рис. 17. В результате решения задачи получили ответ: Х1 = 70 - необходимо сшить женских костюмов, Х2 = 80 - необходимо сшить мужских костюмов, F(x) = 2300 что бы получить максимальную прибыль. Задача № 10 (Задача о коврах) Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т. п. Допустим, например, ресурсы трех видов рабочая сила, сырье и оборудование имеются в количестве соответственно 80(чел/дней), 480(кг), 130 (станко/часов). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса необходимых для производства одного ковра каждого вида и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в таблице. Ресурсы Нормы расхода ресурсов на единицу изделия Наличие ресурсов Ковер А Ковер В Ковер С Ковер D Труд 7 2 2 6 80 Сырье 5 8 4 3 480 Оборудование 2 4 1 8 130 Цена (тыс.руб.) 3 4 3 1 Требуется найти такой план выпуска продукции, при котором общая стоимость продукции будет максимальная. 1. Сформулируем экономико - математическую модель задачи. Обозначим через Х1, Х2, Х3, Х4 количество ковров каждого типа. Целевая функция - это выражение, которое необходимо максимизировать f(x) = 3Х1 +4Х2 +3Х3 +Х4 Ограничения по ресурсам 7Х1 +2Х2 +2Х3 +6Х4 80 5Х1 +8Х2 +4Х3 +3Х4480 2Х1 +4Х2 +Х3 +8Х4130 Х1, Х2, Х3, Х40 Решение 1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначьте через Х1, Х2, Хз, Х4 количество ковров каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2, Хз, Х4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции в ячейке F4. 2. Ввести исходные данные. Введем исходные данные в созданную форму. В результате получим (рис. 19): Рис. 19. 3. Введем зависимость для целевой функции • Курсор в F4. • Курсор на кнопку Мастер функций. На экране диалоговое окно Мастер функций шаг 1 из 2. • Курсор в окно Категория на категорию Математические. Рис. 20. • Курсор в окно Функции на СУММПРОИЗВ. • В массив 1 ввести3 В$3:E$3. • В массив 2 ввести В4:E4. • Готово. На экране: в F4 введена функция, как показано на рис. 20. 4. Введем зависимость для левых частей ограничений: • Курсор в F4. • Копировать в буфер. • Курсор в F7. • Вставить из буфера. • Курсор в F8. • Вставить из буфера. • Курсор в F9. • Вставить из буфера. На этом ввод зависимостей закончен. Запуск Поиска решения. 6) Назначение целевой функции (установить целевую ячейку). • Курсор в поле Установить целевую ячейку. • Ввести адрес $F$4. • Ввести направление целевой функции: Максимальному значению. Ввести адреса искомых переменных: • Курсор в поле Изменяя ячейки. • Ввести адреса В$3:E$3. 5. Ввод ограничений. Курсор в поле Добавить. Появится диалоговое окно Добавление ограничения (рис. 21). Рис. 21.  В окне Ссылка на ячейку ввести $F$7.  Ввести знак ограничение .  Курсор в правое окно. Вести $H$7.  Добавить. На экране опять диалоговое окно Добавление ограничения. Ввести остальные ограничения.  После ввода последнего ограничения ввести ОК. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 22). Рис. 22. 8) Ввод параметров для решения ЗЛП (рис. 23). • Открыть окно Параметры поиска решения. • Установить флажок Линейная модель, что обеспечивает применение симплекс-метода. • Установить флажок Неотрицательные значения. • ОК (На экране диалоговое окно поиска решения). • Выполнить (На экране диалоговое окно результаты поиска решения – рис. 24) Рис. 23. Рис. 24. Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи (ресурс сырье) будет использовано 280 кг. Лекция 2. Транспортные задачи Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам. Специфика ввода условия двухиндексной задачи ЛП состоит лишь в удобстве матричного задания переменных задачи и коэффициентов ЦФ. Рассмотрим решение двухиндексной задачи, суть которой заключается в оптимальной организации транспортных перевозок штучного товара со складов в магазины (табл.1.2). Таблица 1.2 Исходные данные транспортной задачи Тарифы, руб./шт. 1-й магазин 2-й магазин 3-й магазин Запасы, шт. 1-й склад 2 9 7 25 2-й склад 1 5 50 3-й склад 5 4 100 35 4-й склад 2 3 6 75 Потребности, шт. 45 90 50 Целевая функция и ограничения данной задачи имеют вид (1.5) Экранные формы, задание переменных, целевой функции, ограничений и граничных условий двухиндексной задачи (1.5) и ее решение представлены на рис.1.15, 1.16, 1.17 и в табл.1.3. Рис.1.15. Экранная форма двухиндексной задачи (1.5) (курсор в целевой ячейке F15) Таблица 1.3 Формулы экранной формы задачи (1.5) Объект математической модели Выражение в Excel Переменные задачи C3:E6 Формула в целевой ячейке F15 =СУММПРОИЗВ(C3:E6;C12:E15) Ограничения по строкам в ячейках F3, F4, F5, F6 =СУММ(C3:E3) =СУММ(C4:E4) =СУММ(C5:E5) =СУММ(C6:E6) Ограничения по столбцам в ячейках С7, D7, E7 =СУММ(C3:C6) =СУММ(D3:D6) =СУММ(E3:E6) Суммарные запасы и потребности в ячейках H8, G9 =СУММ(H3:H6) =СУММ(C9:E9) Рис.1.16. Ограничения и граничные условия задачи (1.5) Рис.1.17. Экранная форма после получения решения задачи (1.5) (курсор в целевой ячейке F15) Лекция 3. Задачи с булевыми переменными (задачи о назначениях) Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми. На рис.1.18 представлена экранная форма с решением некоторой двухиндексной задачи с булевыми переменными. Рис.1.18. Решение двухиндексной задачи с булевыми переменными Помимо задания требования целочисленности (см. подразд.1.3.2) при вводе условия задач с булевыми переменными необходимо: • для наглядности восприятия ввести в экранную форму слово "булевы" в качестве характеристики переменных (см. рис.1.18); • в окне "Поиск решения" добавить граничные условия, имеющие смысл ограничения значений переменных по их единичной верхней границе (рис.1.19). Рис.1.19. Добавление условия единичной верхней границы значений переменных двухиндексной задачи с булевыми переменными Вид окна "Поиск решения" для задачи с булевыми переменными, представленной на рис.1.18, приведен на рис.1.20. Рис.1.20. Окно "Поиск решения" для задачи с булевыми переменными, представленной на рис.1.18