Пиши Дома Нужные Работы

Обратная связь

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

Глава 3

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

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

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

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

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

Х{ = W1',^1') и ^2 =(х\2)'х22)) ~ точки плоскости Oxjx2, а X = (хих2) — любая точка отрезка X\Xj (рис. 3.1). Очевидно, что

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

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

" = X® - jr-O = г(2> - г(') '

Л| Л| Лл •Л-')


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

х = а]х}' + а2х\ ', 2 = ахху + а2х\',

(3.3)

(3.4)

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

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

(3.5)

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

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

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


           
 
   
   
 
 

Глава 3

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



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

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

X = а.\Ху + а2Х2+...+апХп,

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

7 = 1

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

/ 111, I Лч

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

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

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

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

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

X = а{Хх + а4Х4, где

а] > 0,а2 > 0, а) + а4 = 1. i

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

Подставив значение Х$ в выражение для X, получим X = ctjA'i + ot4(a2*2 + a3X,) = а^, + а2а4А'2 + a3a4Jf3.


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

Обозначив f, = a|, t2 = a2a4, t3 = a3a4 , получим окончательно

X = txXx + t2X2 + t3X3,

где

/, > 0,/2 s 0,/3 £ 0 и tx + t2 + Ц = 1.

Рис. 3.2

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

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

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

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

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

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



Глава 3


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



 


               
   
   
 
   
 

(3.6) (3.7) (3.8)

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

  АХ = В,
  Х>0,
г«11 «12 •••
«21 «22 •••
v«ff!l «ю2 •••

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

С = (с,,с2,...,с„); А

где

 

«1л ^   >   Г АЛ
«2л ;Х = х2 ; в = bi
атп'   <х„)   т)

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

Векторная форма записи: F = СХ -» max (min) при ограничениях /fa, + Р2х2+...+Р„х„ = Р,

(3.9)

Х>0, (3.11)

^«12Л «22
'«.1Л «21
Р
^m2J
V<W

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

 

V   гь)
«2л , /»« h
v«™^   ybm)

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

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


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

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

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

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

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

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

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

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

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

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

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


 


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


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



Глава 3


 


             
       
 
 
 
 

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

Рис.3.3 X = a^j + а2Х2+. ..+арХр,

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

п

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

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

(3.12)

F(X*) = F(a{Xl+*2X2+...+apXp) =

= alF{Xl) + a2F(X2)+...+apF(Xp). |

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

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

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

У=1

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

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

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


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

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

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

ч

X = a,A,! + a2X2+...+aqXq, ау > 0 (у = \,2,...,q), £ay=l-

М

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

F(X) = F(aiX] + a2X2+.. .+aqXq) = axF(Xx) + a2F(X2)+...

ч ...+aqF(Xq} = a,A/ + a2M+...+aqM = Л/^Гсху = M,

/-1

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

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

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

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

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


       
 
   
 

Глава 3

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

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

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

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

лг2 = (*Р>,42),••-,*!?; о, о,...,0),

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

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

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

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

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

(О (2)

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

Х\ = а1х^)2х<2), О-а^ч-а^2},,

из

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

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

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


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

(0 (2) (О (2)

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

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

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

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

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

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

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

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

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

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

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

/>,(х, + na,)+...+Pw(xm + iiam)+...+Pn(x„ + ца„) = Р. (3.17) Р,(х, - na,)+...+Pm(xffl - цат)+...+Р„(х, - цал) = Р. (3.18)

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



Глава 3


 


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

Х2 =(х1-цсс1, ..., хт-цат;0, 0, ..., 0).

Поскольку Xj: > 0 (/' = 1, 2, ..., я), то можно подобрать ц на­столько малым, что все компоненты решений Х\ и Xi будут неот­рицательными. В результате Х\ и Х2 будут различными допусти­мыми решениями задачи (3.9) — (3.11). При этом, как легко ви­деть, решение -{Х\ + Х2) = (хих2,...,хт; 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, + с2х2 принимает максимальное (или мини­мальное) значение:

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

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

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

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

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

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

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

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

F = схху2х2 =«,, (I) F - с,Х| + с2х2 = а2 (II) F = с,Х| + с2х2 = о3, (Ш)


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

< д3 или а{> а2> аг.

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

X, п

О

Рис. 4.2

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



Глава 4


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



 


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

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

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

3xi

< 21, (IV)

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


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

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

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

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


 


 

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

F=6

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


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

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

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

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


^^^^^^^^^т



Глава 4


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



 


           
 
   
     
 
 


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

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

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

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

б) F = 2х, - Зх2 + 1 -> min
при ограничениях: х, + х2 > 4, (I) • 2х, - х2 :> 1, (II) х, - 2х2 < 1, (III)
х\ >0, х2>0; (IV, V)

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

Решение, а) Геометрическое решение задачи показано на рис. 4.5, а, из которого следует, что линия уровня с максималь­ным уровнем совпадает с граничной линией АВ многоугольника решений ABCD, т.е. с линией х\ + х2 = 8. Следовательно, на всем отрезке АВ линейная функция F «* 3*j + Зхг принимает одно и то же максимальное значение, равное 3(xi + х2) — 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), то она всегда будет пересекать много­угольник решений, следовательно, линейная функция неограни­ченно убывает.

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

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



Глава 4


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



 


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

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

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

УПРАЖНЕНИЯ

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

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

х, + х2 > 4,

-X] + 2 < 2, X] + 2х2 < 10, х, > 0, х2 > 0. х, > 0, х2 > 0.

Х\ + х2 > 2,

-Х| + 2 < 4,

хх + 2х2 < 8,


 

4.6. F = х, + х2 -> max при ограничениях: х, - 4х2 - 4 <, 0, 3xi - х2 £ 0, X! + х2 - 4 £ 0, х, :> 0, х2 > 0. 4.8. F = х, - х2 -> max при ограничениях: -2х\ + Х2 < 2, X! - 2х2 < -8, xi + Х2 < 5, xj > 0, х2 £ 0.

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

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

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

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

4.11. F = -4х, - 2х2 + х3 - х4 -» max при ограничениях: Гх] - х2 + 4х3 - 2х4 = 2, \3х, + 2х2 - х3 + 4х4 = 3, xj > 0, j = 1,2,3,4.

4.12.

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

10х23 + 2х4 + 3х5 = 25, х,;>0Л = 1,2,...,5.


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



 


           
 
   
 
   
 


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






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2017 pdnr.ru Все права принадлежат авторам размещенных материалов.