1. Линейность: переменные решения линейно входят в ограничения и целевую функцию.
2. Делимость: допускаются нецелые значения переменных решения.
3. Уверенность: значения параметров известны и постоянны.
4. Неотрицательность: отрицательные значения переменных недопустимы. Пример 1 представляет компоненты модели линейного программирования.
Пример 1
XI = количество изделия 1 для производства Переменные решения Х2 = количество изделия 2 для производства
хз = количество изделия 3 для производства
Максимизировать бх + 8x2 + 4 Х3 (прибыль) (целевая функция)
Ограничения
Рабочее время 2 xi + 4 Х2 + 3 Х3 < 250 часов
Материал 7 х + 6 хг + 5 Хз < 100 фунтов
Изделие 1 х, > 10 единиц
Условие xi, Х2, Хз > О
неотрицательности
Сначала указываются и определяются переменные решения. Они обычно представляют количество. В данном случае, это количества трех различных изделий, которью можно производить.
Затем определяется целевая функция. В нее входит каждая переменная в модели и доля (прибыль на единицу продукции) каждой переменной. Так, изделие х имеет прибыль $5 за единицу. Прибьшь от изделия xi, для данного решения будет в 5 раз больше значения х, указанного в решении; общая прибыль от всех изделий будет равна сумме прибылей от каждого отдельного изделия. Таким образом, если х, =10, Х2 = О и Хз = 12, то значение целевой функции будет: 1 5(10) + 8(0) + 4(12) = 98
I За целевой функцией следует (в произвольном порядке) список трех ограничений, j Каждое ограничение имеет справа числовое значение (например, ограничение про-! должительности рабочего времени имеет значение 250), которое показывает вели-j чину ограничения, - а слева алгебраический символ, который показывает, является I это значение максимальным (<), минимальным (>) или равным (=). Левая часть каж-I дого ограничения состоит из переменных, к которым относится это ограничение, и I коэффициента для каждой переменной, который показывает, какое количество 1 представляет собой одна единица переменной решения. Например, для ограниче-I ния по продолжительности рабочего времени, одна единица xi будет требовать двух I часов рабочего времени. Сумма значений в левой части каждого ограничения пред-I ставляет количество этого ограничения, которое использовано в данном решении. I Так, если х, = 10, Х2 = О, и Х3 = 12, то количество использованного труда таково:
2 (10) + 4 (0) + 3 (12) = 56 часов 1 Так как эта сумма в левой части ограничения не превышает значения в правой, дан-i ное ограничение выполнимо.
I Обратите внимание, что третье ограничение, относящееся к единственной перемен-; ной XI, должно быть по крайней мере 10 единиц. Его коэффициент равен единице, [ хотя это и не показано.
параметрами. Параметры - это фиксированные (постоянные) величины; модель
.....4„-ет"4™ можно решить только если эти величины заданы.
метрь7 - числовые эффективного использования моделей линей-
константы. у "ого программирования, они должны удовлетворять
,,,,*ssi-*«,»i следующим посылкам:
I Наконец, имеются ограничения неотрицательности. Они внесены в список отдель-I ной строкой и отражают тот факт, что никакое значение переменной не может быть I отрицательным.
Построение модели
Для построения модели в линейном программировании необходимо понимание всех ее компонентов (составляющих). Это помогает организовать процесс преобразования информации о проблеме в модель.
Разумееся, очень важно получить достоверную информацию о применимых ограничениях, а также о правильных значениях параметров. В противном случае, полезность модели будет сомнительной. Следовательно, в некоторых случаях значительные усилия должны быть затрачены для получения такой информации.
В построении модели используйте форму, показанную в примере 1. Начните с определения переменных решения. Очень часто эти переменные обозначают количество чего-либо (например, Х] = количество изделия 1). Обычно переменные связаны с прибылью, затратами, сроками и другими подобными величинами. Знание этого факта поможет вам определить переменные решения в задаче.
Ограничения - это пределы или требования к одной или нескольким переменным, они относятся к доступному количеству ресурсов (рабочей силы, материалов, или машинного времени), или к минимальным требованиям (типа «изготовить не менее 10 единиц изделия 1»), Целесообразно дать наименование каждому ограничению («Рабочая сила», «Материал 1» и т.д.). Рассмотрим некоторые из ограничений, с которыми вы можете столкнуться.
1. Ограничение, относящееся к одной или нескольким переменным. Это наиболее типичный вид ограничения. Ограничения в примере 1 относятся именно к этому типу.
2. Ограничение, определяющее соотношение. Например, «отношение Х] к Х2 должно быть не менее чем 3 :2». Данное условие описывается формулой:
Х2-2
Выполнив соответствующую математическую операцию, получаем:
2xi>3x2
Однако данная форма все еще не приемлема, так как все переменные ограничения должны находиться в левой части неравенства (или равенства), а правая часть должна содержать только постоянные значения. Поэтому перенесем все переменные данного неравенства в левую часть и получим:
2xi-3x2>0
(Обратите внимание, что направление неравенства остается тем же самым.)
3. Ограничение, определяющее процентное соотношение одной или более переменных относительно другой или других переменных. Например, «Х] не может составлять более 20% от общего». Предположим, что общее состоит из переменных щ, Х2, и хз- Математически это можно записать в следующем виде:
Х1<0,20(х, + Х2+ хз)
Как обычно, все переменные должны быть сгруппированы в левой части данного соотношения. Для этого раскрываем скобки в правой части и производим перегруппировку:
X, <0,20 XI + 0,20 Х2 + 0,20 Хз
То есть:
0,80 XI - 0,20 Х2 - 0,20 Х3 < О
Когда модель построена, то следующий этап заключается в ее решении. В следующих разделах мы рассмотрим три подхода к прикладному решению: графический, симплексный и компьютерный.
менными.
Содержание графической процедуры
Графический метод линейного программирования отображает ограничения в виде графиков и определяет область, которая удовлетворяет всем ограничениям. Эта область называется областью возможных решений (feasible solutions space). Затем выстраивается целевая функция; она используется для определения оптимальной точки в области возможных решений. Координаты точки могут читаться непосредственно с графика, хотя обычно необходимо их алгебраическое определение.
Обычный порядок действий в графическом подходе выглядит следующим образом:
1. Математически представить целевую функцию и ограничения.
2. Выстроить на графике ограничения.
3. Определить область возможных решений.
4. Выстроить на графике целевую функцию.
5. Найти оптимальное решение.
Данный подход можно наглядно проиллюстрировать решением типичной задачи.
Рассмотрим следующее:
Два изделия могут производиться на определенном оборудовании. На производство этих изделий имеется 12 часов времени. Изделие 1 требует 1 час на единицу, а изделие 2 требует 3 часа на единицу. Оба изделия изготавливаются из одинакового сырья. На производство изделия 1 требуется 4 фунта материала, а для изделия 2 требуется 3 фунта. Для производства обоих изделий имеется в наличии 24 фунта сырья. Если цель - получение максимальной прибыли от этих изделий, изделие 1 дает прибыль $4 с единицы, а изделие 2 - $5 с единицы, то какое количество каждого изделия следует произвести?
Для решения данной задачи необходимо записать условия в математической форме. Это выглядит следующим образом:
1. Определить переменные решения. В данном случае они таковы: XI = количество изделия 1
Х2= количество изделия 2.
2. Записать формулу целевой функции. Она такова: Максимизировать Z = 4 xi + 5 Х2
3. Определить ограничения и записать их формулу. В данном случае имеются два ограничения: машинное время и сырье. Ограничения таковы: Машинное время: xi + 3 Х2< 12
Сырье:4х1 + Зх2<24
4. Добавить требования неотрицательности: xi, Х2>0 Таким образом, модель выглядит следующим образом:
Максимизация функции: Z = 4X + 5x2 Ограничения:
Машинное время: Xi + 3x2<12
Сырье: 4х, + 3х2<24
Неотрицательность: xi,X2>0 Следующий шаг - построение ограничений.
Графический метод линейного программирования
Графический метод в линейном программировании - ? г л - 1
метод поиска оптимальных решений для задач с двумя „ейногопрограмва-переменными. Этот подход описывается в данном раз- ния - графический метод gjje. I поиска оптимальных реше-
I НИИ для задач с двумя пере-