Характеристика задач линейного программирования

Размещено на http://www.allbest.ru/

1. Задачи оптимизации

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

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

, (1)

где ci - некоторые константы, при условии, что переменные удовлетворяют системе линейных равенств и неравенств:

, (2)

, (3)

, (4)

где - линейные функции, - действительные числа ().

Функция, экстремальное значение которой требуется найти, называется целевой функцией. Решения, удовлетворяющие системе ограничений называются допустимыми, а решения, удовлетворяющие одновременно ограничениям и требованиям минимизации (максимизации) целевой функции - оптимальными.

При постановке задачи линейного программирования необходимо:

1. Определить от каких переменных зависит целевая функция.

2. Составить систему ограничений на переменные.

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

2. Задача оптимального использования ресурсов

Предположим, что предприятие может выпускать n различных видов продукции при известных нормах затрат. Требуется построить оптимальный план выпуска продукции, чтобы прибыль от ее реализации была максимальной. При этом необходимо учитывать ограниченность m различных ресурсов.

Обозначим ai,j - объём i-ого ресурса, который расходуется на производство одной единицы j-ого вида продукции; xj - количество единиц j-ого вида продукции в производственном плане предприятия; bi - максимальное количество i-ого вида ресурса; сj - прибыль на единицу j-ого вида продукции (i=1,…,m; j=1,…,n).

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

, (5)

Тогда, учитывая ограничения на ресурсы, получаем следующую систему неравенств:

(6)

(7)

(8)

(9)

(i=1,…,n), (10)

Кроме того, в некоторых случаях (в зависимости от единицы измерения выпускаемой продукции) следует предполагать, что xi принимают целые значения.

Пример 1. Предприятие выпускает 2 вида продукции. Цена единицы 1 вида продукции - 25 000 руб., 2 вида продукции - 50 000 руб. Для изготовления продукции используются три вида сырья, запасы которого 37, 57.6 и 7 условных единиц. Нормы затрат каждого сырья на единицу продукции представлены в следующей таблице.

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

Решение. Пусть продукция производится в количестве: 1-й вид - x1 единиц, 2-й вид - x2 единиц. Тогда стоимость произведенной продукции выражается целевой функцией:

f(x1,x2)=25000 x1+50000x2,

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

1.2 x1+1.9 x2 37;

2.3 x1+1.8 x2 57,6;

0.1 x1+0.7 x2 7;

x10, x2 0.

Также будем предполагать, что x1 и x2 принимают целые значения.

Запишем полученную математическую модель в новом документе MS Excel (рис. 2.2.1).

Рис. 1

Внесем в таблицу значения стоимости продукции, данные о расходах и запасах всех видов сырья. При этом будем предполагать, что первоначально x1 и x2 равны нулю (ячейки C2 и D2). В ячейку H1 запишем целевую функцию:

=C2*C3+D2*D3

Столбец Затраты заполним следующими значениями:

Найдем решение данной задачи используя пакет Поиск решения MS Excel.

Пакет Поиск решений (Solver) - дополнительная надстройка MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации.

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

· количество неизвестных (decision variable) - 200;

· количество формульных ограничений (explicit constraint) на неизвестные - 100;

· количество предельных условий (simple constraint) на неизвестные - 400.

Вызов пакета Поиск решения осуществляется выбором в меню «Сервис» вкладки «Поиск решения» (рис. 2.2.2).

Рис. 2

Если пакет Поиск решения отсутствует, то для его установки необходимо:

1. В меню «Сервис» выбрать вкладку «Надстройки» (рис. 2.2.3).

2. Установить флажок возле строки «Поиск решения» (рис. 2.2.4).

Рис. 3

Рис. 4

В окне Поиск решения следует выполнить следующие действия (рис. 2.2.5):

1. Установить целевую ячейку (ячейка H1);

2. Указать, что необходимо найти максимальное значение целевой функции;

3. Указать адреса изменяющихся ячеек, т.е. ячеек в которых находятся значения переменных x1 и x2 (ячейки C2 и D2);

Рис. 5

4. Добавить все необходимые ограничения, используя раскрывающийся список условных операторов ( <=, =, >=, цел. или двоич.) (рис. 2.2.6). Если выбран цел., то в поле Ограничение появится «целое». Если выбрано двоич., в поле Ограничение появится «двоичное»;

Рис. 6

5. При необходимости изменить параметры поиска решения (рис. 2.2.7).

Рис. 7

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

Предельное число итераций - управляет временем решения задачи путем ограничения числа вычислительных циклов (итераций).

Относительная погрешность - определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.

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

Сходимость - применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается.

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

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

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

Показывать результаты итераций - приостанавливает поиск решения для просмотра результатов отдельных итераций.

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

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

Оценка линейная - выбор этого переключателя означает работу с линейной моделью. линейный программирование транспортный задача

Оценка квадратичная - выбор этого переключателя означает работу с нелинейной моделью.

Разности прямые - используется в большинстве задач, где скорость изменения ограничений относительно невысока. Увеличивает скорость работы средства Поиск решения.

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

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

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

6. Нажать кнопку Выполнить.

7. В окне результатов поиска решения выбрать операцию сохранения найденного решения (рис. 2.2.8).

Более того, по найденным результатам можно создавать отчеты. Отчеты полезны для сравнения влияния на решение различных ограничений или исходных данных. Поэтому они являются очень важными инструментами для анализа полученных результатов и последующего их улучшения в зависимости от возможностей и ресурсов предприятия. Отчеты бывают трех типов: по результатам (Answer), по устойчивости (Sensitivity), по пределам (Limit).

Тип отчета выбирается по окончании поиска решений в диалоговом окне Результаты поиска решений (Solver results) в списке Отчеты (Reports). С помощью левой клавиши мыши, при нажатой клавиши <Ctrl>, можно выбрать сразу два или три типа отчета. При этом каждый отчет будет создан на отдельном рабочем листе.

Рис. 8

Из отчета, составленного по результатам (рис. 2.2.9), получим, что максимальная стоимость произведенной продукции рана 825 000 руб. При этом должен выполняться следующий план производства: 1-ый вид продукции - 19 единиц, 2-ой вид продукции - 7 единиц.

Рис. 9

Пример 2. Банк собирается выдать кредиты по следующим типам:

Общая сумма кредитов не должна превышать 1 000 млн. р. При этом банк обязан выдать не менее 30% всех кредитов на покупку авто и не более 50% - на жилье. Общая доля невозврата не должна превосходить 0.09. Определить какую сумму следует выдавать банку на каждый вид кредита, чтобы максимизировать общий доход.

Пример 3. Компания производит 2 типа деталей. Для производства 1 детали первого типа требуется 1 человеко-час, а для производства детали второго типа требуется 2 человеко-часа. Фонд рабочего времени компании 4000 человеко-часов в неделю. Производственные мощности позволяют выпускать максимум 2250 деталей первого типа и 1750 деталей второго типа в неделю. Каждая деталь первого типа требует 2 кг металлических стержней и 5 кг листового металла. Для производства одной детали второго типа необходимо 5 кг стержней и 2 кг листового металла. Запас каждого вида сырья 10000 кг в неделю. Известно, что еженедельно завод поставляет заказчику не менее 600 деталей первого типа. Сколько деталей каждого типа следует производить, чтобы максимизировать общую прибыль за неделю. Если прибыль от производства одной детали первого типа составляет 30 у.е., а от производства одной детали второго типа - 40 у.е.

Пример 4. Оператор сотовой связи имеет следующие минимальные потребности в количестве сотрудников в различное время суток:

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

3. Транспортная задача

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов производства A1,…, Am, в которых сосредоточены запасы однородных продуктов в количестве a1,…, am единиц. Кроме того имеется n пунктов потребления B1,…, Bn, потребность которых в указанных продуктах составляет b1,…, bn единиц. Известны также транспортные расходы ci,j, связанные с перевозкой единицы продукта из пункта Ai в пункт Bj, i 1,…, m; j 1,..., n. Требуется составить такой план перевозок, чтобы удовлетворить спрос всех пунктов потребления, при минимальной общей стоимости всех перевозок.

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

, (11)

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно не превышать запаса продукта в данном пункте. Формально это означает, что

(), (12)

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

(), (13)

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

(,), (14)

Таким образом, транспортная задача сводится, к минимизации суммарных затрат при полном удовлетворении спроса.

Пример 5. Предприятие имеет три склада со своей продукцией:

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

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

Необходимо составить план перевозок так, чтобы стоимость перевозок была минимальной.

Задания

1. Фирма должна отправить некоторое количество единиц своей продукции с трех складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 единиц продукции, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 единиц продукции. Стоимость перевозки одной единицы продукции со склада в магазин приведены в таблице:

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

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

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

3. Фабрика производит два вида лака - для внутренних и наружных работ. Для производства лаков используется два вида исходных продуктов - нефть и кислота.

Максимально возможные суточные запасы этих продуктов определяются емкостями их хранения и равны 6 и 8 тонн (т) соответственно. Для производства 1 т. лака для внутренних работ расходуется 1 т. нефти и 2 т. кислоты, а для производства 1 т. лака для наружных работ расходуется 2 т. нефти и 1 т. кислоты. Суточный спрос на лак для наружных работ не превышает 2 т. Спрос на лак для внутренних работ неограничен.

Доход от реализации 1 т. лака для внутренних работ равен 3 млн. рублей, а доход от реализации 1 т. лака для наружных работ - 2 млн. рублей.

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

Размещено на Allbest.ru