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

Задачи управления с двухиндексными переменными

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

Содержание работы:

1. Задача целочисленного программирования.

2. Двухиндексные задачи ЛП

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

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

Пример 1. Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входят 3 фунта азотных, 4 фунта фосфорных и один фунт калийных удобрений, а в улучшенный - 2 фунта азотных, 6 фунтов фосфорных и 2 фунта калийных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 фунтов азотных, 20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 3 долл., а улучшенный - 4 долл. Сколько и каких наборов удобрений надо купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Решение. Пусть х - количество обычных наборов удобрений, у - количество улучшенных наборов удобрений. L(x, у) = 3х + 4у →min при ограничениях:

Задача целочисленного программирования - №1 - открытая онлайн библиотека

Воспользуемся возможностями Excel и введем уравнения для ограничений и ЦФ с помощью мастера функций. Здесь выберем из категории Математические функцию СУММПРОИЗВ.

Примечание. Функция СУММПРОИЗВ(массив1; массив2; массив3; …) – перемножает соответствующие элементы заданных массивов и возвращает сумму произведений.

Массив1; массив2; массив3;…- это от 2 до 30 массивов, чьи компоненты нужно перемножить, а затем сложить. Аргументы, которые являются массивами, должны иметь одинаковые размерности. Если это не так, то функция СУММПРОИЗВ возвращает значение ошибки #ЗНАЧ!. СУММПРОИЗВ трактует нечисловые элементы массивов как нулевые.

Используя обозначения соответствующих ячеек формулу для расчета ограничений можно записать как сумму произведений каждой из ячеек, отведенных для значений коэффициентов (B3, В4), на соответствующую ячейку, отведенную для переменных задачи (F3, F4) и вычесть, то есть Задача целочисленного программирования - №2 - открытая онлайн библиотека . То есть чтобы задать эту формулу необходимо в ячейку В7 ввести следующее выражение и нажать клавишу «Enter»=СУММПРОИЗВ( В3:В4, $F$3:$F$4) – В5. Она скопирована в C7:Е7(в ячейке Е7 она скорректирована, убрано вычитаемое Е5). Выделим ячейку с целевой функцией и вызовем «Сервис/ Поиск решения». В диалоговом окне укажем: «Установить целевую ячейку:» $Е$7, «минимальное значение», «изменяя ячейки» $F$3:$F$4, «ограничения» $B$7:$D$7>=0. В окне «Параметры» установим флажок «Линейная модель» и «Неотрицательные значения». Запустим выполнение. Поиск решения вернет результат: х= 1.5,у = 2.15. Целевая функция равна 15.5. Но наборы удобрений нельзя покупать частями! Нужно наложить еще одно ограничение: х, у - целые числа. Вновь вызываем Решатель, нажимаем кнопку «Добавить» и в диалоговом окне «Добавление ограничения» указываем, что $F$3:$F$4 - целые (в том же выпадающем списке, откуда ранее мы выбирали символ для ограничения). Нажимаем «ОК». Запустим выполнение. На этот раз получим значение целевой функции 17 (естественно, оно ухудшилось), а количество наборов стало таким: х = 3, у = 2.

Задача целочисленного программирования - №3 - открытая онлайн библиотека

Пример 2.В контейнер упакованы комплектующие изделия трех типов. Стоимость и вес одного изделия составляют 400 руб. и 12 кг для первого типа, 500 руб. и 16 кг для второго типа, 600 руб. и 15 кг для третьего типа. Общий вес комплектующих равен 326 кг. Определить максимальную и минимальную возможную суммарную стоимость находящихся в контейнере комплектующих изделий.

Решение. x, y, z –количество комплектующих 1-го, 2-го и 3-го типа.

L(x, у, z) = 400х + 500у+600z →min(max)

Ограничения Задача целочисленного программирования - №4 - открытая онлайн библиотека . Целевая функция равна 12600 руб. и 10500 руб.

К задачам целочисленного программирования относят также задачи, где некоторые переменные могут принимать всего два значения: 0 и 1. Такие переменные называют булевыми, двоичными, бинарными.

Пример 3.Имеются 6 предметов, каждый из которых характеризуется весом и ценой (см. рис.). Нужно выбрать из них такие предметы, чтобы их общий вес не превышал 12, а суммарная цена была максимальной (так называемая "задача о рюкзаке").

Решение. В блоке А20:А25 размещены условные названия предметов, а в соседних столбцах - их вес и цена. В блоке D20:D25 фиксируется наличие (1) или отсутствие (0) предмета в наборе. Блокам даны имена в соответствии с их заголовками. В Решателе задаем: максимизировать $А$27 по переменным "наличие" при ограничениях $А$26<=0 и наличие=двоичное. Последнее ограничение задается так. В диалоговом окне "Добавление ограничения" сначала нажимаем F3 и вставляем имя "наличие", в выпадающем списке выбираем "двоич". После запуска Решателя он выдает сообщение – значение целевой ячейки равно 23, а двоичные значения: 0, 1,0, 0, 1, 0, т.е. нужно выбрать второй и пятый предметы.

Задача целочисленного программирования - №5 - открытая онлайн библиотека

Двухиндексные задачи ЛП

Выполнить заказ по производству 32 изделий Задача целочисленного программирования - №6 - открытая онлайн библиотека и 4 изделий Задача целочисленного программирования - №7 - открытая онлайн библиотека взялись бригады Задача целочисленного программирования - №8 - открытая онлайн библиотека и Задача целочисленного программирования - №9 - открытая онлайн библиотека . Производительность бригады Задача целочисленного программирования - №8 - открытая онлайн библиотека по производству изделий Задача целочисленного программирования - №6 - открытая онлайн библиотека и Задача целочисленного программирования - №7 - открытая онлайн библиотека составляет соответственно 4 и 2 изделия в час, фонд рабочего времени этой бригады 9,5 ч. Производительность бригады Задача целочисленного программирования - №9 - открытая онлайн библиотека – соответственно 1 и 3 изделия в час, а ее фонд рабочего времени – 4 ч. Затраты, связанные с производством единицы изделия, для бригады Задача целочисленного программирования - №8 - открытая онлайн библиотека равны соответственно 9 и 20 руб., для бригады Задача целочисленного программирования - №9 - открытая онлайн библиотека – 15 и 30 руб.

Составьте математическую модель задачи, позволяющую найти оптимальный объем выпуска изделий, обеспечивающий минимальные затраты на выполнение заказа.

Решение. Искомыми величинами в задаче являются объемы выпуска изделий. Изделия Задача целочисленного программирования - №6 - открытая онлайн библиотека будут выпускаться двумя бригадами Задача целочисленного программирования - №8 - открытая онлайн библиотека и Задача целочисленного программирования - №9 - открытая онлайн библиотека . Поэтому необходимо различать количество изделий Задача целочисленного программирования - №6 - открытая онлайн библиотека , произведенных бригадой Задача целочисленного программирования - №8 - открытая онлайн библиотека , и количество изделий И1, произведенных бригадой Задача целочисленного программирования - №9 - открытая онлайн библиотека . Аналогично, объемы выпуска изделий Задача целочисленного программирования - №7 - открытая онлайн библиотека бригадой Задача целочисленного программирования - №8 - открытая онлайн библиотека и бригадой Задача целочисленного программирования - №9 - открытая онлайн библиотека также являются различными величинами. Вследствие этого в данной задаче 4 переменные. Для удобства восприятия будем использовать двухиндексную форму записи Задача целочисленного программирования - №25 - открытая онлайн библиотека – количество изделий Задача целочисленного программирования - №26 - открытая онлайн библиотека (j=1,2), изготавливаемых бригадой Задача целочисленного программирования - №27 - открытая онлайн библиотека (i=1,2), а именно,

Задача целочисленного программирования - №28 - открытая онлайн библиотека – количество изделий Задача целочисленного программирования - №6 - открытая онлайн библиотека , изготавливаемых бригадой Задача целочисленного программирования - №8 - открытая онлайн библиотека , [шт.]; Задача целочисленного программирования - №31 - открытая онлайн библиотека – количество изделий Задача целочисленного программирования - №7 - открытая онлайн библиотека , изготавливаемых бригадой Задача целочисленного программирования - №8 - открытая онлайн библиотека , [шт.]; Задача целочисленного программирования - №34 - открытая онлайн библиотека – количество изделий Задача целочисленного программирования - №6 - открытая онлайн библиотека , изготавливаемых бригадой Задача целочисленного программирования - №9 - открытая онлайн библиотека , [шт.]; Задача целочисленного программирования - №37 - открытая онлайн библиотека – количество изделий Задача целочисленного программирования - №7 - открытая онлайн библиотека , изготавливаемых бригадой Задача целочисленного программирования - №9 - открытая онлайн библиотека , шт.].

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

Целью решения задачи является выполнение плана с минимальными затратами, т.е. критерием эффективности решения служит показатель затрат на выполнение всего заказа. Поэтому ЦФ должна быть представлена формулой расчета этих затрат. Затраты каждой бригады на производство одного изделия Задача целочисленного программирования - №6 - открытая онлайн библиотека и Задача целочисленного программирования - №7 - открытая онлайн библиотека известны из условия.

Таким образом, ЦФ имеет вид

Задача целочисленного программирования - №42 - открытая онлайн библиотека , Задача целочисленного программирования - №43 - открытая онлайн библиотека

Ограничения

Возможные объемы производства изделий бригадами ограничиваются следующими условиями:

· общее количество изделий Задача целочисленного программирования - №6 - открытая онлайн библиотека , выпущенное обеими бригадами, должно равняться 32 шт., а общее количество изделий Задача целочисленного программирования - №7 - открытая онлайн библиотека – 4 шт.;

· время, отпущенное на работу над данным заказом, составляет для бригады Задача целочисленного программирования - №8 - открытая онлайн библиотека – 9,5 ч, а для бригады Задача целочисленного программирования - №9 - открытая онлайн библиотека – 4 ч;

· объемы производства изделий не могут быть отрицательными величинами.

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

1) величиной заказа на производство изделий;

2) фондами времени, выделенными бригадам;

3) неотрицательностью объемов производства.

Для удобства составления ограничений запишем исходные данные в виде таблицы 1.

Таблица 1

Бригада Производительность бригад, шт/ч Фонд рабочего времени, ч
Задача целочисленного программирования - №48 - открытая онлайн библиотека Задача целочисленного программирования - №49 - открытая онлайн библиотека
Задача целочисленного программирования - №8 - открытая онлайн библиотека 9,5
Задача целочисленного программирования - №9 - открытая онлайн библиотека
Заказ, шт  

Ограничения по заказу изделий имеют следующий вид

Задача целочисленного программирования - №52 - открытая онлайн библиотека и

Задача целочисленного программирования - №53 - открытая онлайн библиотека .

Ограничение по фондам времени содержательную форму

Задача целочисленного программирования - №54 - открытая онлайн библиотека

и

Задача целочисленного программирования - №55 - открытая онлайн библиотека .

Проблема заключается в том, что в условии задачи прямо не задано время, которое тратят бригады на выпуск одного изделия Задача целочисленного программирования - №6 - открытая онлайн библиотека или Задача целочисленного программирования - №7 - открытая онлайн библиотека , т.е. не задана трудоемкость производства. Но имеется информация о производительности каждой бригады, т.е. о количестве производимых изделий в 1 ч. Трудоемкость Тр и производительность Пр являются обратными величинами, т.е.

Задача целочисленного программирования - №58 - открытая онлайн библиотека .

Поэтому используя таблицу 1, получаем следующую информацию:

® Задача целочисленного программирования - №59 - открытая онлайн библиотека ч тратит бригада Задача целочисленного программирования - №8 - открытая онлайн библиотека на производство одного изделия Задача целочисленного программирования - №6 - открытая онлайн библиотека ;

® Задача целочисленного программирования - №62 - открытая онлайн библиотека ч тратит бригада Задача целочисленного программирования - №8 - открытая онлайн библиотека на производство одного изделия Задача целочисленного программирования - №64 - открытая онлайн библиотека ;

® Задача целочисленного программирования - №65 - открытая онлайн библиотека ч тратит бригада Задача целочисленного программирования - №66 - открытая онлайн библиотека на производство одного изделия Задача целочисленного программирования - №6 - открытая онлайн библиотека ;

® Задача целочисленного программирования - №68 - открытая онлайн библиотека ч тратит бригада Задача целочисленного программирования - №66 - открытая онлайн библиотека на производство одного изделия Задача целочисленного программирования - №64 - открытая онлайн библиотека .

Запишем ограничения по фондам времени в математическом виде

Задача целочисленного программирования - №71 - открытая онлайн библиотека

и

Задача целочисленного программирования - №72 - открытая онлайн библиотека .