Решение задачи традиционными методами. Алгоритм решения. Для решения данной задачи разработано много способов

Алгоритм решения. Для решения данной задачи разработано много способов. Рассмотрим один из наиболее распространенных – симплекс-метод Для его использования необходимо определить начальный базис, то есть решение, удовлетворяющее системе равенств (3.3.2.2). В некоторых задачах базис просматривается непосредственно, но во многих его необходимо найти.

В данной задаче базис определить легко. Для этого требуется взять m неизвестных – по числу уравнений в системе (3.3.2.2). В нашей системе уравнений (т=3) это х₅, х₆, х₇, которые и выражаем через оставшиеся неизвестные х₁,х₂,х₃,х₄.

Систему уравнений необходимо записать в следующем виде:

x₅=15–(3х₁+5х₂+2х₃+7х₄)

x₆=9–(4х₁+3х₂+3х₃+5х₄) (3.3.2.5)

х₇=30–(5x_t+6x₂+4x₃+8х₄)

Переменные, находящиеся в левой части системы, называются базисными (основными), а находящиеся справа – небазисными (неосновными). Для определения значений базисных переменных х₅, х₆, х₇ необходимо приравнять к нулю небазисные x_1, х₂, х₃, x₄ и подставить их в систему уравнений (3.3.2.5). Полученное таким образом решение является базисным. В нашей задаче оно будет выглядеть следующим образом:

(Х₁, Х₂, Х₃, Х₄, Х₅, Х₆, Х₇)

(0, 0, 0, 0, 15, 9, 30)

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

1. Заполнение исходной симплекс-таблицы. В соответствии с полученной системой уравнений и критерием оптимизации заполним исходную симплекс-таблицу (табл. 3.3.2.3).

2. Проверка базисного решения на оптимальность. Просматриваются знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации) – последняя строка табл. 3.3.2.3.

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

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

4. Выбор из небазисных переменных той, которая способна при введении ее в базис увеличить значение целевой функции. Наиболее простой и чаще всего используемый способ состоит в выборе той небазисной переменной, которой соответствует наибольший положительный коэффициент в целевой функции. В нашей задаче это переменная х₂ (наибольший положительный коэффициент равен 50). Значит, х₂ необходимо ввести в базис.

5. Определение базисной переменной, которая должна быть выведена из базиса. Для всех положительных коэффициентов в системе уравнений определяется отношение свободного члена уравнения к коэффициенту при вводимой в базис переменной. Для нашей задачи это будут следующие отношения: 15/5=3; 9/3=3; 30/6=5.

Минимальное из полученных отношений указывает строку и базисную переменную, которая должна быть выведена из базиса. При наличии нескольких одинаковых отношений берется любое. В нашей задаче выведем из базиса переменную х₅.

6. Представление новой базисной переменной через небазисные. Строится новая симплекс-таблица (табл. 3.3.2.4). Отмечается звездочкой строка и столбец в предыдущей симплекс-таблице (табл. 3.3.2.3) для выводимой из базиса и для вводимой в него переменной.

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

Таблица 3.3.2.3

Таблица 3.3.2.4

В нашей задаче на первой итерации разрешающий элемент равен 5 (табл. 3.3.2.3). Результаты деления каждого элемента строки, отмеченной звездочкой, на разрешающий коэффициент заносятся в строку 1 новой таблицы (табл. 3.3.2.4). 7. Представление остальных базисных переменных и целевой функции через новый набор небазисных переменных. Для этого коэффициенты в последней таблице при новой базисной переменной умножаются на такое число, чтобы после сложения с преобразуемой строкой предыдущей таблицы в столбце новой таблицы при базисной переменной появился ноль. Результаты сложения заносятся в новую симплекс-таблицу. Исходя из этого, для получения коэффициентов второй строки в новой таблице (табл. 3.3.2.4) умножаем коэффициенты при новой базисной переменной х₂ на число –3, складываем с соответствующими коэффициентами второй строки предыдущей симплекс-таблицы (табл. 3.3.2.3) и результаты расчета заносим во вторую строку новой таблицы (табл. 3.3.2.4).

Аналогичные преобразования проводим и для других строк. После этого выполняем новую итерацию. Цикл расчета начинается с этапа 2 и повторяется до нахождения оптимального решения.

Поскольку в последней строке табл. 3.3.2.4 не все коэффициенты целевой функции при небазисных переменных положительны, то решение неоптимально; следовательно, выполняется следующий итерационный цикл расчета и строится новая симплекс-таблица (табл. 3.3.2.5). В качестве вводимой в базис небазисной переменной принимаем х_а (или х,), имеющую наибольший положительный коэффициент. Отмечаем звездочкой столбец х₃. В качестве выводимой из базис переменной берем х₆, так как для нее частное от деления свободного члена на соответствующий положительный коэффициент минимально. Разрешающий множитель равен 9/5. Результаты расчета представлены в табл. 3.3.2.5

Таблица 3.3.2.5

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

(х₁, х₂, х₃, х₄, х₅, х₆, х₇)

(0, 3, 0, 0, 0, 0, 12)

Из полученных результатов следует, что предприятию наиболее выгодно изготовление только изделия И₂, производство которого обеспечит максимальную прибыль в размере Ymax=150. При этом материальные и трудовые ресурсы будут задействованы полностью, а финансовые – недоиспользованы на 12 единиц.