Использование табличного симплекс-метода для решения задач линейного программирования для оптимизации экономических задач

|A1 |2 |7/2 |1 |0 |0 |1/2 |-1/4 |

| |( |9 1/4 |0 |0 |0 |1/4 |5/8 |

- 15 -

Так как все симплекс-разности положительны, то оптимальное решение

найдено :

X = ( 7/2 , 3/4 , 11/4 , 0 , 0 ) ( единиц )

max F = 9 1/4 ( рублей )

- 16 -

4. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

4.1 Построение двойственной задачи и её численное решение

Проведение анализа на чувствительность связано с теорией

двойственности, поэтому в курсовой работе необходимо построить двойственную

задачу и найти её численное решение.

Для рассматриваемой модели двойственная задача имеет вид :

min T( y ) = min ( 10y1 + 12y2 + 10y3 ) при условиях

y1 + 3y2 + 2y3 ( 2

А1

5y1 + 2y2 + 4y3 ( 3 А2

y1 ( 0 , y2 (0 , y3

( 0. А3, А4, А5

Оптимальное решение двойственной задачи получается при решении прямой

задачи из последней симплекс-таблицы. В результате получаем оптимальное

решение двойственной задачи :

Yопт = ( 0, 1/4, 5/8, 0, 0 ), для которого Т(yопт) = 9 1/4.

Оптимальное значение целевой функции в двойственной задачи совпадает с

оптимумом целевой функции прямой задачи, в чём не трудно убедиться.

4.2 Определение статуса ресурсов

Ресурсы относятся к дефицитным, если оптимальный план предусматривает

их полное использование, при частичном использовании ресурсов, они

считаются не дефицитными. Статус ресурсов для любой модели линейного

программирования можно установить непосредственно из оптимальной симплекс-

таблицы исходной по значению дополнительных переменных. Положительное

значение до -

- 17 -

полнительной переменной указывает на неполное использование

соответствующего ресурса, т.е. на его недефицитность, нулевое значение

дополнительной переменной указывает на дефицитность ресурса.

Для данного примера дополнительные переменные х4 и х5 равны нулю,

следовательно, оборудование второго и третьего типов являются

“дефицитными”, а первого типа - “недефицитным” ( х3 = 2,75 ). Такой же

вывод можно сделать из решения двойственной задачи.

4.3 Определение значимости ресурсов

Значимость ресурса характеризуется величиной улучшения оптимального

значения целевой функции F, приходящейся на единицу прироста данного

ресурса. Значимость ресурсов всегда можно определить по значению

двойственных переменных в оптимальном решении двойственной задачи.

В данном случае Yопт = ( 0, 1/4, 5/8, 0, 0 ). Таким образом, из двух

“дефицитных” ресурсов оборудование второго типа имеет большую значимость и

увеличении интервала работы на этом оборудовании более выгодно с точки

зрения влияния на значение целевой функции.

4.4 Определение допустимого интервала изменения запаса ресурсов

Изменение отведённого администрацией предприятия времени ( т.е. правых

частей ограничений ) может привести к недопустимости текущего решения.

Поэтому важно определить диапазон изменений компонент вектора ограничений,

в котором допустимость решений не нарушается.

Оборудование второго типа, которое используется для изготовления

изделий, является “дефицитным и имеет большую значимость. Определим

диапазон допустимых изменений интервала работы на этом оборудовании.

Оптимальная

- 18 -

симплекс-таблица задачи имеет вид :

| | |C |2 |3 |0 |0 |0 |

|Б |Cб |A0 |A1 |A2 |A3 |A4 |A5 |

|A2 |3 |3/4 |0 |1 |0 |-1/4 |3/8 |

|A3 |0 |11/4 |0 |0 |1 |3/4 |-13/8 |

|A1 |2 |7/2 |1 |0 |0 |1/2 |-1/4 |

| |( |9 1/4 |0 |0 |0 |1/4 |5/8 |

Так как начальными базисными переменными являлись x1, x2, x3 в

оптимальной симплексной таблице в соответствующих столбцах расположена

матрица А-1 Изменим время работы на оборудование второго типа на величину

(2, тогда время работы будет 12 + (2 .

Найдём базисное решение, соответствующее изменённому времени работы на

оборудовании второго типа :

[pic]

0.75 - (2 / 4 ( 0 , (2 = 3;

2.75 + 3(2 / 4 ( 0 , (2 = -3.66;

3.5 + (2 / 2 ( 0 , (2 = -7.

Отсюда видно, что -3.66 ( (2 ( 3 , т.е. 8.34 ( b2 ( 15 .

Таким образом первоначальный интервал работы на оборудовании второго

типа можетбыть увеличен до 15 часов или уменьшен до 8.34 часа без нарушения

допустимого решения. Уменьшение времени влечёт за собой уменьшение единиц

вырабатываемой продукции, поэтому является не целесообразным.

- 19 -

4.5 Исследование зависимости оптимального решения от

изменений запасов ресурсов

Изменение свободного члена ограничения исходной задачи на величину (2

вызывает изменение целевой функции на (F = ( i ( y j .Если приращение

времени работы бертся из интервала допустимых изменений, значений

двойственных оценок остаются неизменными. Таким образом, изменение целевой

функции будет линейно зависеть от изменения времени работы.

В данном примере (F = ( i ( 12 = 12 ( ( i . Ищется зависимость

значений целевой функции от изменения времени работы на оборудовании

второго типа. Для этого изменяется время работы начиная от 0 часов с шагом

h = 0.5 до 3 часов.Результаты измерений приведены в таблице 1.

Таблица 1

|(2, часов|0 |0.5 |1 |1.5 |2 |2.5 |3 |

|b2, часов|12 |12.5 |13 |13.5 |14 |14.5 |15 |

|(F, руб. |0 |6.25 |13 |20.25 |28 |36.25 |45 |

|F, руб. |9.25 |( |( |( |( |( | |

Т.к. зависимость F( b2 ) - линейная, то достаточно подсчитать значение

функции в двух крайних точках интервала.

Cледовательно, с увеличением времени работы на оборудовании второго

типа на 2 часа увеличивается и объём изделий на общей стоимостью 28

рублей.

- 20 -

5. ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ПОЛУЧЕННЫХ

РЕЗУЛЬТАТОВ

Графический метод применим только для двух и менее переменных х, что

подходит к данному заданию.Линии, соответствующие ограничения, строятся на

осях Ох. Заштрихованная область - область допустимых стратегий.

x1 + 5x2 ( 10 ;

3x1 + 2x2 ( 12 ;

2x1 + 4x2 ( 10 .

x1 ( 0 ; x2 ( 0 .

1). x1 + 5x2 ( 10 ;

x1 = 0, x2 = 2 ;

x1 = 10, x2 = 0 .

2). 3x1 + 2x2 ( 12 ;

x1 = 0, x2 = 6 ;

x1 = 4, x2 = 0 .

3). 2x1 + 4x2 ( 10 ;

x1 = 0, x2 = 2.5 ;

x1 = 5, x2 = 0 .

4). Найдём экстремум функции :

F = 2x1 + 3x2 ,

[pic]

Графически область допустимых решений показана на рисунке 1.

- 21 -

Рисунок 1 - Область допустимых решений данной системы.

- 22 -

6. ВЫВОДЫ И РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ

ИСПОЛЬЗОВАНИЮ

Составление математической модели и решение систем линейных неравенств

часто имеет место в реальной жизни. Примеры таких задач :

Пример 1. Рассматривается работа промышленного предприятия под углом

зрения его рентабельности, причём приводится ряд мер с целью повышения этой

рентабельности. Показатель эффективности - прибыль ( или средняя прибыль ),

приносимая предприятием за хозяйственный год.

Пример 2. Группа истребителей поднимается в воздух для перехвата

одиночного самолёта противника. Цель операции - сбить самолёт. Показатель

эффективности - вероятность поражения цели.

Пример 3. Ремонтная мастерская занимается обслуживанием машин; её

рентабельность определяется количеством машин, обслуженных в течение дня.

Показатель эффективности - среднее число машин, обслуженных за день.

Пример 4. Группа радиолокационных станций в определённом районе ведёт

наблюдение за воздушным пространством. Задача группы - обнаружить любой

самолёт, если он появится в районе. Показатель эффективности - вероятность

обнаружения любого самолёта, появившегося в районе.

Пример 5. Предпринемается ряд мер по повышения надёжности электронной

цифровой вычислительной техники ( ЭЦВТ ). Цель операции - уменьшить частоту

появления неисправностей ( “сбоев” ) ЭЦВТ, или, что равносильно, увеличить

средний промежуток времени между сдоями ( “наработку на отказ” ).

Показатель эффективности - среднее время безотказной работы ЭЦВТ.

Пример 6. Проводится борьба за экономию средств при производстве

определённого вида товара. Показатель эффективности - количество

сыкономленных средств.

С помощью анализа модели на чувствительность определить параметр, от

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

увеличение эффективности и на сколько, а так же многое другое.

- 23 -

ПРИЛОЖЕНИЕ

- 24 -

СОДЕРЖАНИЕ

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . 25

1. НАЗНАЧЕНИЕ ПРОГРАММЫ. . . . . . . . . . . . . . . . . . . . . . . . . .

. . 26

2. УСЛОВИЯ ПРИМЕНЕНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . 26

1.1 Ограничения и область применения . . . . . . . . . . . . . . . .

. . . . . 6

1.2 Требования к техническим средствам . . . . . . . . . . . . . . .

. . . . . 7

3. ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ . . . . . . . . . . . . . . . . . . . . . .

5

4. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ . . . . . . . . . . . . . . . . . . . . . . . .

. 11

5. ТЕКСТ ИСХОДНОГО МОДУЛЯ . . . . . . . . . . . . . . . . . . . . . . . . .

. . 11

6. ОПИСАНИЕ ЛОГИКИ СТРУКТУРНОЙ СХЕМЫ . . . . . . . . . . . . 11

7. ТЕСТОВЫЙ ПРИМЕР. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . 25

- 25 -

ВВЕДЕНИЕ

В данной части пояснительной записки к курсовой работе представлена и

описана программа, релизующая решение систем линейных неравенств табличным

методом.

- 26 -

1. НАЗНАЧЕНИЕ ПРОГРАММЫ

Программа предусмотрена для решения систем линейных неравенств

табличным методом, а так же для попытки оптимизации различных

экономических, социальных и т. д. проблем.

Метод, описанный в программе, может применяться на государственных и

частных предприятиях для улучшения эффективности производства.

- 27 -

2. УСЛОВИЯ ПРИМЕНЕНИЯ

1.1 Ограничения и область применения

Из программных средств требуется операционная система MS DOS

версии 5.0, программная Среда NORTON COMMANDER, язык программирования

Borland Pascal 7.0 . Кроме того НГМД должен содержать файлы в директории

KURSOVIK:

1. Файл входных данных - KURS97.DAT

2. Программный файл - KURS97.EXE

1.2 Требования к техническим средствам

IBM PC или IBM PC - совместимый компьютер с дисководом 3.25” ёмкостью

1.2 Мб.

- 28 -

3. ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ

Входные и выходные данные заносятся в файлы KURS97.DAT и KURS97.RES

соответственно. Входные данные записываются в определённом порядке.

Выходные данные записываются в виде симплекс-таблиц.

- 29 -

4. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

Входные данные вносятся в файл KURS 97.DAT в следующей очерёдности :

сначача вводятся коэффициенты при неизвестных в целевой функции, затем

вводятся элементы вектора ограничений, а потом - элементы матрицы

ограничений по столбцам.

Результаты вычислений вы найдёте в файле KURS 97.REZ.

- 30 -

5. ТЕКСТ ИСХОДНОГО МОДУЛЯ

Полный текст программы KURS97.PAS выглядит следующим образом :

. program Kurs97;

uses crt;

const

n = 2;

m = 3;

Epsilon = 0.000001;

var

VectorA : array [1..m, 0..m+n] of real;

TargetVector : array [1..m+n] of real;

SimplexVector : array [0..m+n] of real;

DigitOfBasisVector : array [1..m] of real;

BasisVector : array [1..m] of integer;

IndexOfEnterVector : integer;

IndexOfOutputString : integer;

MinimumBuffer : real;

key : char;

FileOfOutput : text;

{ Описание процедур }

procedure ReadDates; { считывание данных из файла }

var

DateFile : text;

procedure ReadDatesTargetVector; { считывание данных целевого вектора

}

var i : integer;

begin

for i:=1 to n do Readln(DateFile, TargetVector[i]);

end;

procedure ReadDatesVectorA; { считывание вектора А и заполнение

единицами диагонали}

var i,j : integer;

begin

for j:=0 to n do

for i:=1 to m do

Readln(DateFile, VectorA[i, j]);

i:=1;

for j:=n+1 to n+m do

- 31 -

begin

VectorA[i, j]:=1;

inc(i)

end;

end;

procedure ReadDatesBasisVector;

var i : integer;

begin

for i:=1 to m do BasisVector[i]:=n+i;

end;

begin

Assign(DateFile, 'kurs97.dat');

Reset(DateFile);

ReadDatesTargetVector;

ReadDatesVectorA;

ReadDatesBasisVector;

Close(DateFile);

end;

procedure CountSimplexVector; { расчет симплек-вектора }

var

i,j : integer;

Summa : real;

Simplex : real;

begin

SimplexVector[0]:=0;

for i:=1 to m do

SimplexVector[0]:=SimplexVector[0] +

DigitOfBasisVector[i]*VectorA[i, 0];

for j:=1 to m+n do

begin

Summa:=0;

for i:=1 to m do Summa:=Summa + DigitOfBasisVector[i]*VectorA[i,

j];

SimplexVector[j]:=Summa - TargetVector[j];

if abs(SimplexVector[j]) SimplexVector[i]

then

- 32 -

begin

GetEnterVector:=i;

Min:=SimplexVector[i];

end;

end;

function GetOutputString : integer; { поиск выводимой строки }

var

i : integer;

Temp : real;

begin

GetOutputString:=1;

if VectorA[1, IndexOfEnterVector] > 0 then MinimumBuffer:=VectorA[1,

0] / VectorA[1, IndexOfEnterVector];

for i:=2 to m do

begin

Temp:=VectorA[i, 0] / VectorA[i, IndexOfEnterVector];

if Temp > 0 then

if MinimumBuffer >= Temp then

begin

MinimumBuffer:=Temp;

GetOutputString:=i;

end;

end;

end;

procedure ReCountOutputString; { пересчет коэффициентов выводимой

строки }

var

i,j : integer;

Buffer : real;

procedure ReCountDigitOfBasisVector;

begin

DigitOfBasisVector[IndexOfOutputString]:=TargetVector[IndexOfEnterVector];

end;

procedure ReCountBasisVector;

begin

BasisVector[IndexOfOutputString]:=IndexOfEnterVector;

end;

begin

ReCountDigitOfBasisVector;

ReCountBasisVector;

Buffer:=VectorA[IndexOfOutputString, IndexOfEnterVector];

for i:=0 to m+n do

begin

VectorA[IndexOfOutputString, i]:=VectorA[IndexOfOutputString, i] /

Buffer;

end;

end;

- 33 -

procedure ReCountVectorA;

var i,j : integer;

begin

for j:=0 to m+n do

begin

for i:=1 to m do

begin

if i <> IndexOfOutputString then

if j <> IndexOfEnterVector

then VectorA[i, j]:=VectorA[i, j] - VectorA[i,

IndexOfEnterVector]*VectorA[IndexOfOutputString, j];

end;

end;

for i:=1 to m do

if i <> IndexOfOutputString then VectorA[i, IndexOfEnterVector]:=0;

end;

function AllIsPositiv : boolean;

var i : integer;

begin

AllIsPositiv:=True;

for i:=1 to m+n do

if SimplexVector[i] < 0 then AllIsPositiv:=False;

end;

function ToStr(const D : real) : string;

var S : string;

begin

str(D:6:2, S);

ToStr:=' ' + S + ' ';

end;

procedure WriteMatrixs;

procedure WriteTargetMatrix;

var i : integer;

begin

writeln(' +---------------------------------------

--------------+');

write (' ¦ Target ¦');

for i:=1 to n+m do write(ToStr(TargetVector[i]),'¦'); writeln;

end;

procedure WriteMatrixA;

var i,j : integer;

begin

writeln(' +-----------------+--------+--------+--------+--------+---

-----+--------¦');

writeln(' ¦ Basis ¦ D.Basis¦ A 0 ¦ A 1 ¦ A 2 ¦ A 3 ¦

A 4 ¦ A 5 ¦');

writeln(' +--------+--------+--------+--------+--------+--------+---

-----+--------¦');

for i:=1 to m do

- 34 -

begin

write(' ¦ A ',BasisVector[i],'

¦',ToStr(DigitOfBasisVector[i]),'¦');

for j:=0 to m+n do write(ToStr(VectorA[i, j]),'¦'); writeln;

if i = m then writeln(' +--------+--------+--------+--------+-----

---+--------+--------+--------¦')

else writeln(' +--------+--------+--------+--------+-----

---+--------+--------+--------¦');

end;

end;

procedure WriteMatrixSimplex;

var i : integer;

begin

write(' ¦ Simplex¦');

for i:=0 to m+n do write(ToStr(SimplexVector[i]),'¦'); writeln;

writeln(' +------------------------------------------------

--------------+');

end;

begin

clrscr;

WriteTargetMatrix;

WriteMatrixA;

WriteMatrixSimplex;

end;

procedure WriteMatrixsInFile;

procedure WriteTargetMatrix;

var i : integer;

begin

writeln(FileOfOutput, ' +-------------------------

----------------------------+');

write (FileOfOutput, ' ¦ Target ¦');

for i:=1 to n+m do write(FileOfOutput, ToStr(TargetVector[i]),'¦');

writeln(FileOfOutput);

end;

procedure WriteMatrixA;

var i,j : integer;

begin

writeln(FileOfOutput, ' +-----------------+--------+--------+-------

-+--------+--------+--------¦');

writeln(FileOfOutput, ' ¦ Basis ¦ D.Basis¦ A 0 ¦ A 1 ¦ A 2

¦ A 3 ¦ A 4 ¦ A 5 ¦');

writeln(FileOfOutput, ' +--------+--------+--------+--------+-------

-+--------+--------+--------¦');

for i:=1 to m do

begin

write(FileOfOutput, ' ¦ A ',BasisVector[i],'

¦',ToStr(DigitOfBasisVector[i]),'¦');

for j:=0 to m+n do write(FileOfOutput, ToStr(VectorA[i, j]),'¦');

writeln(FileOfOutput);

if i = m then writeln(FileOfOutput, ' +--------+--------+--------

+--------+--------+--------+--------+--------¦')

else writeln(FileOfOutput, ' +--------+--------+--------

+--------+--------+--------+--------+--------¦');

end;

end;

- 35 -

procedure WriteMatrixSimplex;

var i : integer;

begin

write(FileOfOutput, ' ¦ Simplex¦');

for i:=0 to m+n do write(FileOfOutput,

ToStr(SimplexVector[i]),'¦'); writeln(FileOfOutput);

writeln(FileOfOutput, ' +----------------------------------

----------------------------+');

end;

begin

clrscr;

WriteTargetMatrix;

WriteMatrixA;

WriteMatrixSimplex;

end;

{ Головная программа }

BEGIN

ClrScr;

ReadDates;

Assign(FileOfOutput, 'kurs97.res');

Rewrite(FileOfOutput);

CountSimplexVector;

WriteMatrixs;

while not AllIsPositiv do

begin

IndexOfEnterVector:=GetEnterVector;

IndexOfOutputString:=GetOutputString;

ReCountOutputString;

ReCountVectorA;

CountSimplexVector;

WriteMatrixsInFile;

WriteMatrixs;

if key=#0 then key:=readkey; key:=#0;

end;

Close(FileOfOutput);

END.

- 36 -

6. ОПИСАНИЕ ЛОГИКИ СТРУКТУРНОЙ СХЕМЫ

В программе реализованны следующие процедуры :

1. Процедура ReadDates - считывает данные из файла.

2. Процедура ReadDatesTargetVector - считывает коэффициенты при

неизвестных в целевой функции из файла.

3. Процедура ReadDatesVector - считывание их входного файла матрицы А и

заполнение диагональной матрицы.

4. Процедура CountSimplexVector - рассчёт симплекс-разностей.

5. Процедура GetEnterVector - поиск вводимого в базис столбца.

6. Процедура GetOutputString - поиск выводимой из базиса строки.

7. Процедура ReCountOutputString- пересчёе выводимой строки.

8. Процедура ReCountVectorA - пересчёт остальной матрицы ограничений.

9. Процедуры WriteMatrixA, WriteTargetMatrix, WriteMatrixSimplex -

печать результирующих таблиц на экран и в файл.

- 37 -

7. ТЕСТОВЫЙ ПРИМЕР

Тестовый пример программы KURS 97.EXE представлен на рисунке 2 в виде

исходной и результирующих симплекс-таблиц данного задания.

- 39 -

ЛИТЕРАТУРА

1. ЕСПД ГОСТ 19.105-78, 19.104-78.

2. ЕСПД ГОСТ 19.502-78.

3. Венцель Е.С. Исследование операций.-М.:Советское радио. 1972 г.

4. Дектярев Ю.И. Исследование операций.-М.:Высшая школа. 1986 г.

5. Зайченко Ю.П. Исследование операций.-К.:Вища школа. 1979 г.

6. Зайченко Ю.П., Шумиллова С.А. Исследование операций ( сборник задач ).-

К.:Вища школа. 1990 г.

Страницы: 1, 2