СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. Геометрический метод решения задач ЛП
2. Симплекс-метод
2.1 Идея симплекс-метода
2.2 Реализация симплекс-метода напримере
2.3 Табличная реализация простогосимплекс-метода
ЗАКЛЮЧЕНИЕ
СПИСОКИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Темамоей работы касается решения задач, возникающих в экономике. При этом встаетвопрос о выборе наилучшего в некотором смысле варианта решения. А на поиск возможноговарианта часто влияют разного рода факторы, сужающие рамки выбора. Иначеговоря, требуется решить задачу оптимизации, которая состоит в необходимостивыбора наилучшего варианта решений среди некоторого, как правило, ограниченногомножества возможных вариантов.
Задачаоптимизации может быть сформулирована на языке математики, если множестводоступных вариантов удается описать с помощью математических соотношений(равенств, неравенств, уравнений), а каждое решение — оценить количественно спомощью некоторого показателя, называемого критерием оптимальности или целевой функцией.Тогда наилучшим решением будет то, которое доставляет целевой функциинаибольшее или наименьшее значение, в зависимости от содержательного смыслазадачи. Так, например, при инвестировании ограниченной суммы средств внесколько проектов естественной является задача выбора тех проектов, которыемогут принести в будущем наибольшую прибыль. При доставке в магазины продукцииот различных поставщиков возникает задача минимизации транспортных затрат.
Процессформализации задачи называется построением ее математической модели. Он состоитиз трех этапов.
1. Выбор параметровзадачи, от которых зависит решение. Эти параметры называют управляющимипеременными и обозначают />, формируя из нихвектор />. Принять решение – это значитзадать конкретные значения переменных.
2. Построениечислового критерия, по которому можно сравнивать различные варианты решений.Такой критерий принято называть целевой функцией и обозначать через />.
3. Описание всегомножества X допустимых значений переменных –ограничений, связанных с наличием материальных ресурсов, финансовых средств,технологическими возможностями и т.п..
Математическаязадача оптимизации состоит в нахождении такого допустимого решения />, которое доставляет целевой функциинаибольшее или наименьшее значение среди всех возможных решений.
/>.
1. Геометрический метод решения задач ЛП
Этотметод часто используется при решении задач, в которых только две неизвестныхвеличины. Разберем его на следующих примерах:
Пример1.1. (Задача о производстве красок).
Небольшаяфабрика изготовляет два вида красок: INT — для внутренних работ иEXT — для наружных работ. В производстве красок используются два исходных продукта Аи В. Из-за малой площади склада максимально возможные суточные запасыэтих продуктов равны 6 т. и 8 т. соответственно. На производство 1 тонны краскиINT расходуется 1 тонна продукта А и 2тонны продукта В,а на изготовление 1 тонны краски EXT идет 2 тонны продукта А и 1тонна продукта В. Фабрика продает краску по цене 3тыс. долл. затонну краски INT и 2 тыс. долл. за тонну краски EXT. Исходныеданные удобно свести в таблицу:Исходные продукты
Расход продукта на 1 т. краски Запас продуктов INT EXT
A 1 2 6
B 2 1 8
Цена 1т. краски 3 тыс. долл. 2 тыс. долл.
Изучениерынка сбыта показало, что суточный спрос на краску EXT никогда непревышает спрос на краску INT, более чем на 1 тонну. Какое количествокраски каждого вида должна производить фабрика в сутки, чтобы доход отреализации продукции был максимален?
Построимматематическую модель задачи. Для этого надо определить переменные задачи,целевую функцию и ограничения, которым удовлетворяют переменные. Обозначимчерез x1 — планируемый суточный объем производства краскиINT, а через x2 — суточный объем производства краски EXT.Целевая функция f(x) будет выражать суточный доход от продажи краски,равный 3x1 + 2x2 (тыс. долл.). Этот доход подлежитмаксимизации
f(x)= 3x1 + 2x2 ® max.
Построимограничения задачи, связанные с ограниченными запасами продуктов А и В.На производство краски INT в количестве x1(т)будет использовано 1x1(т) продукта А, а напроизводство краски EXT в объеме x2 (т) будетзатрачено 2x2 (т) продукта А. Поскольку суточный запаспродукта А равен 6 т., то расход продукта А на изготовлениекрасок двух видов не может превышать в сутки этой величины: 1x1+2x2£ 6. Аналогичнополучим ограничение, связанное с запасом продукта В: 2x1+1x2£ 8. Ограничение посоотношению спроса на краски можно описать неравенством: x2 — x1£ 1. Учитываяестественные условия неотрицательности объемов выпуска продукции, окончательнополучим следующую задачу линейного программирования
f(x) = 3 x1 + 2 x2®max (1.1)
1 x1 + 2 x2£6, (1.2)
2 x1 + 1 x2£8, (1.3)
— x1+ x2£ 1, (1.4)
x1³ 0, x2³ 0. (1.5)
Построиммножество планов задачи, описываемое ограничениями (1.2)-(1.5). Рассмотримпервое неравенство. Оно задает некоторую полуплоскость, расположенную по однусторону от граничной прямой
p1:1x1+2x2=6
Построимэту прямую на плоскости с координатными осями x1и x2.Для проведения прямой достаточно знать две ее точки. Проще всего найти точкипересечения прямой с осями координат. Полагая x1 = 0, изуравнения прямой получим x2 = 3, а при x2 = 0найдем x1 = 6. Таким образом прямая p1пройдетчерез точки (0,3) и (6,0). Чтобы определить, по какую сторону отпрямой расположена искомая полуплоскость, достаточно подставить в неравенство (1.2)координаты любой точки плоскости. Если прямая не проходит через началокоординат, то удобнее всего взять точку (0, 0). Очевидно, что в этой точкенеравенство (1.2) строго выполняется (1* 0 + 2* 0 , значитполуплоскость, определяемая этим неравенством, лежит ниже прямой p1,включая в себя начало координат. Искомую полуплоскость отметим штриховкой (рис.1.1).
Аналогичнопостроим полуплоскость, задаваемую неравенством (1.3). Для этого нанесемна координатную плоскость граничную прямую
p2:2x1+x2=8,
найдяее точки пересечения с осями координат: (0,8) и (4,0).
Подставляякоординаты точки (0,0) в неравенство (2.3), видим, что начало координатлежит в искомой полуплоскости (2* 0 + 1* 0 , значит все точки,удовлетворяющие неравенству (2.3), расположены левее прямой p2.Отметим эту область штриховкой (рис.1.1).
Точки,задаваемые ограничением (4), находятся ниже прямой
p3:-x1+x2=1,
проходящейчерез точки (0, 1) и (-1, 0).
Наконец,условия неотрицательности: x1³ 0, x2³0задают все точки первой четверти, что также отметим штриховкой.
Выделяятеперь точки плоскости, удовлетворяющие всем ограничениям задачи (1.1)-(1.5),то есть расположенные одновременно во всех заштрихованных полуплоскостях,получаем множество планов X. Оно представляет собой многоугольник (вданной задаче — пятиугольник). Его стороны лежат на прямых, уравнения которых получаютсяиз исходной системы неравенств (1.2)-(1.5) заменой знаков неравенств на строгиеравенства.
/>
Рис. 1.1
Дляграфического представления целевой функции введем понятие линии уровня(изолинии функции).
Определение.Линией уровня (изолинией) функции f(x) называется множество точек x =(x1, x2), в которых она принимает одно и то жепостоянное значение f(x) = h, где h — некоторое число. Длялинейной функции двух переменных f(x) = c1 x1 + c2x2 линия уровня, соответствующая числуh, будетпредставлять прямую с уравнением
c1 x1 + c2 x2 = h (1.6)
Приизменении числа h будем получать семейство линий уровня (параллельныхпрямых) с одним и тем же направляющим вектором c = =(c1, c2),перпендикулярным всем прямым. Известно, что вектор c = (c1, c2)для линейной функции f(x) = c1 x1 +c2 x2указывает направление ее возрастания. Геометрически это означает, чтопри параллельном перемещении прямой (1.6) в направлении целевого вектора c значениецелевой функции возрастает.
Построимлинии уровня целевой функции f(x) = 3x1 + 2 x2 внашей задаче. Их уравнения будут иметь вид 3x1 + 2 x2 =h. Они задают семейство параллельных прямых, зависящих от параметра h.Все прямые перпендикулярны целевому вектору c = (3, 2), составленному изкоэффициентов целевой функции, поэтому для построения семейства линий уровняцелевой функции достаточно построить ее целевой вектор, и провести несколькопрямых, перпендикулярных этому вектору. Линии уровня будем проводить намножестве планов X, помня при этом, что при параллельном перемещениипрямых в направлении целевого вектора c = (3, 2) значениефункции f(x)= 3x1 + 2x2 будет возрастать.Поскольку в задаче оптимальный план должен доставлять целевой функциимаксимально возможное значение, то для решения задачи графически надо средивсех точек x = (x1, x2) множества планов Xнайти такую точку x* = (x1*, x2*),через которую пройдет последняя линия уровня в направлении целевого вектора c= (3,2). Из рисунка 1.2 видно, что искомой точкой будет точка,лежащая в вершине множества X, образованной пересечением прямых p1и p2. Решая систему уравнений, описывающих этипрямые найдемоптимальный план x1* = 3 1/3,x2* = 1 1/3. При этом максимальноезначение целевой функции будет равно f(x*) = 12 2/3.Таким образом, ежесуточно фабрика должна производить 3 1/3тонн краски INT и 11/3 тонн краски EXT,получая при этом доход 12 2/3 тыс. долларов.
x1+ 2 x2 = 6,
2 x1+ x2 = 8,
Пример1.2. Лечебное предприятие закупает два вида мультивитаминных комплексов«Здоровье» и «Долголетие» с содержанием витаминов трех видов. Количество единицэтих витаминов в одном грамме мультикомплексов, необходимая их норма припрофилактическом приеме и стоимость одного грамма комплексов «Здоровье» и«Долголетие» отражены в таблицеВитамины
Кол-во единиц витаминов в 1 гр. комплекса Норма единиц витаминов Здоровье Долголетие
V1 3 1 9
V2 1 2 8
V3 1 6 12
Стоимость 1 грамма комплекса 5 руб. 4 руб.
Сколькограммов мультивитаминных комплексов каждого вида требуется на одинпрофилактический прием, чтобы были получены все витамины не меньше требуемойнормы, и при этом их суммарная стоимость была минимальной.
Составимматематическую модель задачи. Для этого введем переменные: x1–количество комплекса «Здоровье» (гр.), x2– количествокомплекса «Долголетие»(гр.), необходимое для профилактического приема.Целевая функция выражает суммарную стоимость витаминных комплексов, котораядолжна быть минимально возможной
f(x)= 5 x1 + 4 x2® min (1.7)
Ограничения,описывающие выполнение норм по витаминам, имеют вид:
Повитамину V1: 3x1 + x2³ 9, (1.8)
Повитамину V2: x1 + 2x2³8, (1.9)
Повитамину V3: x1 + 6x2³12. (1.10)
Приэтом переменные должны быть неотрицательны: xj ³ 0, j = 1, 2.
Снованачнем решение с построения множества планов X, для чего проведемграничные прямые, уравнения которых получаются при замене в ограничениях знаковнеравенств на равенства
p1: 3 x1+ x2 = 9,
p2: x1 +2 x2 = 8,
p3: x1 +6 x2 = 12.
Подставляякоординаты точки (0,0) в неравенства (1.8)-(1.10) видим, что началокоординат им не удовлетворяет и, следовательно, не входит в множество планов Х.Поэтому штриховки направлены выше и правее граничных прямых. Выделяя точки,удовлетворяющие всем неравенствам и условиям неотрицательности, получаем множествопланов, изображенное на рис. 1.2. В данном примере оно не ограничено.
/>
Рис. 1.2
Изобразимцелевую функцию (1.7) с помощью линий уровня. Для этого достаточно построитьцелевой вектор c = (5, 4) и перпендикулярно ему провести несколькопрямых на множестве Х. Поскольку целевой вектор указывает направлениевозрастания целевой функции, а в задаче о рационе требуется найти ее минимум,то для нахождения оптимального решения будем перемещать линию уровняпараллельно самой себе по множеству Х в направлении, противоположномцелевому вектору.
/>
Рис. 1.3
Последнейточкой множества планов, через которую еще проходит линия уровня будет точкапересечения прямых p1 и p2. Решая системууранений (рис. 1.3).
3 x1+ x2 = 9
x1+ 2 x2 = 8
получимоптимальный план x1* = 2, x2* = 3. Минимальноезначение целевой функции при этом будет равно
f(x*)= 5∙2 + 4∙3 = 22.
Следовательно,самый дешевый набор для профилактического приема состоит из 2 гр.комплекса А и 3 гр. комплекса В, и его стоимость равна 22 руб.
Теперьнесложно сформулировать геометрический способ решения стандартных задач ЛП сдвумя переменными:
· изображается допустимый многоугольник />–пересечение полуплоскостей, являющихся решениями соответствующих неравенств;
· изображается целевой вектор />;
· через допустимое множество проводится перпендикуляр к целевомувектору – это линия уровня целевой функции;
· путем перемещения линии уровня параллельно самой себе внаправлении целевого вектора до тех пор, пока /> неокажется по одну сторону от перемещаемой прямой, визуально определяется точка(или точки) максимума;
· вычисляются координаты точки максимума (решением соответствующейсистемы уравнений, задающих прямые, точка пересечения которых и есть искомаяточка) и максимальное значение целевой функции.
Замечание.Для определения точки минимума следует перемещать изолинию против направленияцелевого вектора.
Вразобранных примерах оптимальный план находился в единственной вершинемногоугольника допустимых планов. Однако при решении задач ЛП могут встретитьсяи другие случаи.
Бесконечноемножество оптимальных планов. На рис.1.4 целевая функция принимаетодно и то же максимальное значение в любой точке отрезка AB,соединяющего две вершины множества планов Х. Такая ситуация возникает,если линии уровня параллельны граничной прямой.
Отсутствиеограниченного решения. На рис.1.5 изображен случай, когда целеваяфункция не ограничена сверху на множестве планов и решение задачи на максимумне существует. При этом решение задачи на минимум может существовать, (как взадаче о витаминах).
Отсутствиедопустимых планов. На рис.1.6 области, допустимые по каждому изограничений, не имеют общих точек. В этом случае говорят, что ограничения несовместны,множество планов пусто и задача ЛП решения не имеет.
/>/> />/> />
Рис. 1.4 Рис.1.5 Рис. 1.6
2. Симплекс-метод 2.1 Идея симплекс-метода
Рассмотримуниверсальный метод решения канонической задачи линейного программирования
/>, />, />,
с n переменными и mограничениями-равенствами, известный как симплекс-метод.
Множествопланов канонической задачи – выпуклое многогранное множество, имеющее конечноечисло угловых точек. И если эта задача имеет оптимальное решение, то онодостигается хотя бы в одной угловой точке.
С любойугловой точкой связан базисный план задачи, в котором /> переменныхравны нулю, а оставшимся переменным соответствуют линейно независимые столбцыматрицы условий />. Эти линейно независимыестолбцы образуют невырожденную базисную матрицу />.
Переборвсех угловых точек сопряжен с большими вычислительными затратами и поэтому неэффективен. В 1947 году Дж. Данциг предложил упорядоченную процедуру перебораугловых точек, при которой для нахождения оптимального решения достаточноисследовать лишь небольшую их часть. Эта процедура называется симплекс-методом.
Дж.Данциг предложил при переходе от одной крайней точки к другой заменять вбазисной матрице всего один вектор. Это означает, что при таком переходе мыдолжны одну из базисных переменных исключить – сделать ее небазисной (равнойнулю), а на ее место ввести новую переменную из числа небазисных (нулевых) –сделать ее базисной (положительной).
Оказывается,геометрически такая замена приводит к переходу от одной угловой точки к смежной(соседней), связанной с предыдущей точкой общим ребром.
Из всехсоседних точек выбирается та, в которой целевая функция возрастает более всего.Поскольку число угловых точек конечно, через конечное число переходов будетнайдена вершина с наибольшим значением целевой функции, либо будет установленанеограниченность целевой функции на неограниченном множестве планов.
Общаясхема симплекс-метода состоит из следующих основных шагов.
· шаг 0. Определение начального базиса /> и соответствующей ему начальной угловойточки (базисного плана) />.
· шаг 1. Проверка текущего базисного плана на оптимальность.Если критерий оптимальности выполнен, топлан оптимален ирешение закончено. Иначе переход на шаг 2.
· шаг 2. Нахождение переменной, вводимой в составбазисных. (Из условия увеличения целевой функции).
· шаг 3. Нахождение переменной, исключаемой из составабазисных переменных (Из условия сохранения ограничений задачи).
· шаг 4. Нахождение координат нового базисного плана(смежной угловой точки). Переход на шаг 1.
Повторяющиесяшаги 1–4 образуют одну итерацию симплекс-метода.
Из этойсхемы следует, что во-первых, для начала работы симплекс-метода надо иметькакую-то угловую точку – начальный базисный план, а во-вторых, надо уметьисследовать текущую угловую точку на оптимальность, не вычисляя всех смежныхвершин. Эти проблемы легко решаются, если каноническая задача ЛП имеет некийспециальный вид.
Определение.Будем говорить, что каноническая задача ЛП имеет «предпочтительныйвид», если
1. правые части уравнений />, />.
2. матрица условий /> содержит единичнуюподматрицу размера />
/>.
Другимисловами, в любом уравнении есть переменная с коэффициентом равным единице,отсутствующая в остальных уравнениях. Первое условие не являетсяобременительным, так как в случае отрицательной правой части некоторогоуравнения, достаточно умножить его на (–1). В задаче предпочтительного виданачальный базисный план находится очень просто.
Пример2.1.
/>
/>
Матрицаусловий A и вектор правых частейограничений b имеют вид
/>, />,
ацелевой вектор с = (1, -3, 0, 4, 2).
Сразу очевиднаодна базисная матрица: /> с единичнымивекторами условий.
Следовательно,выбирая в качестве базисных переменных x1,x3,x5,и полагая в системе уравнений x2 = x4 = 0 (небазисные переменные), немедленнонаходим x1 =10,x3 = 20,x5= 8, так что начальный базисный план x0= (10, 0, 20, 0, 8).Видим, что значения базисных переменных равныправым частям ограничений. Из этого понятнотребование положительности правых частей bi.
Вдальнейшем, базисные переменные будем объединять в вектор xБ.
Такимобразом, в канонической задаче предпочтительного вида в качестве начальнойбазисной матрицы берется единичная подматрица AБ= E, а соответствующие ей базисные переменныеравны правым частям ограничений:
xБ = b.
Длябазисного плана такого вида может быть сформулирован достаточно простой дляпроверки критерий оптимальности. Введем величины
∆j= – cj, j = 1,...,n, (2.1)
где сБ– вектор из коэффициентов целевой функции при базисных переменных xБ, Aj – j-йстолбец матрицы условий, cj – j-й коэффициент целевой функции. Разности ∆jназываются симплексными разностями или симплексными оценками.
Критерийоптимальности базисного плана. Если для базисного плана с единичнойбазисной матрицей все симплексные оценки неотрицательны, то этот планоптимален.
Применимданный критерий для проверки на оптимальность базисного плана x0 = (10, 0, 20, 0, 8) из примера 2.1.
Так какв этом плане вектор базисных переменных xБ=(x1, x3,x5), то сБ = (c1, c3,c5) = (1, 0, 2).
/>.
Следовательно,
∆1= – c1 = 1∙1+ 0∙0 + 2∙0 – 1= 0,
∆2= – c2 = 1∙3+ 0∙1 + 2∙2 – (-3) = 10,
∆3= – c3 = 1∙0+ 0∙1 + 2∙0 – 0= 0,
∆4= – c4 = 1∙(-1)+ 0∙5 + 2∙1 – 4= -3,
∆5= – c5 = 1∙0+ 0∙0 + 2∙1 – 2= 0.
Так какоценка ∆4 x0не оптимален. Заметим, что симплексные оценки, соответствующие базиснымпеременным, всегда равны нулю, так что достаточно проверять только небазисныеоценки. 2.2 Реализация симплекс-метода на примере
Продемонстрируемприменение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП
f(x) = x1+ 2x2+0x3+ 0 x4→max (2.2)
–x1+ 2x2+ x3= 4, (2.3)
3x1+2x2 + x4= 12, (2.4)
xj≥ 0, j = 1,2,3,4. (2.5)
Матрица условий A = (A1, A2,A3, A4), где
/> /> /> />
Целевойвектор c =(c1,c2, c3,c4) = (1, 2, 0, 0); вектор правых частей b=(b1, b2)= (4, 12).
Шаг0. Нахождение начальной угловой точки (базисного плана).
Задача имеетпредпочтительный вид, так как правые части уравнений положительны, а столбцыматрицы условий A3,A4 образуют единичную подматрицу. Значитначальная базисная матрица />= (A3,A4); x3иx4– базисные переменные,x1иx2 — небазисные переменные, cБ= (c3,c4) == (0, 0).
Начальныйбазисный план имеет вид x0= (0, 0, x3, x4)= (0, 0, 4, 12); f(xo)= 0.
Шаг1. Проверка базисного плана на оптимальность.
Подсчитаемсимплексные оценки для небазисных переменных по формуле (5.1)
1= cБ, A1> – c1= 0 ·(–1)+ 0·3 – 1 = –1.
2= cБ, A2> – c2= 0 ·2 + 0 · 2 –2 = –2.
Так какоценки отрицательны, то план x – не оптимален. Будем искать новыйбазисный план (смежную угловую точку) с большим значением целевой функции.
Шаг2. Нахождение переменной вводимой в базис.
Целевуюфункцию можно увеличить, если ввести в состав базисных переменных (сделать положительной)одну из небазисных переменных x1илиx2, поскольку обе оценки jx2.
Шаг3. Определение переменной выводимой из базиса.
Послеввода в базис переменной x2новыйплан будет иметь вид
x' =(0, x2,x3, x4).
Этот планне является базисным, так как он содержит только одну нулевую координату,значит надо сделать нулевой (исключить из базиса) одну из переменных x3илиx4. Подставим координаты плана x' = (0, x2,x3,x4) в ограничения задачи. Получим
2x2+ x3= 4,
2x2 + x4= 12.
Выразимотсюда базисные переменные x3иx4через переменную x2, вводимуюв базис.
x3 = 4 – 2x2, (2.6)
x4 = 12 – 2x2. (2.7)
Такпеременные x3иx4должныбыть неотрицательны, получим систему неравенств
4 – 2x2 ≥0, (2.8)
12 – 2x2 ≥ 0. (2.9)
Чембольше значение x2, тем большевозрастает целевая функция. Найдем максимальное значение новой базиснойпеременной, не нарушающее ограничения задачи, то есть удовлетворяющееусловиям (2.8), (2.9).
Перепишемпоследние неравенства в виде
2x2 ≤ 4,
2x2 ≤ 12,
откудамаксимальное значение x2 = min { 4/2,12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x3иx4, получаем x3 = 0.Следовательно x3 выводится из базиса.
Шаг4. Определение координат нового базисного плана.
Новыйбазисный план (смежная угловая точка) имеет вид
x' = (0, x2, 0,x4)
Базисэтой точки состоит из столбцов A2 и A4, такчто />= (A2,A4).Этот базис не является единичным, так как вектор A2 = (2,2),и следовательно задача (2.2)–(2.5) не имеет предпочтительного видаотносительно нового базиса. Преобразуем условия задачи (2.3), (2.4) такимобразом, чтобы она приняла предпочтительный вид относительно новых базисныхпеременных x2,x4, то естьчтобы переменная x2входила в первое уравнение скоэффициентом, равным единице, и не присутствовала во втором уравнении.Перепишем уравнения задачи
– x1+ 2 x2+x3 = 4, (p1)
3x1 +2 x2+ x4 = 12. (p2)
Поделимпервое уравнение на коэффициент при x2.Получим новоеуравнение />= p1 / 2,эквивалентное исходному
– 1/2 x1+ x2+1/2 x3 = 2. (/>)
Используемэто уравнение, которое назовем разрешающим, для исключения переменной x2из второго уравнения. Для этого надо уравнение /> умножитьна 2 и вычесть из p2. Получим /> = p2– 2/> = p2– p1:
4 x1 – x3+ x4 = 8. (/>)
В итогеполучили новое «предпочтительное» представление исходной задачиотносительно новых базисных переменных x2, x4:
f(x) = x1 + 2 x2+ 0 x3 + 0 x4 max
– 1/2 x1+ x2+ 1/2 x3 =2 (/>)
4 x1– x3+ x4 = 8 (/>)
xj0, j= 1,2,3,4
Подставляясюда представление нового базисного плана x1= (0, x2,0, x4), сразу найдем его координаты, так как значениябазисных переменных равны правым частям уравнений
x' = (0, 2, 0, 8); f(x1)=4.
На этомзавершается первая итерация простого симплекс-метода. Далее процесс решениязадачи продолжается с шага 1, состоящем в проверке найденного плана наоптимальность. Решение заканчивается тогда, когда все симплексные оценкитекущего базисного плана окажутся неотрицательными.
Мы небудем проводить вторую итерацию по схеме первой, поскольку все вычислениясимплекс-метода удобнее проводить в табличном виде. 2.3 Табличная реализация простого симплекс-метода
Табличнуюреализацию продемонстрируем на том же примере (2.2)–(2.5).
Шаг0. Решение начинается с построения начальной симплекс-таблицы. Сначалазаполняется правая часть таблицы с третьей колонки. В двух верхних строкахзаписываются имена переменных задачи (x1,...,x4) и коэффициенты целевой функции при этихпеременных. Ниже записываются коэффициенты уравнений – элементы матрицы условийА, так что под переменной x1располагаетсястолбец A1,под переменной x2– столбецA2и т.д. В правый столбецзаносятся правые части ограничений (числа bi> 0).
Затемнаходим столбцы матрицы условий, образующие единичный базис – в нашем примереэто A3 и A4 – и соответствующие им базисные переменные x3,x4записываем во вторую колонку. Наконец, в первом столбце записываемкоэффициенты целевой функции при базисных переменных.
Таблица1 - Начальная симплекс-таблица
СБ Базисные переменные
с1=1
с2=2
с3=0
с4=0
Значения базисных перем. (xБ=b)
x1
x2
x3
x4
c3=0
x3
a11=-1
a12=2
a13=1
a14=0
b1=4
c4=0
x4
a21=3
a22=2
a23=0
a24=1
b2=12
Строка оценок j
1= -1
2= -2
3= 0
4= 0
f(x)= 0
Так какзадача имеет предпочтительный вид, то значения базисных переменных равны правымчастям уравнений, расположенным в последнем столбце. Поскольку небазисныепеременные равны нулю, то начальный базисный план равен
xo= (0, 0, x3, x4) = (0, 0, 4, 12).
Шаг1. Для проверки плана xoнаоптимальность подсчитаем симплексные оценки для небазисных переменных x1и x2поформуле
j=, Aj > – cj.
1= , A1> – c1= 0 ·(–1)+ 0 ·3 – 1 = –1.
Притабличной реализации для подсчета оценки 1надо найтисумму произведений элементов первого столбца (cБ) насоответствующие элементы столбца A1при небазиснойпеременной x1. Аналогичноподсчитывается оценка 2, как скалярное произведениепервого столбца (cБ) на столбец при переменной x2.
2= cБ, A2> – c2= 0 ·2 + 0 · 2 –2 = –2.
Симплексныеоценки записываются в последней строке симплекс-таблицы, которая называетсядельта-строкой. При этом заполняются не только клетки при небазисныхпеременных, но и базисные клетки. Легко проверить, что для базисных единичныхстолбцов матрицы условий симплексные оценки равны нулю. В последней клеткестроки оценок записываем значение целевой функции в точке xo.Заметим, что, так как небазисные координаты базисного плана равны нулю, топодсчет целевой функции удобно производить по формуле
f(x)=cБ,xБ >,
перемножаяскалярно первый и последний столбцы таблицы.
Так каксреди оценок jестьотрицательные, топлан xo – не оптимальный, и надо найти новый базисный план,заменив одну из базисных переменных на новую из числа небазисных.
Шаг2. Поскольку обе оценки 1и 2x1, x2.Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то естьx2.
Столбецсимплекс-таблицы, в котором находится вводимая в базис переменная называетсяведущим столбцом.
Впримере ведущим будет столбец при x2.
Шаг3. Если в ведущем столбце все элементы отрицательны, то решения задачи несуществует и maxf(x) . В примере всеэлементы ведущего столбца положительны, следовательно, можно найти максимальноезначение x2, при котором одна из старых базисныхпеременных обратится в ноль. Напомним, что максимальное значение x2 = min{4/2, 12/2}=2.
Потаблице это значение вычисляется как наименьшее из отношений компонентбазисного плана (из последнего столбца) к соответствующим положительнымэлементам ведущего столбца.
Наименьшееотношение находится в строке с базисной переменной x3.Значит переменная x3исключаетсяиз состава базисных переменных (x3 =0).
Строка,содержащая переменную, исключаемую из базиса, называется ведущей строкой.
Впримере ведущей строкой будет первая строка.
Элемент,находящийся на пересечение ведущей строки и ведущего столбца, называетсяведущим элементом.
В нашемслучае ведущий элемент a12 = 2.
Табл. 2- Начальная симплекс-таблица с ведущими строкой и столбцом
cБ Базисные перемен.
с1=1
с2=2
с3=0
С4=0 Значения базисных перем. Уравнения
x1
x2
x3
x4
c3=0
x3
–1
2
1
4
p1
c4=0
x4
3
2
1
12
p2
Строка оценок j
1= –1
2= –2
3= 0
4= 0
f(x)= 0
Шаг4. Для получения нового базисного плана приведем задачу к новомупредпочтительному виду относительно новых базисных переменных.
Дляэтого построим новую симплекс-таблицу, во втором столбце которой вместоисключаемой переменной x3 запишемновую базисную переменную x2, а впервом столбце (сБ) вместо с3запишемкоэффициент целевой функции при x2 : c2=2.В новой симплекс таблице столбец при x2 долженстать единичным (ведущий элемент должен равняться единице, а все остальные элементыдолжны обратиться в ноль). Это достигается следующими преобразованиями строктаблицы.
a. Все элементы ведущей строки делим на ведущий элемент и записываем в тойже строке новой симплекс- таблицы.
Полученнуюстроку p1' назовем разрешающей.
b. К оставшейся второй строке прибавим разрешающую строку, умноженную натакое число, чтобы элемент, стоящий в ведущем столбце обратился в ноль.
p2'= p2 + (- 2) p1'= p2 — p1.
c. Заполним последнюю строку, вычислив оценки j' = — — cj, где cБ',Aj' — соответствующие столбцы новой симплекс-таблицы, и значениецелевой функции f(x)= .
Получимвторую симплекс-таблицу с новым базисом.
Таблица3 — Результат первой итерации
cБ' Базисные перемен.
с1=1
с2=2
с3=0
с4=0 Значения базисных перем. Уравнения
x1
x2
x3
x4
c2=2
x2
–1/2
1
1/2
2
p1' =p1/2
c4=0
x4
4
-1
1
8
p2' =p2 — p1
оценки j'
–2
1
f(x')=4
Новыйбазисный план x'= (0, x2, 0,x4) = (0, 2, 0, 8).
Посколькуоценка 1= -2 то план x'не оптимален. Для перехода к новому базисному плану (соседнейугловой точки) проведем еще одну итерацию симплекс — метода.
Таккак 1 то в базис вводитсяпеременная x1. Первый столбец, содержащий x1 — ведущий.
Находимотношения компонент базисного плана к соответствующим положительнымэлементам ведущего столбца и в качестве ведущей строки берем строку снаименьшим отношением. В таблице 2 в ведущем столбце только второй элементбольше нуля (= 4), следовательно, вторая строка будет ведущей, арасположенная в ней базисная переменная x4подлежитисключению из базиса.
Выделяемведущий столбец и ведущую строку и на их пересечении находим ведущий элемент(= 4).
Строимновую (третью) симплекс-таблицу, заменяя в ней базисную переменную x4на x1, и снова преобразуястроки таблицы таким образом, чтобы ведущий элемент стал равным единице, аостальные элементы ведущего столбца обратились в ноль. Для этого ведущую(вторую) строку делим на 4, а к первой строке прибавляем полученную вторуюстроку, деленную на 2. Последнюю строку вычисляем по формулам для симплексныхоценок j''= '', Aj''> — cj, где cБ'', Aj'' — соответствующие столбцы новой симплекс-таблицы. Значение целевойфункции на новом базисном плане находим по формуле f(x'')= '', xБ''>.
Таблица4 — Результат второй итерации
cБ'' Базисн. перемен.
с1=1
с2=2
с3=0
с4=0 Значения базисных перем. уравнения
x1
x2
x3
x4
c2=2
x2
1
3/8
1/8
3
p1''=p1'+p2''/2
c1=1
x1
1
-1/4
1/4
2
p2'' = p2'/4
оценки j''
1/2
1/2
f(x'')= 8
Новыйбазисный план x''= (x1, x2,0, 0) = (2, 3, 0, 0). Поскольку все оценкинеотрицательны, то план x''— оптимальный план.
Такимобразом, x* = (2, 3, 0, 0), f(x*) = 8.
ЗАКЛЮЧЕНИЕ
Рассмотренныеспособы решения задач линейного программирования широко используются напрактике. Однако следует отметить, что математическая модель всегда беднеереальной экономической системы. Она описывает эту систему лишь приблизительно,выделяя одни свойства и пренебрегая другими. Для компенсации указанногонедостатка в математической экономике разрабатывается несколько типов моделей,каждый из которых призван отразить какую-то одну определённую сторонуэкономической действительности с тем, чтобы при решении конкретнойэкономической задачи можно было подобрать такую модель, которая лучше всего кней подходит.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.
2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическоепрограммирование. – М.: Высшая школа, 1980.
3. Калихман И.Л. Линейная алгебра и программирование. – М.: Высшая школа,1967.
4. Нит И.В. Линейное программирование. – М.: Изд-во МГУ, 1978.
5. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечныеметоды. – М.: Физматиз, 1963.
6. Тарасенко Н.В. Математика-2. Линейное программирование: курс лекций. –Иркутск: изд-во БГУЭП, 2003.
7. Математическое программирование в примерах и задачах: Учеб. пособие. –2-е изд., испр. и доп. – М.: Высш. шк., 1993. – 336 с.
8. www.yandex.ru
9. www.mathematica.ru
10. www.monax.ru