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

Глава 3

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Выпуклые множества в л-мерном пространстве

В разд. 2.2 выпуклое множество точек определялось как мно­жество, которое вместе с любыми своими двумя точками содер­жит весь отрезок, их соединяющий. Однако в случае я перемен­ных не ясно, что следует понимать под "отрезком" в «-мерном пространстве. Очевидно, надо дать аналитическое определение этого понятия.

Начнем с п = 2 (двумерного пространства, плоскости). Пусть

Х_{ = W¹',^¹') ^и ^2 ⁼(^х\²⁾'^х2²⁾) ~ ^точки плоскости Oxjx₂, а X = (х_их₂) — любая точка отрезка X\Xj (рис. 3.1). Очевидно, что

отношение а длин отрезков XXi и Х\Х^ удовлетворяет условию О <, а < 1. Запишем это отношение а через координаты точек. Получим

Л] ~"' Л] Л'у Л1

" ⁼ X® - jr-O ⁼ г(²> - г(') '

Л| Л| Лл •Л-')

Полагая сц = а и а₂ = 1 - а, условия (3.1), (3.2) примут вид

(3.3)

(3.4)

aj > 0, а₂ > 0, а) + а₂ = 1.

Равенство (3.3) можно записать в виде X = а.\Х{ + а₂Х₂,

(3.5)

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

Таким образом, отрезок X\Xi можно определить как множество точек (векторов), удовлетворяющих условиям (3.5) и (3.4).

В случае «-мерного пространства определение отрезка будет таким же — множество точек, удовлетворяющих условиям (3.5) и

Глава 3

(3.4), если под Х\ и Х₂ подразумевать точки (векторы) и-мерного пространства: Х_х = (х\^[) ,х^{₂^]) ,...,х^) и Х_г = (х\²Кх^,...,х^)-

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

Тонка X называется выпуклой линейной комбинациейточек Х\, Хь ..., Х_п, если выполняются условия

X = а.\Ху + а₂Х₂+...+а_пХ_п,

а,-> О U = 1,2,...,«), £а_; = 1.

7 = 1

Так, например, выражение (1/6)^ + {\/2)Х₂ + (1/3)Лз есть вы­пуклая линейная комбинация точек Х\, Х₂, Xj, а выражения (1/3)*, + (\/2)Х₂ + (1/3)Лз или (1/3)^1 - (\/2)Х₂ + (7/6)JT₃ явля­ются линейными, но не выпуклыми комбинациями тех же точек

/ 111, I _Лч

(в первом — + — + — *1,аво втором а₂ = -— < 0).

Очевидно, что в частном случае при и = 2 выпуклой линейной комбинацией двух точек является соединяющий их отрезок. По­этому множество точек является выпуклым,если оно вместе с лю­быми своими двумя точками содержит их произвольную выпуклую линейную комбинацию.

Рассмотрим теорему о представлении выпуклого многогран­ника.

Теорема 3.1.Выпуклый n-мерный многогранник является выпук­лой линейной комбинацией своих угловых точек.

П Возьмем для простоты п — 2, а в качестве многогранника — треугольник Х\Х₂Х$ (рис.3.2). Через произвольную точку X тре­угольника проведем отрезок Х\Х$. Поскольку точка X лежит на этом отрезке, то

X = а_{Х_х + а₄Х₄, где

а] > 0,а₂ > 0, а) + а₄ = 1. i

Точка Xi лежит на отрезке Х₂Х^, следовательно, Х₄ = а₂Х₂ + а₃Х₃, где а₂ > 0,а₃ > 0, а₂ + а₃ = 1.

Подставив значение Х$ в выражение для X, получим X = ctjA'i + ot₄(a₂*₂ + a₃X,) = а^, + а₂а₄А'₂ + a₃a₄Jf₃.

Основы методов линейного программирования___________ ________ 47

Обозначив f, = a|, t₂ = a₂a₄, t₃ = a₃a₄ , получим окончательно

X = t_xX_x + t₂X₂ + t₃X₃,

где

/, > 0,/₂ s 0,/₃ £ 0 и t_x + t₂ + Ц = 1.

Рис. 3.2

Таким образом точка X есть выпуклая линейная комбинация уг­ловых точек (вершин) треугольника ХуХ₂Ху Ш

Из теоремы 3.1 следует, что выпуклый многогранник порожда­ется своими угловыми точками или вершинами: отрезок — двумя точками, треугольник — тремя, тетраэдр — четырьмя точками и т.д. В то же время выпуклая многогранная область, являясь неог­раниченным множеством, не определяется однозначно своими угловыми точками: любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.

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

В разд. 1.3 были рассмотрены различные формы задачи линей­ного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей, кано­нической или стандартной задачи.

В данном разделе будем рассматривать каноническую задачу (1.20) — (1.22), в которой система ограничений есть система урав­нений (2.1).

Для обоснования свойств задачи линейного программирования и методов ее решения целесообразно рассмотреть еще два вида записи канонической задачи.

Глава 3

_овы методов линейного программирования

Матричная форма записи:

F = СХ -> max (min) при ограничениях

где

Здесь С — матрица-строка, А — матрица системы, X — матри­ца-столбец переменных, В — матрица-столбец свободных членов.

(3.9)

Х>0, (3.11)

где CJ — скалярное произведение векторов¹ С = (q, q, ..., с„) и Z= (xj, X2, ..., х_я), векторы

состоят соответственно из коэффициентов при переменных и свободных членов.

Векторное неравенство X > О означает, что все компоненты вектора ^неотрицательны, т.е. х_у- > 0, у = 1,2,...,л.

В гл. 2 была сформулирована, но не доказана в общем виде следующая теорема.

Теорема 3.2.Множество всех допустимых решений системы ог­раничений задачи линейного программирования является выпуклым.

□ Пусть Х_х =(х,^(,),х<¹⁾,...,х1^,)) и Х_г = (х(²⁾,х<²>,...,хР) - два допустимых решения задачи (3.6) — (3.8), заданной в матричной форме. Тогда АХ\ = В и АХ₂ = В. Рассмотрим выпуклую линейную комбинацию решений Х\ и Х₂, т.е.

X = щХ\ + а₂Х₂ при оц > 0,а₂ > 0 и а) + а₂ = 1,

и покажем, что она также является допустимым решением систе­мы (3.7). В самом деле АХ = А(щХ_{ + а₂Х₂) = а₁АХ₁ + (1 - а₁)АХ₂ = а_{В + (1 - а^В = В,

т.е. решение X удовлетворяет системе (3.7). Но так как Х_х >0, Х₂ sO, оц > О, a₂ ^ 0, то и X >0, т.е. решение Z удовлетворяет и

условию (3.8).И

Итак, доказано, что множество всех допустимых решений задачи линейного программирования является выпуклым, а точнее (если учесть изложенное в гл. 2), представляет выпуклый многогранник или выпуклую многогранную область, которые в дальнейшем будем называть одним термином — многогранником решений.

Ответ на вопрос, в какой точке многогранника решений воз­можно оптимальное решение задачи линейного программирова­ния, дается в следующей фундаментальной теореме.

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

П Будем полагать, что многогранник решений является огра­ниченным. Обозначим его угловые точки через Х\, Х₂, ..., Х_р, а

¹ Скалярным произведением СХ двух векторов С = (с_ь с₂, ..., с„) и X = = (лг,, х₂, ..., х_п) называется число, равное сумме произведений соответст­вующих координат этих векторов: СХ = С|Х, + с₂х₂ + ... + с„х„.

¹ Формулировка теоремы остается такой же и при отыскании мини­мального значения линейной функции.

Глава 3

оптимальное решение — через X* (рис.3.3). Тогда FyX* j > F(X) для всех то­чек X многогранника реше­ний. Если X* — угловая точка, то первая часть тео­ремы доказана.

Предположим, что Л" не является угловой точкой, тогда на основании теоре­мы 3.1 X* можно предста­вить как выпуклую линей­ную комбинацию угловых точек многогранника ре­шений, т.е.

п

a_y SO, j = 1,2,. ..,/>; ]£a_y = 1.

Так как F(X) — линейная функция, получаем

F(X*) = F(a_{X_l+*₂X₂₊...₊a_pX_p) =

= a_lF{X_l) ₊ a₂F(X₂)₊...₊a_pF(X_p). |

В этом разложении среди значений F(XJ) (/ = 1,2, ..., р) выбе­рем максимальное. Пусть оно соответствует угловой точке Х_к (1 <: к < р); обозначим его через М, т.е. F{X_k) = М. Заменим в

выражении (3.12) каждое значение этим максимальным значени-

р ем Л/. Тогда, учитывая, что а_у ^ 0, У]осу = 1, найдем fIx*)<

У=1

< щМ +а₂М+...+а_рМ = Л/Vay = М. По предположению Л* —

У=1оптимальное решение, поэтому, с одной стороны,

F(XjiF(X_k) = M, но, с другой стороны, доказано, что F(X j <, М, следовательно, F\X*\ = М = F{X_k), где Х_к— угловая

точка. Итак, существует угловая точка Х_к, в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что F(X) принимает максимальное значение более чем в одной угловой точке, например, в точках Х\, Х₂, ..., X_q. где \s,q<,p; тогда F(X_{)=F{X₂)=...= F(X_q) = M.

Пусть X — выпуклая линейная комбинация этих угловых то­чек, т.е.

ч

X = a,A^,_! + a₂X₂+...+a_qX_q, а_у > 0 (у = \,2,...,q), £^ay=l-

М

В этом случае, учитывая, что функция F{X) — линейная, полу­чим

F(X) = F(a_iX_] + a₂X₂+.. .+a_qX_q) = a_xF(X_x) + a₂F(X₂)+...

ч ...+a_qF(X_q} = a,A/ + a₂M+...+a_qM = Л/^Гсху = M,

/-1

т.е. линейная функция F принимает максимальное значение в произвольной точке X, являющейся выпуклой линейной комби­нацией угловых точек Х\, Х₂, ..., Х_д.Ш

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

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

Следующая теорема посвящена аналитическому методу нахож­дения угловых точек.

Теорема 3.4.Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка много-

Глава 3

гранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

О Пусть X = (х,, х₂, ..., х_т; 0, 0, ..., 0) — допустимое базисное решение системы ограничений (3.10) задачи, в котором первые т компонент — основные переменные, а остальные п — т компо­нент — неосновные переменные, равные нулю в базисном реше­нии (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что X — угловая точка многогранника решений.

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

*,=(xjVW,...,_x(0; о, 0,...,0)и

лг₂ = (*Р>,4²⁾,••-,*!?; о, о,...,0),

другими словами, — выпуклой линейной комбинацией точек ЯГ, и Х₂ многогранника решений, т.е.

X = а, ЯГ, + а₂Х₂, (3.13)

где ot| > 0, а₂ > 0, а, + а₂ = 1 (полагаем, что а, * 0, а₂ *■ 0, ибо в

противном случае точка ЯГ совпадает с точкой Х\ или Я^).

Запишем векторное равенство (3.13) в координатной форме:

(О (2)

I = а,*}' + а₂х\ ',

Х\ = а₁х^⁾+а₂х<²⁾, О-а^ч-а^²},,

из

0 = а,4^!)+а₂х1²>.Поскольку ху 2: 0, я)²) > 0 (j = 1,2,...,л), а, > 0, а₂ > 0, то последних п-т равенств следует, что ху₊₁ = 0, ху₊₁ =0, ...,

ху = 0, ху = 0, т.е. в решениях ЯГ,, Х₂ и X системы уравнений

(3.10) значения п—т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют зна-

Основы методов линейного программирования 53

(0 (²) (О (2)

чения основных, следовательно, х\ > = х\ ' = х,, ..., ху = ху = х₂.

Таким образом, все п компонент в решениях X, ЯГ, и Х₂ совпада­ют и значит, точки ЯГ, и Х₂ сливаются, что противоречит допуще­нию. Следовательно, X — угловая точка многогранника решений. Докажем обратное утверждение. Пусть X = (х,, х₂, ..., х_т; 0, 0, 0) _ угловая точка многогранника решений и первые ее т координат положительны. Покажем, что X — допустимое базис­ное решение.

Если векторы Р\, Рг, ■-, Р_т линейно независимы¹, то ранг г матрицы А, составленной из компонент этих векторов, равен т, т.е. определитель \А\ * 0, следовательно, переменные х,, х₂, ..., х_т

являются основными, и решение X = (х,, х₂, ..., х_ш; 0, 0, ..., 0) — базисное, допустимое, т.е. утверждение доказано.

Предположим противное, т.е. векторы Р\, Р₂, ..., Р_т линейно зависимы; тогда в равенстве

а_хР\+...+а_тР_т+...+а„Р_п =0 (3.14)

хотя бы один из коэффициентов а,,..., а_т,..., а„ отличен от нуля. Умножим почленно равенство (3.14) на множитель ц > 0:

\ю._хР\+...+\ю._тР_т+...+[1а._пР_п =0. (3.15)

Подставив координаты угловой точки ЯГ многогранника реше­ний в систему ограничений (3.10), получим

Р,х_]+...+Р_тх_т+...₊Р_пх„ = Р. (3.16)

Равенство (3.15) почленно сложим с равенством (3.16), а затем вычтем его из равенства (3.16). Получим

/>,(х, + na,)+...+P_w(x_m + iia_m)+...+P_n(x„ + ца„) = Р. (3.17) Р,(х, - na,)+...+P_m(x_ffl - ца_т)+...+Р„(х, - ца_л) = Р. (3.18)

¹ Векторы />,, Р₂, ..., Р„ (они же столбцы матрицы А) называются ли­нейно зависимыми, если можно подобрать такие числа a,,a₂,.-,a„, не равные нулю одновременно, что а,/*, + а₂Р₂+...+а„Р„ =0, где 0 — нулевой вектор (состоящий из нулей). В противном случае векторы Л. Р₂, .., Р„ называются линейно независимыми.

Глава 3

 

Сравнивая полученные равенства (3.17), (3.18) с равенством (3.16), заключаем, что при любом ц системе ограничений (3.10) удовлетворяют решения Х_х = (jjq + (ia_b ..., х_т + \х.а_т; 0, 0, ..., 0) и

Х₂ =(х₁-цсс₁, ..., х_т-ца_т;0, 0, ..., 0).

Поскольку Xj_: > 0 (/' = 1, 2, ..., я), то можно подобрать ц на­столько малым, что все компоненты решений Х\ и Xi будут неот­рицательными. В результате Х\ и Х₂ будут различными допусти­мыми решениями задачи (3.9) — (3.11). При этом, как легко ви­деть, решение -{Х\ + Х₂) = (х_их₂,...,х_т; 0, 0, ..., 0) = X, т.е. точ­ка X лежит на отрезке (в данном случае в его середине), располо­женном в многограннике решений. Значит X не является угловой точкой, что противоречит условию. Следовательно, наше допуще­ние неверно, т.е. векторы Р\, Pi, ..., Р_т линейно независимы и X— допустимое базисное решение задачи (3.9) — (З.Н).И

Из теорем 3.3 и 3.4 непосредственно вытекает важное следст­вие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допусти­мых базисных решений.

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

Глава 4

ГЕОМЕТРИЧЕСКИЙ МЕТОД

РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Рассмотрим задачу в стандартной форме (1.4)—(1.6) с двумя переменными (я = 2). К такой форме может быть сведена и кано­ническая задача (с ограничениями в виде уравнений), когда число переменных я больше числа уравнений т на 2, т.е. я — т — 2.

Глава 4

геометрический метод решения задач

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 4.1). Необходимо среди то­чек этого многоугольника найти такую точку, в которой линейная функция F = CjX, + с₂х₂ принимает максимальное (или мини­мальное) значение:

Рассмотрим так называемую линию уровня линейной функции F, т.е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение а, т.е. F = а, или

с,х, + с₂х₂ = а. (4.1)

Линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии — так называемые изо­термы есть не что иное, как линии -уровня температуры Т = с. Еще более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

Предположим, надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имею­щая наибольшую широту, т.е. точка, через которую проходит па­раллель (линия уровня) с самой большой широтой (уровнем).

Именно так и надо поступать при геометрическом решении задач линейного программирования. На многоугольнике решений следует найти точку, через которую проходит линия уровня функ­ции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии уровня функции (4.1) есть уравнение прямой линии. При различных уровнях а линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением меж­ду коэффициентами с\ и с₂ и, следовательно, равны. Таким образом, линии уровня функции F — это своеобразные "параллели", распо­ложенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня

F = с_хх_у+с₂х₂ =«,, (I) F - с,Х| + с₂х₂ = а₂ (II) F = с,Х| + с₂х₂ = о₃, (Ш)

чем _линия II заключена между линиями I и III. Тогда а_х < а₂ <

< д₃ или а_{> а₂> а_г.

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

X, п

О

Рис. 4.2

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на которой из них уровень больше. Например, одну из линий можно взять прохо­дящей через начало координат (если линейная функция имеет вид F = с,*, + с₂х₂, т.е. без свободного члена, то это соответст­вует нулевому уровню). Другую линию можно провести произ­вольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее, определив направление возрастания линейной функции (обозначим его вектором q), найдем точку, в которой функция принимает максимальное или минимальное значение, подобно тому как на карте нахо­дится самая северная или самая южная точка (на рис. 4.1 — это точка С или А).

Глава 4

Геометрический метод решения задач

fr 4.1. Решить геометрически 1-ю задачу из разд. 1.2:

F = 2х, + Зх₂ -> max при ограничениях:

х,+3х₂ < 18,(1) 2х, +х₂ < 16, (II) х₂ 5 5, (III)

< 21, (IV)

х,>0, х₂>0. (V,VI)

т.е. координаты точки С определяются решением системы урав­нений i ' ² ~ ,,' откуда xi = 6, х₂ = 4, т.е. С(6;4). [2х_х + Х₂ = 16,

Максимум (максимальное значение) линейной функции равен ^ш« = 2- 6 + 3-4 = 24.

Итак, /"_тах = 24 при оптимальном решении X! = 6, х₂ = 4, т.е. максимальная прибыль в 24 руб.¹ может быть достигнута при производстве 6 единиц продукции Р\ и 4 единиц продукции Рг-^ > 4.2. Решить геометрически 2-ю задачу из разд. 1.2:

F = 4х, + 6х₂ -> min

F=6

Решение. Изобразим многоугольник решений (аналогично тому, как в задаче 2.5) на рис. 4.3. Очевидно, что при F= О линия уровня 2xi + 3^2 = 0 проходит через начало координат (строить ее не обязательно). Зададим, например, F = 6 и построим линию уровня 2x_t + Зх₂ = 6. Ее расположение указывает на направление возрастания линейной функции (вектор q ). Так как рассматривае­мая задача — на отыскание максимума, то оптимальное решение — в угловой точке С, находящейся на пересечении прямых I и II,

Зх, + х₂ ;> 9, (I) ■ х, + 2х₂ > 8, (II) х, + 6х₂ > 12, (III)

Х!>0, х₂>0. (IV, V)

Решение. Многоугольник решений представляет собой неог­раниченную многоугольную область (рис. 4.4). По расположению

Напоминаем, что в задаче все цифры условные.

^^^^^^^^^_т

Глава 4

Геометрический метод решения задач

линии уровня, например, F= 12 или 4х) + 6х₂ ⁼ 12, находим на­правление вектора q (этот вектор указывает на направление воз­растания линейной функции). Очевидно, что точка минимума — это точка В "входа" в многоугольник решений, ибо при дальней­шем перемещении линии уровня в направлении вектора q значе­ния линейной функции увеличиваются.

Находим координаты точки В (2;3), при этом F_min - 4 ■ 2 + +6 • 3 = 26.

Итак, F_mm = 26 при оптимальном решении х\ = 2, х₂ = 3, т.е. минимальная стоимость рациона 26 руб., если в него включить 2 единицы корма I и 3 единицы корма II. ►

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

^ 4.3. Решить геометрически следующие задачи: a) F = 3jC] + Зх₂ -> max при ограничениях: х, + х₂ < 8, (I) 2jc, - х₂ > 1, (II) х, - 2х₂ ^ 2, (III)х,*0, х₂*0; (IV, V)

Решение, а) Геометрическое решение задачи показано на рис. 4.5, а, из которого следует, что линия уровня с максималь­ным уровнем совпадает с граничной линией АВ многоугольника решений ABCD, т.е. с линией х\ + х₂ = 8. Следовательно, на всем отрезке АВ линейная функция F «* 3*j + Зхг принимает одно и то же максимальное значение, равное 3(xi + х₂) — 3 • 8 = 24. Это означает, что задача имеет бесконечно много оптимальных реше­ний (их задают координаты точек отрезка АВ), среди которых базисных оптимальных решений два — соответственно в угловых точках ДЗ; 5) и В(6; 2). Точки отрезка АВ задаются уравнением Х2 = 8 — X], где 3 < х, <, 6.

Рис.4.5

Итак, /"max = 24 при бесконечном множестве оптимальных ре­шений xj = с, Х2 = 8 — с, где 3 й с < 6.

Замечание.При геометрическом решении подобных за­дач важно точно установить, действительно ли совпадает линия уровня с границей многоугольника решений или это связано с неточностью построений, мелким масштабом рисунка и т.п. Ответ на этот вопрос будет положительным, если линия уровня и граничная прямая параллельны, т.е. их коэффициенты при переменных пропорциональны. В рассматриваемом примере коэффициенты при переменных линии уровня / = 3xj + 3x2 пропорциональны соответствующим коэффициентам гранич­ной ПРЯМОЙ Х[ + Х2=6.

б) Геометрическое решение задачи показано на рис. 4.5, б, из которого следует, что если линию уровня перемещать в направле­нии убывания линейной функции (т.е. в направлении, противо­положном вектору q), то она всегда будет пересекать много­угольник решений, следовательно, линейная функция неограни­ченно убывает.

Итак, конечного оптимума линейной функции нет¹, т.е.

¹ Если задачу с той же линейной функцией и с той же системой ог­раничений решать на максимум (F -> max), то линию уровня следует перемещать в направлении возрастания F (т.е. в направлении вектора q ), и в этой задаче отсутствует конечный оптимум (см. рис.4.5, a): F_maK = оо.

Глава 4

Геометрический метод решения задач

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

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

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

УПРАЖНЕНИЯ

Задачи 4.4—4.10решить геометрически.
4.4. F = 2x_i - 6х₂ -» max 4.5. F = 2х, - х₂ -> min

при ограничениях: при ограничениях:

х, + х₂ > 4,

Х\ + х₂ > 2,

-Х| + 2х₂ < 4,

х_х + 2х₂ < 8,

4.7. F = 2х, - х₂ -> min при ограничениях: х, + х₂ > 4, 2x_t - х₂ £ 2, -х, - 2х₂ -2. -10, х, 2: 0, х₂ > 0.

4.9. Текст условия приведен в
задаче 1.4.

4.10.Текст условия приведен в
задаче 1.5.

Задачи 4.11, 4.12решить геометрически, предварительно при­ведя их к стандартной форме.

4.12.

F = х, + 2х₂ + х₃ - х₄ - 6 -> min
при ограничениях:
-х, + 5х₂ + х₃ + х₄ + х₅ = 10,
2х, - х₂ + х₃ - Зх₄ = 6,

10х₂+х₃ + 2х₄ + 3х₅ = 25, х,;>0Л = 1,2,...,5.

Симплексный метод

Глава 5 СИМПЛЕКСНЫЙ МЕТОД