Исследование математической модели. Построенная математическая модель может быть исследована с помощью одного из методов линейного программирования — симплекс-метода или каким-либо другим.

Для возможности применения к построенной математической модели симплекс-метода необходимо иметь вместо системы неравенств систему равенств. Для этого в каждое из неравенств введем фиктивное неизвестное (дополнительное неизвестное) Тогда математическая модель может быть записана в таком виде:

Вводимые дополнительные неизвестные образуют начальный базис (базисные переменные). Все другие переменные называются небазис­ными. В симплекс-методе вводится также понятие — базисное решение, в котором все небазисные переменные принимаются равными 0, а значения базисных переменных определяются из решения системы равенств. На на­чальном этапе базисное решение

() будет выглядеть так (0,0,0,0,1,1,1).

Решение задачи сводится к определению базисных решений с помощью составления последовательности симплекс-таблиц (табл. 3.3), обеспечи­вающих направленное движение к искомому оптимуму.

Для облегчения расчетов вся исходная информация и промежуточные расчеты представляются в виде, так называемых, симплекс-таблиц (табл. 3.3,3.4, и т.д.)

Алгоритм симплекс-метода включает несколько этапов:.1. Проверка базисного решения () на оптималь­ность. Если все коэффициенты целевой функции F (последняя строка табл. 3.3) при небазисных переменных неположительные, то исходный базис опти­мален, в нашей задаче для начального базисного решения (0, 0,0,0,1, 1, 1) все коэффициенты при небазисных переменных для базисного решения поло­жительны, значит решение не оптимально. Значение же целевой функции для этого базисного решения равно 0.

2. Проверка задачи на наличие решения. Ваш над каким-либо положи­тельным коэффициентом при небазисной переменной в целевой функции нет ни одного столбца с неположительным коэффициентом, то задача имеет решение. Для данного класса задач решение всегда имеется.

3. Выбор из небазисных переменных той, которая при введении ее в ба­зис увеличивает значение целевой функции. Обычно выбирают небазисную переменную с наибольшим положительным коэффициентом в последней строке.

В нашей задаче можно выбрать любую из Выберем х₁ от­метим ее звездочкой.

4. Определение базисной переменной, которая должна быть выведена из базиса. Для этого определяем минимальное частное от деления соответ­ствующих свободных членов и положительных коэффициентов столбца отмеченного звездочкой. Имеем: 1/0,25; 1/0,20; 1/0,24. Минимальное част­ное соответствует базисной переменной х₅, эту строку отмечаем звездоч­кой. Коэффициент 0,25, находящийся на пересечении строки и столбца, отмеченных звездочками, называется разрешающим элементом (см. жирное число в табл. 3.3).

5. Ввод в базис небазисной переменной и выражение ее через новые не­базисные переменные. В нашем примере вводим х) и выражаем ее через новый набор небазисных переменных - Для этого все коэффи­циенты строки, отмеченной звездочкой, делим на разрешающий элемент, и результаты расчета записываем в новую симплекс-таблицу (табл. 3.4) в строку выведенной из базиса переменной.

6. Выражение остальных базисных переменных и целевой функции че­рез новые небазисные переменные. В нашем примере базисные переменные х6 х7 выражаем через новый набор небазисных переменных –x5,x₂,x₃, x₄. Для этого коэффициенты в строке с новой базисной переменной в новой таблице (в нашей задаче при х,) умножается на такое число, чтобы после сложения с преобразуемой строкой табл. 3.3 в столбце X/ появился 0.

В соответствии со сказанным, для получения коэффициентов второй стро­ки (см. табл. 3.4) умножаем коэффициенты строки х1 на множитель - 0,20.

Множитель для каждой преобразуемой переменной и целевой функции (x₆, х₇, F) в новой табл. 3.4, равен обратной величине коэффициента, стоя­щего на пересечении преобразуемой переменной и вводимой в базис пере­менной.

Складываем результаты умножения с соответствующими коэффициентами второй строки табл. 3.3. Результаты сложения заносим во вторую строку табл. 3.4, и т.д.

После заполнения табл. 3.4 весь расчет начинается сначала с п. 1. И так до тех пор, пока не будет найдено оптимальное решение.

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

Решение есть.

В качестве вводимой в базис переменной выберем х₄, которой соответ­ствует наибольший положительный коэффициент. Отмечаем столбец х₄ звездочкой

В качестве выводимой из базиса переменной берем х7 так как для нее частное от деления свободного члена на коэффициент при x7 минимально.

Отмечаем строку звездочкой. Разрешающий элемент равен 0,037 (см. жир­ное число в табл. 3.4).

Затем составляется новая симплекс-таблица и так до тех пор, пока в по­следней строке коэффициенты при небазисных переменных будут неположительные.

В системе из и уравнений с т неизвестными (и < т) общее число мак­симально допустимых базисных решений равно числу сочетаний из n по m.

В нашей задаче максимально допустимое число базисных решений бу­дет равно:

Поиск оптимального решения заключается в направленном переходе от одного допустимого базисного решения к другому в направлении максими­зации целевой функции. Общее число итераций в симплекс-методе ограни­чено сверху и, следовательно, оптимальное решение может быть достигну­то за конечное число шагов, обычно в несколько раз меньшее, чем макси­мально допустимое число итераций.

Для снижения трудоемкости определения оптимального комплекта ма­шин в условиях неполной определенности целесообразно использовать электронно-вычислительную технику, которая не только снижает трудоем­кость требуемых вычислений, но и резко сокращает время поиска.

Ниже приводится программа, написанная на языке программирования Фортран, для определения оптимального комплекта машин в условиях непол­ной определенности (прогр. 3.2).

В результате расчета на печать выводятся: вероятности использования каждого комплекта машин P(J) и минимальные суммарные затраты при использовании оптимального комплекта машин. В условиях неполной оп­ределенности.