Реферат Программная реализация задачи дробно-линейного программирования
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное агентство по образованию
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра экономической информации
Курсовой проект
по курсу «Имитационное моделирование экономических процессов»
на тему: «Программная реализация задачи дробно-линейного программирования»
Факультет:
Группа:
Студент:
Преподаватель:
Новосибирск
2009
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ. 3
1. ПОСТАНОВКА ЗАДАЧИ.. 4
2. ТЕКСТ ПРОГРАММЫ.. 7
3. ТЕСТИРОВАНИЕ ПРИЛОЖЕНИЯ.. 17
ЗАКЛЮЧЕНИЕ. 20
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ. 21
ВВЕДЕНИЕ
В курсовом проекте необходимо реализовать программное обеспечение, разработанное в среде программирования Delphi 7, в виде консольного приложения на языке Object Pascal.
Входная информация (исходные данные задачи) должны быть размещены в отдельном последовательном файле с расширением .txt, структурированы c краткими комментариями.
Выходная информация, также должна выводиться в отдельный последовательный файл, содержать координаты оптимального решения, значение целевой функции, краткую интерпретацию результатов и предусмотреть возможность отображения промежуточных результатов.
Размерность задачи должна быть произвольной и задаваемой исходными данными, однако существуют ограничения:
· Число производственных ресурсов m может меняться от 2 до 20;
· Число продуктов n может меняться от 2 до 20.
После разработки программного обеспечения, необходимо сгенерировать и просчитать тестовые примеры разной размерности. Результаты численных экспериментов необходимо сопоставить с результатами, получаемыми при использовании ILOG OPL Studio на тех же исходных данных.
1. ПОСТАНОВКА ЗАДАЧИ
Администрация производственной фирмы желает рассчитать еженедельную программу выпуска своих изделий A и B, которая дает максимум чистого дохода на рубль всех сделанных затрат.
Изделие А гарантированно реализуется по цене 208.3 руб., а изделие B по цене 23.9 руб.
Расход сырья на изделие A составляет 3 кг, а на изделие B- 2 кг. Расход оборудования на изделие A составляет 2 ст. час., на изделие B- 4 ст.час. Минимальные объемы сырья и станочного парка, при которых не произойдет остановки производства составляют, соответственно: 600 кг, и 400 ст. час. в неделю.
Фирма же имеет 1800 кг сырья, 800 ст. час. оборудования. Себестоимости изделия A и изделия B (без учета заработной платы) составляют, соответственно, 235.6 руб., 3.0 руб.
Сумма оплаты рабочих и служащих фирмы вместе с другими накладными расходами составляет 5.76 тыс. руб. в неделю.
Требуется:
1. Составить экономико-математическую модель расчета оптимальной программы выпуска изделий фирмы.
2. Решить полученную задачу дробно-линейного программирования симплекс-методом с обобщенным критерием оптимальности.
Решение:
Построим экономико-математическую модель задачи дробно-линейного программирования в общем случае.
Введем переменные решаемой задачи:
Тогда получаем ограничения на производство продукции за счет имеющегося в наличия объема производственных ресурсов:
где pj – цена товара j, по которой он может быть продан на рынке;
сj – себестоимость производства единицы товара j без учета зарплаты;
p0 – накладные расходы производства всего объема продукции.
Задача дробно-линейного программирования решается с помощью симплекс-метода. Строиться исходная симплекс-таблица.
Первая фаза симплекс-метода – поиск допустимого решения. Выбираем в качестве временной целевой функции строку таблицы с отрицательным элементом в столбце свободных членов. В выбранной строке находим любой отрицательный элемент, он определяет разрешающий столбец. Разрешающая строка находится по минимальному неотрицательному отношению элементов столбца свободных членов к соответствующим им по строкам элементам разрешающего столбца.
Процесс повторяется, пока в столбце свободных членов имеются отрицательные элементы. Как только в столбце свободных членов нет отрицательных элементов, то переходим ко второй фазе симплекс-метода.
Обобщающим критерием оптимальности является – неотрицательность определителей
Если при максимизации рентабельности получим отрицательное значение целевой функции, тогда полученный результат будет свидетельствовать об убыточности производственного процесса. При этом максимизация рентабельности приводит к минимизации убыточности.
2. ТЕКСТ ПРОГРАММЫ
Для разработки программного обеспечения используется среда разработки Borland Delphi 7 с использованием языка Object Pascal.
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils, System; //
type matrixtype = array [0..100] of array [0..100] of real; // описание типа
vector= array of integer; // описание типа
var element: vector; // хранит координаты разрешающего элемента
matrix: matrixtype; // жорданова матрица
n,m: integer; // n ресурсов и m товаров
i,j: integer; // элемент матрицы
k: integer; // вспомогательная для формирования первоначальной матрицы
Input, Output: TextFile; // файловые переменные
temp: string; // строка из файла
rent: real; // значение целевой функции
iteration: integer; // количество итераций
answer: array of real;
function first_part(matrix: matrixtype): vector;
// Функция получает матрицу Matrix и возвращает
// координаты разрешающего элементы
var a,b,c,d,e: integer;
min_vector: array of real; // вектор значений Bi/aij
minimum: real; // значение минимального элемента Bi/aij
begin
SetLength(min_vector,n+1); // установление размерности вектора
SetLength(Result,3); // установление размерности вектора для разрешающего элемента
// инициализации переменной Result в "-1"
Result[1]:=-1;
Result[2]:=-1;
// поиск отрицательных элементов в правой части матрицы
for a:=1 to n do
begin
if (matrix[a,m+1]<0) then // если найден в a-той строке отрицательный элемент
begin
for b:=1 to m do // то ищем в a-той строке отрицательные элементы
begin
if (matrix[a,b]<0) then // если нашли отрицательный элемент в строке а,
// то это и будет наш разрешающий столбец
begin
for c:=1 to n do // и мы формирует вектор отношений Bi/aij
begin
if (matrix[c,b]<>0) then // если элемент aij неотрицателен
min_vector[c]:=matrix[c,m+1] / matrix[c,b] // то находим отношение
else // иначе
min_vector[c]:=-1; // значение отношения Bi/aij равно "-1"
end;
c:=1;
minimum:=min_vector[c]; // первоначально инициализируем минимальное значение первым элементом вектора отношений Bi/aij
while ((minimum<=0) AND (c<=n)) do // если он отрицателен, то ищем первое положительное отношение, которое не вылазиет за вектор
begin
minimum:=min_vector[c]; // найденный первый минимальный положительный элемент
c:=c+1; // указатель на следующий элемент вектора отношений Bi/aij
end;
e:=c; // сохраним в отдельную переменную указатель вектора на мин эелемент
for d:=c to n do // пробегаем оставшуюся часть вектора отношений Bi/aij и
begin
if ((min_vector[d]<minimum) AND (min_vector[d]>0)) then// и ищем минимальное положительное отношение Bi/aij
begin
minimum:=min_vector[d]; // если нашли, то присваиваем в переменную minimum значение
e:=d; // и призваиваем указатель на элемент вектора в e
end;
end;
Result[1]:=e; // значение разрешающей строки
Result[2]:=b; // значение разрешающего столбца
end;
end;
end;
end;
end;
function simplex(matrix: matrixtype; element: vector): matrixtype;
// Функция получает матрицу Matrix и вектор Element с координатами разрешающего элемента и
// производит итерацию симплекс-метода
var i, j, ir, jr: integer;
begin
ir:=element[1]; jr:=element[2];// координаты разрешающего элемента
// вычисления элементов новой матрицы матрицы правилом прямоугольника
for i:=1 to n+2 do // пробегаемся по строкам
begin
if (i<>ir) then begin // если строка не разрешающая, то
for j:=1 to m+1 do // пробегаемся по столбцам
begin
if ((j<>jr)) then // если столбец не разрешающих, то
begin // вычисляем значение элемента новой матрицы правилом прямоугольника
Result[i,j]:=((matrix[i,j]*matrix[ir,jr])-(matrix[i,jr]*matrix[ir,j]))/matrix[ir,jr];
end;
end;
end;
end;
// вычислим значения элементов новой матрицы по разрешающему столбцу
for i:=1 to n+2 do // все строки матрицы
begin
result[i,jr]:=-((matrix[i,jr])/(matrix[ir,jr])); // вычисление элементов на разрешающем столбце
end;
// вычисляем значения матрица по разрешающей строке
for j:=1 to m+2 do // по всем столбцам
begin
// находим значения матрицы по разрешающем строке
result[ir,j]:=((matrix[ir,j])/(matrix[ir,jr]));
end;
// значение матрица на месте разрешающего элемента
result[ir,jr]:=1/matrix[ir,jr];
// копируем в новую матрицу имена переменных
for i:=1 to n do // в строках
result[i,0]:=matrix[i,0];
for j:=1 to m do // в столбцах
result[0,j]:=matrix[0,j];
// фиксируем имена выведенных и введенных в симлекс-таблицу переменных
result[ir,0]:=matrix[0,jr]; // введенная
result[0,jr]:=matrix[ir,0]; // выведенная
end;
function second_part(matrix: matrixtype): vector;
// Второй этап: поиск определителей и нахождение разрешающего элемента
// в случае неоптимальности решения
var det,min_vec: array of real;
j,h: integer;
a,b: integer;
minimum: real;
begin
SetLength(Result,3); // выделение памяти под дин массив для хранения координат
// разрешающего элемента
SetLength(det,m+1); // выделение памяти под дин массив для хранения
// определителей матрицы
// инициализация переменных на выходе
result[1]:=-1;
result[2]:=-1;
b:=-1; // для хранения номера столбца, первоначально "-1"
for j:=1 to m do // считаем ВСЕ определители, число которых равно числу товаров
begin // считаем определители матрицы
det[j]:=(matrix[n+1,j]*matrix[n+2,m+1])-(matrix[n+2,j]*matrix[n+1,m+1]);
if (det[j]<0) then // если нашли отрицательный определитель
begin
b:=j;// то сохраняем в b номер столбца с отрицательным определителем
end;
end;
if (b>-1) then begin // если уж нашли столбец, то надо найти и строку
SetLength(min_vec,n+1); // выделение памяти под вектор отношений Bi/aij
for j:=1 to n do // пробегаемся по строкам
begin
if (matrix[j,b]>0) then // правые части уже >0, поэтому если aij больше нулю, то
min_vec[j]:=matrix[j,m+1]/matrix[j,b] // находим отношения
else
min_vec[j]:=-1; // иначе "-1"
end;
minimum:=min_vec[1]; // первый элемент отношения B1/a1j принимаем за минимальный
h:=1; // указатель на этот элемент
while ((minimum<=0) AND (h<=n)) do // если он нас не удовлетворяет, то
begin
h:=h+1;
minimum:=min_vec[h]; // находим ближайший положительный элемент в векторе отношений
end;
a:=h; // сохраняем указатель на минимальный элемент в векторе
for j:=h+1 to n do // и ищем в оставшейся части минимальный элемент
begin
if ((min_vec[j]<minimum) AND (min_vec[j]>0)) then // если найдем, то
begin
minimum:=min_vec[j]; // Запишем значение в переменную "minimum"
a:=j; // в "а" указатель на этот элемент
end;
end;
Result[1]:=a; // найденная разрешающая строка
Result[2]:=b; // найденный разрешающий столбец
end;
end;
procedure write_matrix(matrix: matrixtype);
// выводит на консоль матрицу Matrix
var i,j: integer; // индексы массива
begin
for i:=1 to n+2 do // по всем строчкам
begin
for j:=1 to m+1 do // по всем столбцам
begin
Write(FloatToStr(matrix[i,j])+' ');// конвертируем в вещественное число и печатаем на экран
end;
writeln(''); // конец строки матрицы печатаем отдельно
end;
end;
procedure write_into_file(matrix: matrixtype);
// Функция печатает матрицу Matrix в файл OUTPUT.txt
var i,j: integer; // Индексы массива
begin
writeln(Output,'');WriteLn(Output,'[Simplex Table ]'+IntToStr(iteration)); // формируем строчку промежуточного расчета
for i:=1 to n+2 do // по всем строчкам
begin
for j:=1 to m+1 do // по всем столбикам
begin
Write(Output,FloatToStr(matrix[i,j])+' '); // конвертируем в вещественное число и печатаем в текстовый файл
end;
writeln(Output,''); // печатаем в файл Output конец строки
end;
end;
begin
SetLength(answer,m+1); // выделение памяти под массив для ответа
WriteLn('Drobno-lineynaya optimization'); // заголовок программы
AssignFile(Input, 'input.txt'); // присвоение файла переменной Input
Reset(Input); // открываем файл для чтения
AssignFile(Output, 'output.txt'); // присвоение переменной Output файла для вывода
Rewrite(Output); // открываем файл для записи решения
ReadLn(Input,Temp);// читаем строку
n:=StrToInt(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1)); // количество ресурсов
ReadLn(Input,Temp); // считываем следующую строку
n:=n*2; // ограничения для минимума и максимума поэтому удваиваем
m:=StrToInt(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1)); // количество товаров
ReadLn(Input,Temp);// убираем пустую строку
ReadLn(Input,Temp); // считываем себестоимость товаров
// инициализация нумерации переменных
for i:=1 to n do // нумеруем строки матрицы
matrix[i,0]:=-i; // отрицательны для различения от переменных основной задачи
for j:=1 to m do // нумеруем столбы матрицы
matrix[0,j]:=j; // положительные, т.к. переменные основной задачи
for j:=1 to m do // для каждого товара
begin // считываем себестоимость из строки temp
matrix[n+2,j]:=-StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1));
temp:=Copy(temp,Pos(';',temp)+1,Length(temp)-Pos(';',temp)); // удаляем обработанный элемент
end;
ReadLn(Input,Temp);// считываем следующую строку
for j:=1 to m do // по каждому товару
begin // считываем цену товара
matrix[n+1,j]:=-StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1))-matrix[n+2,j]; //и определяем прибыль (цена-с/с)
temp:=Copy(temp,Pos(';',temp)+1,Length(temp)-Pos(';',temp)); // удаляем обработанный элемент из строки temp
end;
ReadLn(Input,Temp);// удаляем пустую строку
ReadLn(Input,Temp);// считываем строку расхода сырья
k:=1; // переменная для нумерации ресурсов
while (k<n) do // пока не обработаем данные о расходе сырья
begin
for j:=1 to m do // на каждый товар
begin
matrix[k,j]:=-StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1));// считываем данные о расходе для ограничения по минимуму сырья
matrix[k+1,j]:=StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1));// считываем данные о расходе для ограничения по максимуму сырья
temp:=Copy(temp,Pos(';',temp)+1,Length(temp)-Pos(';',temp)); // удаляем обработанный элемент строки
end;
ReadLn(Input,Temp); // считываем следующую строку
matrix[k,m+1]:=-StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1)); // выделяем минимальное количество сырья
temp:=Copy(temp,Pos(';',temp)+1,Length(temp)-Pos(';',temp)); // удаляем его из строки temp
matrix[k+1,m+1]:=StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1)); // находим максимальное количество товара
temp:=Copy(temp,Pos(';',temp)+1,Length(temp)-Pos(';',temp)); // удаляем его из строки (хотя это лишняя операция)
ReadLn(Input,Temp); // считываем информацию по следующему ресурсу
k:=k+2;
end;
ReadLn(Input,Temp); // считываем информацию о накладных расходах (постоянные затраты)
matrix[n+1,m+1]:=-StrToFloat(Copy(temp,Pos('=',temp)+1,Pos(';',temp)-Pos('=',temp)-1)); // записываем значения в строку прибыли со знаком "-"
matrix[n+2,m+1]:=-matrix[n+1,m+1]; // со знаком "+" в строчку затрат
CloseFile(Input); // закрываем входной файл INPUT
WriteLn(Output,'[BEGIN]'); // уже сейчас формируем выходной файл
iteration:=0; // обнуляем счетчик итераций симплекс-метода в ноль
write_into_file(matrix); // вводим матрицу первоначальную в файл
iteration:=iteration+1; // операция инкремент для количества итераций
write_matrix(matrix); // печатаем первоначальную матрицу на экран
writeln('Press ENTER to continued...'); // печатаем сообщение
readln; // ждем чтобы пользователь посмотрел первоначальную таблицу
SetLength(element,3); // выделяем память под массив для хранения координат разрешающего элемента
element:=first_part(matrix); // ищем разрешающий элемент
while (element[1]<>-1) do // пока есть отрицательные элементы в правой части, тогда
begin
matrix:=simplex(matrix,element); // производим итерацию симплекс-методом
element:=first_part(matrix); // проверяем оптимальной решения и фиксируем разрешающий элемент в переменную element
write_matrix(matrix); // вывод матрицы на экран
write_into_file(matrix); // и в файл
iteration:=iteration+1; // увеличиваем количество итераций
writeln('Press ENTER to continued...'); // печатаем сообщение
readln; // ждем чтобы пользователь посмотрел первоначальную таблицу
end;
element:=second_part(matrix); // проверяем оптимальной решения по определителям, правая часть положительня вся, в element-координаты разрешающего элемента
while (element[2]<>-1) do // если имеется столбец с отрицательным определителем
begin
matrix:=simplex(matrix,element); // производим итерацию симплекс-методом
write_matrix(matrix); // вывод матрицы на экран
write_into_file(matrix); // и в файл
iteration:=iteration+1; // увеличиваем количество итераций
element:=second_part(matrix); // проверяем оптимальность рещения
writeln('Press ENTER to continued...'); // печатаем сообщение
readln; // ждем чтобы пользователь посмотрел первоначальную таблицу
end;
// формирование ответа пользователю
rent:= matrix[n+1,m+1]/matrix[n+2,m+1]; // вычисляем значение целевой функции
WriteLn('rentabelnost = ',rent:10:4); // печатаем его на экран
WriteLn(Output,' '); // также печатаем ответ в файл OUTPUT
WriteLn(Output,'[ANSWER]'); // также печатаем ответ в файл OUTPUT
WriteLn(Output,'Maximum profitability = '+FloatToStr(rent));
WriteLn(Output,' '); // также печатаем ответ в файл OUTPUT
WriteLn(Output,'[VARIABLES]'); // определяем координаты решения
for i:=1 to n do // проверяем переменные в строчках
begin
if matrix[i,0]>0 then // если есть переменная в решении, то
begin
Write('X',matrix[i,0]:1:0,' = ',matrix[i,m+1]:10:0, ' ');//печатаем на экран
Write(Output,'X',matrix[i,0]:1:0,' = ',matrix[i,m+1]:10:0, ' ');// и в файл
answer[i]:=matrix[i,m+1];
end
else
begin
if (i<=m) then // если нет переменных в решении, то печатаем значение равное 0
begin
Write('X',abs(matrix[i,0]):10:0,' = ',0,' '); // на экран
Write(Output,'X',abs(matrix[i,0]):10:0,' = ',0, ' '); // и в файл
answer[i]:=0;
end;
end;
end;
WriteLn(Output,'');
WriteLn(Output,'[INTERPRETATION]');
WriteLn(Output,' Максимальная рентабельность предприятия может составить ', rent:10:4, ' при выполнении следующей производственной программы:');
for i:=1 to m do
begin
WriteLn(Output,'Товара №',i,' в объеме ',answer[i]:10:0, ' единиц.');
end;
WriteLn(Output,'');
WriteLn(Output,'[END]');
CloseFile(Output); // закрываем выходной файл
WriteLn(' ');
WriteLn('In current directory create file OUTPUT.EXE when written result of task ');// информируем пользователя об окончании вычислений
ReadLn;
end.
3. ТЕСТИРОВАНИЕ ПРИЛОЖЕНИЯ
Рассмотрим пример решения задачи дробно-линейного программирования по своему варианту 321 размерностью: два производственных ресурса и два продукта (2 * 2). Входной файл «input.txt» будет содержать следующую информацию о задаче.
Содержимое файла
INPUT.TXT
Количество_ресурсов=2;
Количество_товаров=2;
[Параметры для целевой функции]
Себестоимость_1 =235,6;Себестоимость_2=3;
Цена_1=208,3;Цена_2=23,9;
[Параметры для ограничений задачи]
Расход_1_сырья_на_1_товар=3;Расход_1_сырья_на_2_товар=2;
Минимум_сырья_1=600;Максимум_сырья_1=1800;
Расход_2_сырья_на_товар_1=2;Расход_2_сырья_на_2_товар=4;
Минимум_сырья_2=400;Максимум_сырья_2=800;
Накладные_расходы=5760;
Окно выполнения программы в консольном режиме представлено на рис. 1.
Рис.1. Окно выполнения консольного приложения.
После выполнения программы мы получили выходной файл OUTPUT.TXT с решением задачи и промежуточными вычислениями, содержание которого отражено ниже:
Содержимое
файла
OUTPUT.TXT
[BEGIN]
[Simplex Table 0]
-3 -2 -600
3 2 1800
-2 -4 -400
2 4 800
27,3 -20,9 -5760
-235,6 -3 5760
[Simplex Table 1]
-2 -0,5 -400
2 0,5 1600
0,5 -0,25 100
0 1 400
37,75 -5,225 -3670
-234,1 -0,75 6060
[Simplex Table 2]
-2 0,5 -200
2 -0,5 1400
0,5 0,25 200
0 1 400
37,75 5,225 -1580
-234,1 0,75 6360
[Simplex Table 3]
-0,5 -0,25 100
1 0 1200
0,25 0,375 150
0 1 400
18,875 14,6625 -5355
-117,05 -57,775 29770
[Simplex Table 4]
2 0,5 400
-4 -1,5 600
4 1,5 600
0 1 400
-75,5 -13,65 -16680
468,2 117,8 100000
[ANSWER]
Maximum profitability = -0,1668
[VARIABLES]
X1 = 400 X 2 = 0
[INTERPRETATION]
Максимальная рентабельность предприятия может составить -0.1668 при выполнении следующей производственной программы:
Товара №1 в объеме 400 единиц.
Товара №2 в объеме 0 единиц.
[END]
Сопоставим полученное решение с решением, которое получено при использовании ILOG OPL Studio на тех же исходных данных.
Рис. 2. Лист drobno1 книги Excel ind.xls
Рис. 3. Результат вычисления в программе ILOG OPL Studio
x1 = t1/t0=0.004/0.00001=400
x2 = t2/t0=0/0.00001=000
z = -0.1668
Таким образом, решение разработанной программы совпадает с решением в среде ILOG OPL Studio при одинаковых исходных данных.
Рассмотрим теперь пример решения задачи дробно-линейного программирования следующей размерностью: шесть производственных ресурса и девять продуктов (6 * 9). Входной файл «input.txt» будет содержать следующую информацию о задаче.
Содержимое файла
INPUT
.
TXT
Количество_ресурсов=6;
Количество_товаров=9;
[Параметры для целевой функции]
Себестоимость_1 =235,6;Себестоимость_2=3;Себестоимость_3 =145;Себестоимость_4=50;Себестоимость_5 =20;Себестоимость_6=330;Себестоимость_7 =14;Себестоимость_8=150;Себестоимость_9=450;
Цена_1=208,3;Цена_2=23;Цена_3=115;Цена_4=71;Цена_5=35;Цена_6=300;Цена_7=34;Цена_8=150;Цена_9=468;
[Параметры для ограничений задачи]
Сырье1товар1=3;Сырье1товар2=2;Сырье1товар3=2;Сырье1товар4=4;Сырье1товар5=6;Сырье1товар6=4;Сырье1товар7=4;Сырье1товар8=2;Сырье1товар9=1;
Минимум_сырья_1=9000;Максимум_сырья_1=15000;
Сырье2товар1=7;Сырье2товар2=4;Сырье2товар3=3;Сырье2товар4=5;Сырье2товар5=7;Сырье2товар6=2;Сырье2товар7=3;Сырье2товар8=1;Сырье2товар9=2;
Минимум_сырья_1=15500;Максимум_сырья_1=20000;
Сырье3товар1=1;Сырье3товар2=2;Сырье3товар3=2;Сырье3товар4=4;Сырье3товар5=3;Сырье3товар6=4;Сырье3товар7=6;Сырье3товар8=3;Сырье3товар9=2;
Минимум_сырья_1=8000;Максимум_сырья_1=15000;
Сырье4товар1=2;Сырье4товар2=6;Сырье4товар3=4;Сырье4товар4=2;Сырье4товар5=3;Сырье4товар6=2;Сырье4товар7=5;Сырье4товар8=7;Сырье4товар9=3;
Минимум_сырья_1=25000;Максимум_сырья_1=40000;
Сырье5товар1=2;Сырье5товар2=3;Сырье5товар3=4;Сырье5товар4=5;Сырье5товар5=3;Сырье5товар6=2;Сырье5товар7=5;Сырье5товар8=3;Сырье5товар9=1;
Минимум_сырья_1=10000;Максимум_сырья_1=25000;
Сырье6товар1=3;Сырье6товар6=2;Сырье6товар3=2;Сырье6товар4=4;Сырье6товар5=6;Сырье6товар6=4;Сырье6товар7=4;Сырье6товар8=2;Сырье6товар9=1;
Минимум_сырья_1=9000;Максимум_сырья_1=18000;
Накладные_расходы=60000;
Окно выполнения программы в консольном режиме представлено на рис. 4.
Рис.4. Окно выполнения консольного приложения.
После выполнения программы мы получили новый выходной файл OUTPUT.TXT с решением задачи и промежуточными вычислениями. Так как количество итераций при решении задачи симплекс-методом насчитывает 20, ниже приведено только решение самой задачи и интерпретация:
Содержимое файла
OUTPUT
.
TXT
[ANSWER]
Maximum profitability = 0,533333333333354
[VARIABLES]
X ( 0 5000 0 0 0 0 0 0 0)
[INTERPRETATION]
Максимальная рентабельность предприятия может составить 0.5333 при выполнении следующей производственной программы:
Товара №1 в объеме 0 единиц.
Товара №2 в объеме 5000 единиц.
Товара №3 в объеме 0 единиц.
Товара №4 в объеме 0 единиц.
Товара №5 в объеме 0 единиц.
Товара №6 в объеме 0 единиц.
Товара №7 в объеме 0 единиц.
Товара №8 в объеме 0 единиц.
Товара №9 в объеме 0 единиц.
Сопоставим полученное решение с решением, которое получено при использовании ILOG OPL Studio на тех же исходных данных.
Рис. 5. Лист drobno2 книги Excel ind.xls
Рис. 6. Результат вычисления в программе ILOG OPL Studio
x1 = t1/t0=0/0.000013333=0
x2 = t2/t0=0.066667/0.000013333=5000
x3 = t3/t0=0/0.000013333=0
x4 = t4/t0=0/0.000013333=0
x5 = t5/t0=0/0.000013333=0
x6 = t6/t0=0/0.000013333=0
x7 = t7/t0=0/0.000013333=0
x8 = t8/t0=0/0.000013333=0
x9 = t9/t0=0/0.000013333=0
z = 0.5333
Таким образом, решение, полученное нашей программой, совпадает с решением в среде ILOG OPL Studio при одинаковых исходных данных.
Рассмотрим теперь пример решения задачи дробно-линейного программирования следующей размерностью: четыре производственных ресурса и два продукта (4 * 2). Входной файл «input.txt» будет содержать следующую информацию о задаче.
Содержимое файла
INPUT
.
TXT
Количество_ресурсов=4;
Количество_товаров=2;
[Параметры для целевой функции]
Себестоимость_1 =300;Себестоимость_2=150;
Цена_1=350;Цена_2=230;
[Параметры для ограничений задачи]
Сырье1товар1=3;Сырье1товар2=2;;
Минимум_сырья_1=1000;Максимум_сырья_1=2000;
Сырье2товар1=5;Сырье2товар2=7;
Минимум_сырья_1=700;Максимум_сырья_1=2100;
Сырье3товар1=4;Сырье3товар2=1;
Минимум_сырья_1=600;Максимум_сырья_1=1200;
Сырье4товар1=2;Сырье4товар2=4;
Минимум_сырья_1=500;Максимум_сырья_1=1000;
Накладные_расходы=6000;
Окно выполнения программы в консольном режиме представлено на рис. 7.
Рис.7. Окно выполнения консольного приложения.
После выполнения программы мы получили новый выходной файл OUTPUT.TXT с решением задачи и промежуточными вычислениями:
Содержимое файла
OUTPUT
.
TXT
[Simplex Table 0]
-3.0000 -2.0000 -1000.0000
3.0000 2.0000 2000.0000
-5.0000 -7.0000 -700.0000
5.0000 7.0000 2100.0000
-4.0000 -1.0000 -600.0000
4.0000 1.0000 1200.0000
-2.0000 -4.0000 -500.0000
2.0000 4.0000 1000.0000
-50.0000 -80.0000 -6000.0000
-300.0000 -150.0000 6000.0000
[Simplex Table 1]
-1.5714 -0.2857 -800.0000
1.5714 0.2857 1800.0000
0.7143 -0.1429 100.0000
-0.0000 1.0000 1400.0000
-3.2857 -0.1429 -500.0000
3.2857 0.1429 1100.0000
0.8571 -0.5714 -100.0000
-0.8571 0.5714 600.0000
7.1429 -11.4286 2000.0000
-192.8571 -21.4286 21000.0000
[Simplex Table 2]
-2.0000 -0.5000 -750.0000
2.0000 0.5000 1750.0000
0.5000 -0.2500 125.0000
1.5000 1.7500 1225.0000
-3.5000 -0.2500 -475.0000
3.5000 0.2500 1075.0000
-1.5000 -1.7500 175.0000
-0.0000 1.0000 500.0000
-10.0000 -20.0000 4000.0000
-225.0000 -37.5000 24750.0000
[Simplex Table 3]
-2.0000 0.5000 -500.0000
2.0000 -0.5000 1500.0000
0.5000 0.2500 250.0000
1.5000 -1.7500 350.0000
-3.5000 0.2500 -350.0000
3.5000 -0.2500 950.0000
-1.5000 1.7500 1050.0000
-0.0000 1.0000 500.0000
-10.0000 20.0000 14000.0000
-225.0000 37.5000 43500.0000
[Simplex Table 4]
-0.5714 0.3571 -300.0000
0.5714 -0.3571 1300.0000
0.1429 0.2857 200.0000
0.4286 -1.6429 200.0000
-0.2857 -0.0714 100.0000
1.0000 -0.0000 600.0000
-0.4286 1.6429 1200.0000
-0.0000 1.0000 500.0000
-2.8571 19.2857 15000.0000
-64.2857 21.4286 66000.0000
[Simplex Table 5]
1.3333 -1.8333 -33.3333
-1.3333 1.8333 1033.3333
-0.3333 0.8333 133.3333
2.3333 -3.8333 466.6667
0.6667 -1.1667 233.3333
-2.3333 3.8333 133.3333
1.0000 0.0000 1400.0000
0.0000 1.0000 500.0000
6.6667 8.3333 16333.3333
150.0000 -225.0000 96000.0000
[Simplex Table 6]
-0.7273 -0.5455 18.1818
-0.0000 1.0000 1000.0000
0.2727 0.4545 118.1818
-0.4545 -2.0909 536.3636
-0.1818 -0.6364 254.5455
0.4545 2.0909 63.6364
1.0000 0.0000 1400.0000
0.7273 0.5455 481.8182
12.7273 4.5455 16181.8182
-13.6364 -122.7273 100090.9091
[ANSWER]
Maximum profitability = 0,161671207992734
[VARIABLES]
X ( 254.54545 118.18182)
[INTERPRETATION]
Максимальная рентабельность предприятия может составить 0.1617 при выполнении следующей производственной программы:
Товара №1 в объеме 255 единиц.
Товара №2 в объеме 118 единиц.
[END]
Сопоставим полученное решение с решением, которое получено при использовании ILOG OPL Studio на тех же исходных данных.
Рис. 8. Лист drobno3 книги Excel ind.xls
Рис. 9. Результат вычисления в программе ILOG OPL Studio
x1 = t1/t0=0.0025431/0.0000099909=254.54
x2 = t2/t0=0.0011807/0.0000099909=118.18
z = 0.1616712
Таким образом, решение, полученное нашей программой, совпадает с решением в среде ILOG OPL Studio при одинаковых исходных данных.
При тестировании приложения мы использовали тестовые примеры разной размерностью, причем, в первом случае n=m, затем n<m, и в конце n>m. И во всех случаях программа, написанная на языке Delphi, выдавало правильное решение, которое совпадало с решением, полученным с помощью ILOG OPL Studio. Следовательно, программная реализация задачи дробно-линейного программирования выполнена верна.
ЗАКЛЮЧЕНИЕ
В курсовом проекте было реализовано программное обеспечение в виде консольного приложения на языке Object Pascal для решения задачи дробно-линейного программирования.
Входная информация (исходные данные задачи) размещается в отдельном последовательном файле input.txt, файл структурирован и содержит краткие комментарии.
Выходная информация, также выводиться в отдельный последовательный файл output.txt, содержит координаты оптимального решения, значение целевой функции, краткую интерпретацию полученных результатов задачи и отображает промежуточные результаты вычисления.
Размерность задачи должна быть произвольной и задаваемой исходными данными, однако существуют ограничения:
· Число производственных ресурсов m может меняться от 2 до 20;
· Число продуктов n может меняться от 2 до 20.
После разработки программного обеспечения, необходимо сгенерированы и просчитаны тестовые примеры разной размерности. Результаты численных экспериментов сопоставлены с результатами, получаемыми при использовании ILOG OPL Studio на тех же исходных данных.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1. Бобровский, С. И. Delphi 7 : учебный курс / С. Бобровский. - СПб. [и др.] : Питер , 2007. - 735 с. ил.
2. Мезенцев Ю. А. Экономико-математические методы: учебное пособие / Ю. А. Мезенцев; Новосиб. гос. техн. ун-т. - Новосибирск : Изд-во НГТУ , 2004. - 212 с. ил.
