Содержание
Постановка задачи. 3
Решение задачи 1. 4
Решение задачи 2. 6
Описание программного средства. 8
Постановка задачи
Задача 4.1
Выделены денежные средства S0=100 для вложения в инвестиционные проекты. По каждому проекту известен возможный прирост fi(x) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы. Требуется:
1) распределить средства S0 между проектами так, чтобы суммарный прирост прибыли на всех четырех проектах достиг максимальной величины;
Числовые данные: 
.
Задача 4.2
В начале планового периода продолжительностью 6 лет имеется оборудование, возраст которого t. Оборудование не должно быть старше 6 лет. Известны: стоимость r(t) продукции, произведенной в течение года с помощью этого оборудования; ежегодные расходы u(t), связанные с эксплуатацией оборудования; его остаточная стоимость s; стоимость p нового оборудования, включающая расходы, связанные с установкой, наладкой и запуском оборудования. Остаточная стоимость убывает пропорционально сроку службы (для последнего года принять равной 10%). Требуется:
1) составить матрицу максимальных прибылей за 6 лет;
2) сформировать по матрице максимальных прибылей оптимальные стратегии замены оборудования возрастов t и t1 лет в плановом периоде продолжительностью 6 и N лет.
Необходимые данные приведены в табл. 4.2.
Числовые данные:
Решение задачи 1
Дана задача линейного программирования. Для её решения было создано программное средство, описанное ниже. Результаты работы программы:
Алгоритм решения строится на следующих рассуждениях. Рассмотрим ориентированное дерево с обращённым направлением стрелок к корню. Корень соответствует случаю, когда все части суммы вложены в некоторые инвестиционные проекты (задача решена). Первый от корня ярус соответствует ситуациям, когда следует принимать решение о количестве частей, приходящихся на 4-й проект. Вершины яруса располагаются вертикально – в соответствии с количеством уже распределённых частей. Разность общего количества частей и числа нераспределённых равна объёму средств, вкладываемых в 4-й проект. Исходя из последнего утверждения, можно подсчитать прибыль, которая может быть получена только от 4-го проекта при некотором распределении средств по другим проектам. Прибыль будет мерой для вершины этого яруса. Аналогично поступаем с остальными ярусами. Мера вершины равняется сумме прибыли, полученной от принятия решения и перехода на следующий ярус, и меры той вершины предыдущего яруса, к которой будет проведено ребро. Если возможность распределения для текущей вершины оставшихся средств одна (4 ярус), то мера вершины определяется однозначно и строится ребро к вершине предыдущего яруса. Если таких возможностей несколько, то выбирается та, которая даёт наибольшую прибыль в локальном смысле. На рисунке выше представлен граф, рёбра которого построены так, чтобы реализовать максимальную прибыль.
Структура данных для решения задачи: матрица неких узлов, хранящих информацию о максимальной прибыли, получаемой после принятия решения, которому узел соответствует, и о переходах в состояния, которые это решение реализуют.
Матрица прибыли заполняется по столбцам, начиная с последнего.
|
|
Последний столбец матрицы составлен для различных вариантов вложения средств в 4-тый проект, вторая – в 3-тий, первая – во 2-ой. Номер строки соответствует количеству уже распределённых средств. Первая строка матрицы содержит прибыль для тех случаев, когда в предыдущие проекты средства не вкладываются. Горизонтальное ребро означает то, что очередной проект не получит инвестиций.
Последнее решение (количество частей для первого проекта) принимается по данным первого столбца матрицы 
и первой строке матрицы A.
Таким образом, оптимальное распределение средств: 20 единиц во второй проект, 20 единиц – в третий, 60 единиц – в четвёртый. Прибыль составит 18 единиц.
Решение задачи 2
Данную задачу можно решать с использованием графической модели, аналогичной предыдущей, рассмотрев орграф, вершины которого – узлы прямоугольной сетки или точки с целочисленными координатами в прямоугольной декартовой системе координат. Вдоль горизонтальной оси откладываем время, соответствующее плановому периоду, вдоль вертикальной – возраст оборудования на момент начала очередного планового года.
Каждая вершина характеризуется мерой – максимальной прибылью, которое получит предприятие за оставшееся время, и номерами вершин, на которые произойдёт переход в начале следующего года: либо при замене (уровень 1 года), либо при продолжении использования (уровень возраста оборудования на начало следующего года). Если возраст оборудования равен максимально допустимому, то его следует заменить в начале следующего года. Вершина на оси возраста оборудования находится на уровне возраста оборудования, которым располагает предприятие на момент начала планового периода. Таким образом, для каждого состояния дел к началу очередного года (возраст оборудования и прибыль) возможны, в общем случае, две стратегии: замены и продолжения использования оборудования. Из этих двух следует выбрать ту, которая принесёт максимальную прибыль:
1) Прибыль при замене = остаточная стоимость оборудования (цена его продажи) + выручка при работе на новом оборудовании + максимальная прибыль оставшегося планового времени – стоимость нового оборудования – издержки на обслуживание нового оборудования.
2) Прибыль при продолжении использования = выручка при работе на нём – издержки на обслуживание + максимальная прибыль оставшегося планового времени.
В отличие от предыдущей задачи, в данном случае анализ должен проводиться не только с конца планового периода: сначала отмечаем те узлы, в которые можно попасть из исходного в соответствии с правилом «продолжить/заменить», а затем для каждого узла рассчитывать максимальную прибыль.
Решение задачи с помощью разработанного программного средства:
| 
|
| Столбец | Строка | Решение | Продолжить | Заменить |
| з | =29 -15+5,2= 19,2 | =6,5+30-14-8+6,5= 21 | ||
| з | =22 -18+1,3= 5,3 | =2,6+30-14-8+6,5= 17,1 | ||
| з | =22 -18+17,1= 21,1 | =3,9+30-14-8+21= 32,9 |
Стратегия: замена на каждом шаге, максимальная прибыль равна 32,9 ден.ед.
Плановый период равен 6 лет, возраст оборудования – 1 год.
| Столбец | Строка | Решение | Продолжить | Заменить |
| з | =29 -15+5,2= 19,2 | =6,5+30-14-8+6,5= 21 | ||
| з | =23 -15+3,9= 11,9 | =5,2+30-14-8+6,5= 19,7 | ||
| з | =22 -18+2,6= 6,6 | =3,9+30-14-8+6,5= 18,4 | ||
| з | =22 -18+1,3= 5,3 | =2,6+30-14-8+6,5= 17,1 | ||
| з | =21 -19+0,8= 2,8 | =1,3+30-14-8+6,5= 15,8 | ||
| з | 0.0 | =0,8+30-14-8+6,5= 15,3 | ||
| з | =29 -15+19,7= 33,7 | =6,5+30-14-8+21= 35,5 | ||
| з | =23 -15+18,4= 26,4 | =5,2+30-14-8+21= 34,2 | ||
| з | =22 -18+17,1= 21,1 | =3,9+30-14-8+21= 32,9 | ||
| з | =22 -18+15,8= 19,8 | =2,6+30-14-8+21= 31,6 | ||
| з | =21 -19+15,3= 17,3 | =1,3+30-14-8+21= 30,3 | ||
| з | =29 -15+34,2= 48,2 | =6,5+30-14-8+35,5= 50 | ||
| з | =23 -15+32,9= 40,9 | =5,2+30-14-8+35,5= 48,7 | ||
| з | =22 -18+31,6= 35,6 | =3,9+30-14-8+35,5= 47,4 | ||
| з | =22 -18+30,3= 34,3 | =2,6+30-14-8+35,5= 46,1 | ||
| з | =29 -15+48,7= 62,7 | =6,5+30-14-8+50= 64,5 | ||
| з | =23 -15+47,4= 55,4 | =5,2+30-14-8+50= 63,2 | ||
| з | =22 -18+46,1= 50,1 | =3,9+30-14-8+50= 61,9 | ||
| з | =29 -15+63,2= 77,2 | =6,5+30-14-8+64,5= 79 | ||
| з | =23 -15+61,9= 69,9 | =5,2+30-14-8+64,5= 77,7 | ||
| з | =29 -15+77,7= 91,7 | =6,5+30-14-8+79= 93,5 |
Очевидно, что при таких исходных данных оптимальная стратегия – ежегодная замена оборудования, так как его стоимость гораздо меньше затрат на эксплуатацию. Максимальная прибыль равна 93,5 ден.ед.
Описание программного средства
Системные требования
Операционная система: Windows Vista и выше, пакет.Net Framework 3.5.
Устройства ввода: клавиатура, мышь.
Объём оперативной памяти: 128 Мб.
Частота процессора: 1 ГГц.
Среда разработки
Microsoft Visual Studio 2008, язык C#.
Потоки данных
Входные данные: таблица с данными, целочисленные значения длительности периода и возраста оборудования.
Выходные данные: таблица промежуточных данных, экспортированная в Word и граф переходов.
Основные сущности объектно-ориентированной модели решения:
1. Form – форма для ввода пользовательских данных.
2. GraphDisplay– класс для визуализации графа.
3. WordAccessor – класс, обеспечивающий экспорт в MS Word 2007.
4. Node – класс, хранящий данные об узле.
5. DynamicProgramming – класс, выполняющий алгоритм динамического программирования.
Листинг
Класс DynamicProgramming (задача 1)
public class DynamicProgramming
{
public DynamicProgramming(int[,] BenefitsMatrix)
{
int rows = BenefitsMatrix.GetLength(0);
int cols = BenefitsMatrix.GetLength(1);
Node[,] Nodes = new Node[rows + 1, cols - 1];
List<int> last = new List<int>();
last.Add(rows);
for (int i = 0; i < rows + 1; i++)
{
if (i == rows) Nodes[i, cols - 2] = new Node(last, 0);
else Nodes[i, cols - 2] =
new Node(last, BenefitsMatrix[rows - i - 1, cols - 1]);
}
for (int j = cols - 3; j >= 0; j--)
{
for (int i = 0; i < rows + 1; i++)
{
int MaxVal = -1;
List<int> fathers = new List<int>();
for (int k = i; k < rows + 1; k++)
{
int value = Nodes[k, j + 1].profit +
((k - i > 0)? BenefitsMatrix[k - i - 1, j + 1]: 0);
if (MaxVal == value)
{
fathers.Add(k);
}
if (MaxVal < value)
{
MaxVal = value;
fathers.Clear();
fathers.Add(k);
}
}
Nodes[i, j] = new Node(fathers, MaxVal);
}
}
List<int> StartFathers = new List<int>();
int MaxVal1 = -1;
for (int k = 0; k < rows + 1; k++)
{
int value = Nodes[k, 0].profit;
if (k > 0) value += BenefitsMatrix[k - 1, 0];
if (MaxVal1 == value)
{
StartFathers.Add(k);
}
if (MaxVal1 < value)
{
MaxVal1 = value;
StartFathers.Clear();
StartFathers.Add(k);
}
}
Node ResultNode = new Node(StartFathers, MaxVal1);
GraphDisplay gd = new GraphDisplay(Nodes, ResultNode);
gd.Show();
}
}
Класс DynamicProgramming (задача 2)
public class DynamicProgramming
{
Node[,] Nodes;
DataTable table;
public DynamicProgramming(double[,] DataMatrix,int startAge,int period)
{
table = new DataTable();
table.Columns.Add(new DataColumn("Столбец"));
table.Columns.Add(new DataColumn("Строка"));
table.Columns.Add(new DataColumn("Решение"));
table.Columns.Add(new DataColumn("Продолжить"));
table.Columns.Add(new DataColumn("Заменить"));
int rows = DataMatrix.GetLength(0) - 1;
int cols = period;
Nodes = new Node[rows, cols];
List<int> last = new List<int>();
last.Add(0);
List<int> StartFathers = new List<int>();
double ThrowCost;
Node ResultNode = new Node(null, 0.0);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
Nodes[i, j] = new Node(null,0.0);
}
}
GoAheadIfPossible(startAge,0);
GoAheadIfPossible(0, 0);
StartFathers = new List<int>();
StartFathers.Add(0);
StartFathers.Add(startAge);
ResultNode.fathers = StartFathers;
for (int i = 1; i < rows + 1; i++)
{
Nodes[i - 1, cols - 1] = new Node(last, DataMatrix[i, 2]);
}
for (int j = cols - 2; j >= 0; j--)
{
for (int i = 0; i < rows; i++)
{
if (Nodes[i,j].fathers!= null)
{
string solution ="";
List<int> fathers = new List<int>();
double throwCost = DataMatrix[i + 1, 2] +
DataMatrix[0, 0] - DataMatrix[0, 1]
- DataMatrix[0, 2] + Nodes[0, j + 1].profit;
double followCost = 0.0;
if (i + 1 == rows)
{
Nodes[i, j].profit = throwCost;
solution = "з";
goto write;
}
followCost = DataMatrix[i + 1, 0] - DataMatrix[i + 1, 1] +
Nodes[i + 1, j + 1].profit;
if (Math.Abs(throwCost - followCost) < 0.1)
{
Nodes[i, j].profit = followCost;
solution = "п: з";
goto write;
}
if (throwCost - followCost < 0.1)
{
Nodes[i, j].profit = followCost;
solution = "п";
}
if (throwCost - followCost > 0.1)
{
Nodes[i, j].profit = throwCost;
solution = "з";
}
write:DataRow theRow = table.NewRow();
theRow[0] = j+1;
theRow[1] = i+1;
theRow[2] = solution;
if (followCost!= 0.0) theRow[3] = "="
+ DataMatrix[i + 1, 0].ToString() + " "
+ (-DataMatrix[i + 1, 1]).ToString() + "+"
+ Nodes[i + 1, j + 1].profit.ToString()+"=
"+followCost.ToString();
else theRow[3] = "0.0";
theRow[4] = "="+ DataMatrix[i + 1, 2].ToString() +"+"+
DataMatrix[0, 0].ToString()
+(- DataMatrix[0, 1]).ToString()+
(- DataMatrix[0, 2]).ToString()
+"+" + Nodes[0, j + 1].profit.ToString()
+"= "+throwCost;
table.Rows.Add(theRow);
}
}
}
string sol = "";
for (int i = 2; i < rows + 1; i++)
{
if (Nodes[i - 2, cols - 2].fathers == null)
Nodes[i - 1, cols - 1].fathers = null;
}
StartFathers = new List<int>();
ThrowCost = DataMatrix[startAge, 2] + DataMatrix[0, 0]
- DataMatrix[0, 1] - DataMatrix[0, 2] + Nodes[0, 0].profit;
ResultNode = new Node(null, 0.0);
if (startAge == rows)
{
StartFathers.Add(0);
ResultNode = new Node(StartFathers, ThrowCost);
sol = "з";
}
else
{
StartFathers.Add(0);
StartFathers.Add(startAge);
}
double FollowCost = 0.0;
FollowCost = DataMatrix[startAge, 0] - DataMatrix[startAge, 1]
+ Nodes[startAge, 0].profit;
if (ThrowCost < FollowCost)
{
ResultNode = new Node(StartFathers, FollowCost);
sol = "п";
}
if (ThrowCost == FollowCost)
{
ResultNode = new Node(StartFathers, FollowCost);
sol = "п:з";
}
if (ThrowCost > FollowCost)
{
ResultNode = new Node(StartFathers, ThrowCost);
sol = "з";
}
DataRow TheRow = table.NewRow();
TheRow[0] = 0;
TheRow[1] = startAge;
TheRow[2] = sol;
TheRow[3] = "=" + DataMatrix[startAge, 0].ToString() + " "
+ (-DataMatrix[startAge, 1]).ToString() + "+"
+ Nodes[startAge, 0].profit.ToString() + "= " +
FollowCost.ToString();
TheRow[4] = "=" + DataMatrix[startAge, 2].ToString() + "+"
+ DataMatrix[0, 0].ToString()
+ (-DataMatrix[0, 1]).ToString() + (-DataMatrix[0, 2]).ToString()
+ "+" + Nodes[0, 0].profit.ToString() + "= " +
ThrowCost.ToString();
table.Rows.Add(TheRow);
GraphDisplay gd = new GraphDisplay(Nodes, ResultNode, startAge);
gd.Show();
WordAccessor wa = new WordAccessor(table);
}
private void GoAheadIfPossible(int start,int level)
{
if (start!= Nodes.GetLength(0) - 1)
{
List<int> f = new List<int>();
f.Add(0);
if (level!= Nodes.GetLength(1)-1) f.Add(start+1);
//if (start < Nodes.GetLength(0))
Nodes[start, level].fathers = f;
if (level+1< Nodes.GetLength(1))
{
GoAheadIfPossible(start + 1, level + 1);
GoAheadIfPossible(0, level + 1);
}
}
else
{
List<int> f = new List<int>();
f.Add(0);
Nodes[start, level].fathers = f;
if (level + 1 < Nodes.GetLength(1))
{
GoAheadIfPossible(0, level + 1);
}
}
}
}