View of On bilinear programming

.

MÀîrÎÈ*rerlcÀ

_

_äÉvûË D|Á.NALYSE NUIÍÉRIQUE

El

DE'r'HÉoRrE DE rr'AppRoxurrÀTroN

I,'ANALYSII NUIIEIIIQUB BT LA THÉORIE DIì

L'APPROXIMA1.ION

¡,r¡ii;:i:, f6¡¡10 7j'Nd;:1ì,

l}/fir 'pp;,67-79

^,

. .. îhe

^general

bilinea¡ prçrprqmilg problern can be formulated

as Tollows:

(1)

maximize

{/(x,

V)

:

ex

+

^dy

f

^x?'Cy}

,:,

subject

to linear

constrants

I t

Ì ,,, i

,whe're'A,

B,

C âre

i x m, s x lt, tn x

^n,

-'luatriccs

resPectivelli

and

a,

ll, c, d, x, y

are vectors

of the

appropriatc clirnellsioll

.

^-

, Bilinear ,programming

is a

generalizatiou

of the li'ear

prograrnmiug rrrat lor the

first

time was formu.lated

in

1968

by

.+.r.,r.,rrlN,

rr. il]. ^He

^gavé

àr

programming rvhich

ihttr gar;" .

e local optimnm

itr a firiite

number remarked

that.

oire

of the

Altman's

ïor

the

optimality

^and. not necessary.

his criterion'and

corrstructs

a finite

he bilinear programrning.

.t' ,Arr,interesting and

comprehensive strrd.y

on bilinear

prograrnrrring rs'also doue

in _tg]-bv

v,r¡iD.,\i, ,\.

I

ON BILÏNEAR PROGRAMMING

blems.

is

nsecl

to

establish sim- maxl-

plogfammlug

pro a local and global

l! .

'

^\

^{,' :.}

^:\.

il.r by

r.

MARU9CTAC

I

^I 1clu5-Napoca¡

1.

Introduction

'Ax:4, x>0

^,

Ry : lt, y2

o, (2)

i''

(3)

i,,, ,l,If ^{i $'ìe} consider: t'he simplex

tablêau

^i,i

ilii ,,i;

ttit .,,,, it lr, t' ,i iL; . , , -] t.r li. rr..,';,,, 1

tlren

afler a

Jordan elimination step ^r,r'e get

the

tableau

i,

x jt'

^.

,uþ

,

.'lu

¹

trhere C',

b', d', [i',

à' are formed.

by

the eliments girreu

in

(7) and.

B'

is the

if 'the pivot

elemeilt,is,an'elenrreúL

of tlie:uråitrix

R li, /t) .r:i': : :ìl ^rri , ',ì i ,:, ,' : .'.'J Ì.ì i l:llÌiiri, , ,,i, e,,= C.f $ti i ', . i:, ^, i, ,¡ \\,^¡;, ^I

0:

e

0d,

0, R:

0

q.

p b a

OÇ¡

ON BILINBAR PNOERÀITUI¡¡C 69

f:

elirni-

c/"

Ít

0 (ì

0 (8)

ch ^o11e

Ð' 0

(:

þ' B'

d'

AO

xJt

rl--j.

rvhl daTI

ic:

iltddåtio¡sø|, rule

::t: :.' ,i

, ,1,,,1i,. ,

i

L -1i

U:+i

¡í

'Ll's

-

¡tIL I,

Now r,ve shall specify

the

characteristics

of a

_Jordan

eliminalion

^ste¡:

ln a bilineai

programming.

Thus,

let us

consider

(4) ,f(x, ^y) :ä,p,*

^ø

f _äu,ro+

^P

⁺ _Ðå

^{c¡¡.ï¡!¡,}

,t i. ' .1, ^i_

(6)

^,Lt,h

:Db¡¡!¡

_{1. þn,,} h

=.1,2,

^{. .}

.,

^s,

!:t

and let

^bþq

+

^{O be}

the pivot

elêiten't,'

tfiLoiafter

substituting

, ;;,, ,i yo:'Ïl_,Ðijri,+ìo_ao)''

^:

oþc

\

i+c

lr.l ¡ ,,i, ,. : ,t

^{,1i1.,, rrr,}

in

(4), we obtan

11¡

t '"t|: :" ir i1':

.f (x,

yi

") - _Ð ^{c{ct lD* ai*}

^{-,i d'ot¿o*P'}

^{+'Ð ,,} (Ðci¡t¡ -f

^cisap

I

^Bi)

-

iÍ

1

(5)

2

fr

(7) 6t¡

z¡,=tfiUi¡*)'#

^{øn:,' :ft1!'} l', 2,i .t.i,'t r,

rryhere,,,

i:

L,1,; r

':" ¡:i:

'. ,;r; f i:i

, fi7,''':;t

_'

lri :,i

.f i. :,

..,,,?0r,

,

' l íi(,.'

.r, ii

ⁱ

r,i l, li¡i r ii',,

'

' ifii¡l.i\t ir t.'.í',: ':

^í

pfqgtflmmlng

:t'4 t

! iÍ.i,t a\ii'il

¡

!' i '.,til ì:,;i' :iì

^!'

Ê,

Jorrl4g ell¡nhntiop. ;iu

r r, t, i

I'j

i _{,r l}

: ii

li 1,.'(.i,: .i ,

'ii)

:6 ^oN BILINIAR:P\QGRAMMINö 7t

îo

^obtain a b.f.s. we shall use

t

^ation stepsl deçcribed ut th-":sectiã" ^Z.

io

^simplify

^the uo ^{that A}

^an¿

^{B are}

^of

the full rank. ï'hen ^startinþ from

.

^,

' t.,,' \, I,r i. ¡l .\\);":! r,r'i l

and assuming (witùòut loss of

geierality) that

^the

pivot

from

the

ffust

r

and s column of

A

^ancl B respectìvely,

,

(Jordan elimination steps) we get

the tablepu i

^'

,\^0, ^{*i1* Þ} -À;,,1tli ^{+ Q'+} nì,,ä,

^cl¡

^x¡!¡'

a b

-c

- ^%r!1

f:

(1 1)

P

li1

a

0

rl 0

a1

1,11,

ol

tlteø 'P_local

/:.1 I

-v

0

b.f

.s.

(xo,

yo),

^ahere

bil,ine øù _{þro gr} anr'núng

P lQ

^and

-!,

¹

1

i¡i i ^'

of

^tk:e

!,{(xo,

^xo)

>0,

xs&

Proof.

From

(11)

it is

seen tha (b"

Lemma ^1. If

1ì

:

(¿1,

0),

yo

.f(x, ^y)

-(3)

a1

xr- jt:

(10)

"ili¡i.

,'ì¡ ":l 1 ^{í' li î-}

t.:'i

^{¿ ¡}

,,i ,lì.:,lt

rl--

0.

'':l

elements were taken

ihenafterrfsJ.s.

,',1 i\til",l',-. '' ' "'

70

^r.

MARuscrAc

⁴

Remark 1.

lf

^we

^{take a pivot}

element,in ,the rm.atrix

A

then,itrStead

of tableau (8)

rve consider

the

tableau

'xyl

and after

a

Jordan elimination ^step

with pivot

^{elemetrt a'¡o}

*

^{0 u'e}

^get

^the

tableaU - , ¡,i. : :i:

iir

, i:,.ír',,l ,ir'.

,i''r'

XL,,.Zþ'..frr, Y

¹

; , ,.,,;, i,i t, t.t:l

3. Optinrality

^e

. r i . .. ", : ⁱ

A ^pair (r, y) ₌ R'x ^{R" is}

^called

ba

^1e- soltrtig¡1

of the bili- ,r""r ptägtr*tiriä'g (l) -

^(g)

^{if x}

^and

^y arc

siblc soltrtion

of

(2) aud

l3l

respectivelv.

'-'

^-T-h'. tottowing theorem results immediatqly,

,from

thc: theory,of ^ilinear

cr0

0d,

A

0

Í:

r_

a'

d

0 0 H c

0 0 B

0 (,"r

'; ^1/'

A'

(ì

fensible (see

fll)

r. If

^(x

(1)-(3),

^þrogrønl'

bil,inea.r tlt'c

"f

rra o trul'í'on' so aslc

b d.:

oþtíutal'

s an' ,S tkere'.

y*

tken

trk

problenc TIIEOREI,I programming ilØng

Now the

additional

rule

consists itr

.t L-

ll:

ri ¡l ¡ 't ".1

. j .

^tl1

:df T'.,

,,ì

and

so/(xd,,yr) ;-,/(¡0, ^yo)< 0

f.ot

x,)O, li > 0 sufficièntly small,

im- plies.

(i)-(íi)'

^¡

'' "'Ñow,'let

_1xo,

_{yo) be} ä

degerrerate ^b.f

.s.

x0

:

(aI, 0), 'yo

:

(b1, 0), arrd

let us d,enote

^':

" Io: {i

^æt{1,z,

...,/}Io} :o}

THËoR-rM

3.

Degeneløte,bl,s' 1xt,

P) ^is

ø local møx'imuttt

of f ^on

^A

df

øød"'o'¡úy'

åf

',

,

^{, I}

(i) p> 0, q ) 0',, , ,,Ì

t' _'P*oÍ..' (J) If ^'(*9,

yo)

is a

b.f.s.

thät is a locâl

mqximunl, then

"f(x, v) -.f(xo,y9 ^<

^o

in a certain

neighborhood

of

(xo, yo). Considering

xi:

^(n.,

0, ..,,

fri,

,..,0), xr- t> ^0, i e I,

we have

As/(xr,

yo)

-,f(xo, ^{yo)< 0,} it follorvs

that

þn>0,i e

^io,

i... p>

^O

Since

for *' î ^X it is

necessary

that

YheI,¡+øju<0

sirnilarlv we

get

,'To""!

r, i

^{bloo 0,}

j

æ

J.

.

, _{' From}

₍₁₄₎

it is

seen

that

' .f(xt,y,) -.,/(xo, ^yo)<

⁰ ,/(xt, ^yu) --.f ^{(xo, yo)}

:

ON SILINEAR. PROGRAMMING v3

tl

I

I

(i)-(ü)

_botd

0, ielo -þ¡t, i ê

^Io

!;, t, , ] ll',ir;l

rri, _' i,(ä)¿ .¿li

,( 0,

^Y(,i',t

^{j) .e:}

^Ion

X Jl; :

^{, :}

wherc

Ð Ð cl¡'x,'!i" Ð

^P;

^x, - Ð'qi !¡ ¿

:¡*l j-s*l i-t*l j*s+¡

,f(t, ^y) _-,/(xo,

^{yo) <}

i0,

, íri ^,

for

each

xrÞ

^0,

i: r |-1, ..., nt,

^anó.

!¡

^Þ',0,

i :

^s

-l

^7,

'.., n, ^saffí'

ciently

small,

i.e,

(x0, yo)

is

a local:rnaximum

for /in O: ^X x ^Y

^where,

'X:{x eRnlAx:,a, x>0J,Y={i eR'llfy:b, ^y>0}'

THEoRE;v-

2. Lat

_{1xn; Vo),} xo

:

(at,

0),

^yn

:

(b1,

0)

l:e

I

naxd'cgemeratc

b.f.s.then ^(xo,.yo) 1salo9øI 1!x!.xi'Ìn!,t::of,f

?l,,ni!ryao(?,,,iÍ, ,,:,::,,i,r,,r,.

(i) p70,q>0., | ;,,i;,:.r,

^I

(ä) ,,i'< 0,

V(i,

j)æ Io x Jo, i :

" ; _{'il '} :;' ll wherc,¡,¡

I = {r+

^{1, .}

^..,

^tn},

/ - ^{t +

^1,

^...,n}

Io:

_{d

* Ilþ,,= 0}, Ju:

^{.J

^{u Jlq¡} *

_0}.

Proof. (e). Frorn

(11) rve have

(13)

_./(x,

y) -f(xo,

^yo)

: -Ðp,x,-L ^r¡!¡ * _Ð Ð

^cl¡

r¡)'¡:

:,Ð"(D,i, t, -

^Þ,)

^*,* _{,Ð.[ Ð'1,} ^*, - ^{q¡)v¡+ Ð.} l,Ð,

'1,

ti)*,'

^{; '}

From

(13)

it ^is

^clear

^that (i)-(ii)

^irnplies

that .f(*, {) -.f(xn,

^yo)

^<

⁰

for

each

xr>

0,

yiÞ 0

sufficierrtly small,

i.e,

^(x.o,

(=+)

Let

^(xo,

¡f) ^{be a local}

^{maximum and}

I

t (12)

72

a local

maxilnum.

yo) is

Ð ^r,l D

:t*l ti-¡*r

(14) "f(x', yi)

_{1(xg, yu)}

: _.'r

_:;..

Now,ifp>0,tI >

consider

ÉJ', àJ i

æ ^Io¡

j

í*l,o,j

cl¡

tr, i'þ p

(ctr¡ú

-

^q,,)t,

lclr't

-

^p,)t,

Therefore

"/(x,

y) -./(xo,

^Vo)

:,

j n.lo '

'r. rr,r¡nÚsc¡rc'

,r,lrl.;i , i .:_t i

,r:i , ,rlÌ j,

cI

v¡ - ^{,oi) n} i' ,Ð,,r,1,:D*, 'f ^{*, --}

^zqo)

0, the¡r

fro¡n

(12),

it

^follon's.

^that

it4

( 16)

r,.,I. IMARUSCI,!|C

6 ⁷ 76

Consider

the

inequalities. ^:

, ', i , ,, :,,1i. .. :

ON BILINIAR PROGRAMMING

I

{r ^{= n.l}

{1 ^{= o"'}

i

'i _(l*)i r,

e'r4 rh.'á

2. Let

(xo, yb) ba o d'eg'ùoerøia b.¡.s',

If

^th'bre 't,s.ø,f'¡'.0,

i

=

Iq,or ^tlrcyci¡

^{blu.> O,}

j _*

_J¿, thçn

fot'cucryts\,, (li _Vjì

^is .not'fe,asîl)tL

solutiÒn, where

' ''

., i,,',,

,,, ,i

^, .

i

^i.;r,

*u -,,(i11,

0,

. ,. r

,

x,,, ,...,r 9),.,

fu: t,)

^0,

(15) , . r, i:

^\

tr, :

(b1,

0,

, t . ,

yu, ..

. . , 0)t; ^'

lu i I >

^O.

Proof. Consid"r x""defined

in ^(ts¡'and let'ø|,'= 0,ti L Ïr;r.ph"ir,l,

: -ol,t <0, ^Vr> 0, ^{that rleans}

^xu

É X, Ort

-Ql

=

Similarly it

can be proved

that

yp

é Y, Vt > 0.{' ;r il 'i

^'¡

Now

the

sufficiency

of the

conditiorip

(i)-(ü).¿,iollowS

directly,.frorn

I,emma'2 and

^(14).

\ 5. _.

Global

¡r1uxir1¡rm ^,

f)l ^ttrc lriliney

¿liogramrnirrg

Assurnc

tha!

^{(a9, y1),}

xo: ^(a1,,0)

^i.q

^{a local maximum}

^of

/ ^{on l).}

Iherr it follows that (í)-(ii) or' (i)- (ii),, hold. Fo/ .r': (a',

A)

...,

^x¡,

...,0), _tr :

(b1,0,

..., !¡, ^...i;'0)

^{we have}

¡/¡ ç

^1xr

j¿'t tT

.,1, I r í.

since function

/

^touch

^its

r¡ráxirnurn

irr a

b,f.s.,

ít

follou,s

that

i';,¡,11

i .,,

rnax r{y'(x;,,y)l(x; V)

,er,Xl.X y1},-/(xo,

_yo);

;

,ì:i,ri where

Ð,ç

_,*,

,,ili,

'

_'.:" ^.t-,

',.¡.¡¡l 'j rrr liì

;¡: ;, i ¡t:l

(17)

5- _{',, --}

î7r

xi

X1

:XO

'o t']l

I

./(x',

x't -

^ntilJ.

{l >,gll(xr, ^yi) - ^f

^{(xo, yo)}

:

0},

Yt:Yn

^)-\\_LJ

j=J

".

^.

^{That !s rvhy, in}

^ord.er

^to

^{deter nine}

^{a rew local}

ruaxirrrun, _{rve shall}

fi'd

a local

maxirnq'r

_9f

/ ^{o^n_{x\XÐ} x (\y'), ^i.".

^uããing

to

ilre

l'iiiat

constraints (2)-(3) the following lwo:

(18) ' ^'Ð _,i! , ,; ^'Dnó ,'t

with this

ner'v

bilinear

programrning rn

e

procêed

.i,ililuri u¡ti1

the ptoblern becornes inconsistentl

ri t f i ii I _I

6r, Ileppripfion

,,of the

^algorithm

Frorr

above u'e cönclud.e

withrthe'folloiving:

algcirithm

fór he

global

rning

probleru.

u

(10)

find a

b.f,s.

f (i)

holds tb.en go tci step S, other_

osen

in a

colurnn

for

u,hlch

þ¡ 10

i '¡ l,

....

^s(1þ

^3.

^'r'ests

(ii) or (ii)r. rf (ii) or

(ii),, holcl

the'

go

to step 4.

other-

tvrse,

if

, ;: ,

_:" -"

,

t)¡')

0,, (d,

j) e II x I2

i

$.9,two. J.s. by chosing'ilre' þivcit elelnents

and go

to

Step

2. i ., i:

ii in the coluurn

i

^aÀd

j

respectively

*) 'flte _tc¡nts corrcsponcliug

to

x.!

: I

^ot

yf : -l

,are rrrissilg nr (17).

li! ':l Ìr

'll,¡

i,''j "i

' ,1:

ôtt¡

¡L

Define _lli

J/.rr

:

uri\r {t

> ^jlf(xt,

vr)

¡,fi+9,

^yo)

:0},

wlrere

x, : jt¡ : t.

^,

r, "

If

there is

j e./

such llnat

f(xi, yt)

_,f(xo, ^yo)

:0 has no

positivc solution,

then

ónc täkes

ii : *.o. Similariy, if

^-there

is i e /

such

that

Í(x', ^yj) -./("0,

^Yo)

:0

has

no positive solution thet

yf

':=rrf ^co' ,'t

^:

(i)

_do

not hold

lthere

is -

^{1 and}

-4 _ ^_B f ⁴

^negative

other

two ¡.s.

^{and we}

get the

tableau

-xt-i,à _!t _!a ^I

-16

0

-4

-12

0 0

'oì 10

I

0,,

⁰

00

10000 01000 00010 00101

2 o .)

I

s-6

0

000 20

00o

2 2 2 o

-16

2 4

010 100 0,-o

0

001

0 0

I

3 0,0

0

-ll

-8

2

-0

2 2 2 I 8 0 0

I

0 0 0

I

01 10 00 00 ll 100

5

I

I

6 (,

00

4-8

öñ nr¡.1ñ.ren Þhocnal"iMiñc

Í=

t:

0t

1l

1

-t¡- lt ^I

-*2-'frg,--

0

I

.>

Àfte¡

other

three

_J.s.

we get the

tableau

''.:i-

*L- tu2-

!z': tt-

1_

2, Since we do

0

,5 -6

*l*

tul-

It- tt=

',,. ^,

,ii

- qi-

xø_ ,t(a_ rçt_

!e

0- 0-

JL_

0-

Steþ

4.

Deterrnine

xf

^and

yf from (16), ,í,,, 1,,r;, ,

^{,:,, ; ,}

st-eþ

5. Add the

inequalities

(r7) to the initiar

constraints and go

t.

Step

1.

,

^The .algorithm

is

terminated

rvh:u the

bilinear programmiog

p"obl"rl

is inconsistent.

_{, i}

7. Example

îlo illustrate the

algorithrrr rve,solve the rollowing exarnple

:

maximizè

f(x,y): -xa- llxr- ^*r, I 4tr+2xry,- xtls* 6xny,*Sro1,n"

xz

-l x¿:2

'y, lyø -2

.' ::, ¡ : t;

1z * y¿:2

ⁱ

x, 7

0,

y¡

Þ

0,

_{i, :j}

: 1,2,

3, 4.

Steþ

L The initial

tableau

is:

_i,,

-

^xt

-

^xz

-

^fia

- x¿- ),t -!,¿ -!d -!¿

0

1

0 0

0

0 0 0 B

1

0 0 0

0 0 0

I

0 0

tr

1

0 0

i

0 0 0 0 0

0 0 0

_()

subject to

I

I to

2 2 2 2

After a J. ^{s. we}

^got

t ,1,1,.:

I. MARU$CIAC

^tL

0.:

0- 0- 0-

0Q0 000

)-

^xs

2-t

⁰

650

whjch sholvs

that the new

problem

is

inconsistent

(xr: _-xu -

¹

^<

^0'

foi

every

xu2

^0).

. _Theiefois

¡0

: (2,2,0,0) ;

^y0

: (2, 2, 0, O) is the optimal

solution and

/(x0'

vo)

: 0'.

(Iu'iu. ,,8øbeç-tsotyøi", clwi-Naþocø

Ul ^{A:1 t rrr a} n, l{., Bilinear þrogratnnti.ng.8u11. Acarl. Polo[. Sci. Sér. Sci. Math. Astr:ofom,

. phys.,

t?l Sokir¡r'.st íjøhstat'eM.Al,'tmana,,tsilineitcoeþrograntniro' uanie". ^(33), 91-98 ^(1975)'

[3] V an <1 al, À., , Èkonomska Analiza 4, Nr. 1-2, 21-41 ^(1970)'

0

1 1

0 0 0

100 000 000 001 010 0 0-6 11 I 0

⁰

0 _{0 -11-10}

oN tstl]NÉÀR pnOc;n¡løvrÑfi 79

f:

Received 30. llf. 1978.

îi

1

-8

2

1

3 I 2

-19 -25

RËITDRENCES

(Jniaersitøieo Bøbeç-BoIYai

Faculløtea de ^Møtematicã Str. Rogàl'niceønu' I 3400 Cluj-Naþoco

Steþ

l. After

one

J.s.

^rve

get the

tableau

-%r-xs-jt-!s

It:

tuÙ-

*4 - JL-

Jb

5-l 62

Sleþ 3.

^{Since y'n}

-

^11,

þs: l, 4¿,:4, ^{8s=g.it follows tlnat}

^{(xo' yo)'}

xo

=

^(2,

^2,0,0);

^Vo

=

^(2,?,0'Q),

is a ^local maximúm aird /(x0'

^yo)

! 8 -- 8'=

^0'"

steþ4.wehave i I 'i i r¡ i'

l@: fl-.f(xo, ^v9 : lt(t -3) ':

_o;

_{i'"' t),,:3}

Í(*{,"yr) -,(i.,

^Vo)

: _-19t + 6ltz'\0,'tsa ; :

tO¡6,

I

Similarly

^{we obtain}

'ä

=='19/6, and

yiì: +co.

liìl

'I'herefore

the

inequslities (17)

are ,

^'

Steþ

5. The

new simplex tabjeau

is _the

^following

0 8

1 a

11

10

'

_xT

: min

_{3,19/6}

:

3- L MÀRtr$clAë

where

fü

2

7,q

tt

2

6

r ir..t ¡,i i _''ì

2

llli ' ' l' ;; tl

: _+oo

/c¡

: -5,

il i (, ' ^ir

y1),-/(io,

^yq)

:'-51,- F:ö,

\.' _{\ ¡r,:'.}

r,¡ _i..: ill'r¡ì)'11:i

,r$

2 I

-19 xè 3i'and"i62)

_-: 19.

it - ij Siuce

Í(x',

: i _1l

-frt-1h ^-¡t¿--!s , 1 0,Q,,Q,,,i

4.

1; 0 0,' 0

^I

0,09,1 ,0,0 1

^A

0 0 0-6 01 00

tuL-

u2

^,-,

tu6-

lt-

Nõ-_