Реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства

      F_N(x₀) = (z₁(x₀, u₁) + F_N-1(x₁)), (9)

      где F_N(x₀), F_N-1(x₁) – соответственно условно-оптимальные значения функции цели на всех N этапах, N-1 этапах; z_i(x_i-1, u_i) – значение функции цели на i-том этапе.

     Последнее выражение  называется рекуррентным уравнением Беллмана. Отчетливо просматривается их рекуррентный характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д

     Также в работе приведен числовой пример задачи распределения ресурсов. Структура алгоритма решения таких задач представлена в блок-схемах (см. Приложение А), используя которые опытный программист сможет реализовать этот алгоритм на любом языке программирования. В частности в данной работе представлена реализация задачи на языке программирования Pascal (см. Приложение В). В дальнейшем планируется реализация данного метода на более сложных языках.

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

СПИСОК  ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Кузнецов, А.В. Высшая математика. Математическое программирование / А.В. Кузнецов – Минск: Вышэйшая школа, 1994. – 288с.
2. Кузнецов, Ю.Н. Математическое программирование. / Ю.Н. Кузнецов –Москва: Высшая школа, 1976. –203с.
3. Вентцель, Е.С. Элементы динамического программирования. / Е.С. Вентцель – М.: Наука, 1987. – 198с.
4. Карманов, В.Т. Математическое программирование. / В.Т Карманов. – М.:Наука, 1986. – 253с.
5. Аоки, М. Введение в методы оптимизации. / М. Аоки – М.: Наука, 1977. – 146с.
6. Калихман, И.Л. Динамическое программирование в примерах и задачах / И. Л. Калихман – М.: Высшая школа, 1979. – 125с.
7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. / Р.Беллман, С.Дрейфус – М.: Наука, 1965. – 234с.

ПРИЛОЖЕНИИЕ А

 

Рисунок 1 – Основная программа

 

Рисунок 2 – Процедура ввода данных

 

Рисунок 3 – Функция Поиск максимального  элемента (вектор, индекс_максимального_элемента) 

 

Рисунок 4 – Функция Z

 

Рисунок 5 – Функция F

 

Рисунок 5 – Процедура построения матрицы_результат 

Рисунок 6 – Процедура вывода данных

ПРИЛОЖЕНИЕ В

program Kurs;

uses

    Crt;

const

    MAX_MATRIX_ROWS_COUNT = 40;

    MAX_MATRIX_COLS_COUNT = 100;

    MAX_VECTOR_SIZE = MAX_MATRIX_COLS_COUNT;

type

    DMatrix = record

        rows : word;       

        cols : word;

        items : array[1..MAX_MATRIX_ROWS_COUNT,1..MAX_MATRIX_COLS_COUNT] of real;

        end;

    DVector = record

        size : word;

        items : array[1..MAX_VECTOR_SIZE] of real;

        end;

    TCell = record

        indexOfMax : word;

        value : real;

        end;

    TOutMatrix = record

        rows : word;

        cols : word;

        items : array[1..MAX_MATRIX_ROWS_COUNT, 1..MAX_MATRIX_COLS_COUNT] of TCell;

        end;

var

    step : real;

    effMatrix : DMatrix;

    distVector : DVector;

    outMatrix : TOutMatrix; 

{----------------------------------------------------------------------------}

procedure DataInput(path : string);

    var

        i : word;

        j : word;

        inFile : Text;

        elem : real;

        s : string;

    begin

   Assign(inFile, path);

    Reset(inFile);

    Writeln('Условие:');

    repeat

        Readln(inFile, s);

        Writeln(s);

    until (s = '');

    Writeln('Начальные данные:');

    i := 0;

    while not(Eof(inFile)) do

        begin

        inc(i);

        j := 0;

        Read(inFile, elem);

        distVector.items[i] := elem;

        Write(elem:3:0, ' | ');

        while not(Eoln(inFile)) do

            begin

            inc(j);

            Read(inFile, elem);

            effMatrix.items[i, j] := elem;

            Write(elem:3:0, '  ');

            end;

        Readln(inFile);

        Writeln;

        end;

    effMatrix.rows := i;

    effMatrix.cols := j;

    distVector.size := i;

    step := distVector.items[2] - distVector.items[1];

    Close(inFile);

    Writeln;

    end; 

{----------------------------------------------------------------------------}

function GetMaxItem(vector : DVector; var indexOfMax : word) : real;

    var

        i : word;

        max : real;

    begin

    max := -1e-20;

    for i := 1 to vector.size do

        if (vector.items[i] > max)

            then

                begin

                max := vector.items[i];

                indexOfMax := i;

                end;

    GetMaxItem := max;

    end; 

{----------------------------------------------------------------------------}

function FunctionZ(x : real; order : word) : real;

    var

        i : word;

    begin

    i := Round(x / step) + 1;

    FunctionZ := effMatrix.items[i, order];

    end; 

{----------------------------------------------------------------------------}

function FunctionF(x : real; order : word; var indexOfMax : word) : real;

    var

        i : word;

        a : real;

        b : real;

        vector : DVector;

    begin

    if (order = 1)

        then

           begin

            FunctionF := FunctionZ(x, 1);

            indexOfMax := 1;

            exit;

            end;

    vector.size := round(x / step) + 1;

    a := 0;

    b := x;

    for i := 1 to vector.size do

        begin

        vector.items[i] := FunctionZ(a, order) + FunctionF(b, order - 1, indexOfMax);

        a := a + step;

        b := b - step;

        end;

    FunctionF := GetMaxItem(vector, indexOfMax);

    end; 

{----------------------------------------------------------------------------}

procedure BuildOutMatrix;

    var

        i : word;

       j : word;

        indexOfMax : word;

    begin

    outMatrix.rows := effMatrix.rows;

    outMatrix.cols := effMatrix.cols;

    for j := 1 to outMatrix.cols do

        begin

        for i := 1 to outMatrix.rows do

            begin

            outMatrix.items[i, j].value := FunctionF(distVector.items[i], j, indexOfMax);

            outMatrix.items[i, j].indexOfMax := indexOfMax;

            end;

        end;

    end; 

{----------------------------------------------------------------------------}

procedure DataOutput(vector : DVector);

    var

        i : word;

    begin

    Writeln('Решение:');

    for i := 1 to vector.size do

        Writeln('x', i, ' = ', vector.items[i]:4:2);

    Write('Max = ');

    Writeln(outMatrix.items[outMatrix.rows, outMatrix.cols].value:4:0);

    Readln;

    end; 

{----------------------------------------------------------------------------}

var

    i, j : word;

    rightBoard : real;

    result : DVector;

    indexOfMax : word;

    value : real;

begin

ClrScr;

DataInput('data.txt');

BuildOutMatrix;

rightBoard := distVector.items[distVector.size];

result.size := effMatrix.cols;

for j := result.size downto 1 do

    if (rightBoard <= 0)

        then

            result.items[j] := 0

        else

            begin

            i := Round(rightBoard / step) + 1;

            indexOfMax := outMatrix.items[i, j].indexOfMax;

            value := (indexOfMax - 1) * step;

            result.items[j] := value;

            rightBoard := rightBoard - value;

            end;

DataOutput(result);

end.