Свойства класс TSimplex

Класс TSimplex имеет следующие свойства:

– n, m: integer – соответственно число свободных и число базисных переменных;

– w, b:array of extended – массивы, содержащие соответственно свободные члены и коэффициенты целевой функции;

– wb: extended – свободный член целевой функции;

– FTit, BTit: array of string – соответственно названия свободных и базисных переменых;

– a: array of array of extended – матрица коэффициентов линейных функций базисных переменых;

– result: TNextResult – результат последней операции;

– ir, jr: integer – соответственно разрешающая строка и разрешающий столбец;

– history: TStack – история о предыдущих операциях, позволяет вернуться назад.

Для полной ячности надо описять тип TNextResult и класс TStack.

Тип TNextResult описывает результат последней операции.

TNextResult = (nrFound=0, nrOporOk, nrOporFail, nrOptimOk, nrOptimFail, nrStackEmputy),

где nrFound – найдено решение;

nrOporOk – найден способ, как заменит базис, чтобы приблизиться к опорному решению;

nrOporFail – невозможно найти опорное решение, т.е. и вся задача не имеет решения;

nrOptimOk – найден способ, как заменит базис, чтобы приблизиться к оптимальному решению;

nrOptimFail – невозможно найти оптимальное решение, т.е. и вся задача не имеет решения;

nrStackEmputy – стек с историей о предыдущих ходах пуст, т.е. невозможно сделать шаг назад.

Клас TStack – стек, хранящий историю о сделанных шагах, позволяет откатить положение вычисления назад.

TIJ = record i, j: integer end;

TStack = class

top: integer;

stackIJ: array [0..1000] of TIJ;

end;

Методы класса TSimplex

Класс TSimplex имеет следующие методы:

– procedure newBase – позволяет перейти к новому базису, причем разрешающая строка и разрешающий столбец указывается в свойствах ir, jr;

– function next: TNextResult – находит следующий шаг к опрорному решению или если оно найдено к оптимальному решению, причем сохраняет в свойстве history проделанный путь;

– procedure back – возвращается на один шаг назад, используя свойство history.

Решение

На основе начальных данных математической модели нашей задачи (2.6), построим симплекс таблицу в соответствии с рисунком 2.1.

Рисунок 2.1 – Опорное решение

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

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

Выберем разрешающим столбцом x₁ т.к. коэффициентов целевой функции в этом столбце больше нуля и больше всех остальных положительных коэффициентов целевой функции, он равен 10.

Выберем разрешающей строкой y₂т. к. отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно (0 / 0,6 = 0).

Выделим разрешающий столбец, строку и элемент.

Переедем к новому базису в соответствии с рисунком 2.2 по правилу, высчитывая новые коэффициенты по правилу прямоугольника:

Рисунок 2.2 – Первый шаг

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

Выберем разрешающим столбцом x₃ т.к. коэффициентов целевой функции в этом столбце больше нуля и больше всех остальных положительных коэффициентов целевой функции, он равен 13,66.

Выберем разрешающей строкой y₄ т.к. отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно (0 / 13,66 = 0).

Выделим разрешающий столбец, строку и элемент.

Переедем к новому базису в соответствии с рисунком 2.3 по правилу, высчитывая новые коэффициенты по правилу прямоугольника:

Рисунок 2.3 – Второй шаг

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

Выберем разрешающим столбцом x₂ т.к. коэффициентов целевой функции в этом столбце больше нуля и больше всех остальных положительных коэффициентов целевой функции, он равен 37.

Выберем разрешающей строкой y₁ т.к. отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно (500000 / 5 = 100000).

Выделим разрешающий столбец, строку и элемент.

Переедем к новому базису в соответствии с рисунком 2.4 по правилу, высчитывая новые коэффициенты по правилу прямоугольника:

Рисунок 2.4 – Оптимальное решение

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

Ответ:

Заключение

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