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 НИИ для задач с двумя пере-