Определение базисного (допустимого) решения

Перейдем от неравенств (2) к равенствам (4), введя дополнительные неотрицательные переменные x ₃, x ₄, x ₅. Тогда система ограничений будет иметь вид:

35 x ₁ + 30 x ₂ + x ₃ = 1050

30 x ₁ + 35x₂ + x ₄ = 1050 (4)

20 x ₁ + 40 x₂ + x ₅ = 800,

где x ₁, x ₂, x ₃, x ₄, x ₅ ≥ 0.

Дополнительные переменные воходят в целевую функцию Z с нулевыми коэффициентами:

Z =27,65· x ₁ + 37,6· x ₂ + 0· x + 0· x ₄ + 0· x ₅. (5)

Перепишем систему (4) и ЦФ (5) в виде:

x ₃ = 1050 - (35· x ₁ + 30· x ₂)

x ₄ = 1050 - (30· x ₁ + 35· x ₂) (6)

x ₅ = 800 - (20 x ₁ + 40· x ₂)

Z = 0 – (- 27,65· x ₁ – 37,6· x ₂ - 0· x ₃ - 0· x ₄ - 0· x ₅)

Переменные x ₃, x ₄, x ₅ – базисные, x ₁, x ₂ – небазисные (свободные). Положив x ₁= x ₂= 0, получим значения базисных переменных: x ₃= 1050, x ₄= 1050, x ₅ = 800.

Таким образом, базисное решение системы (0, 0, 1050, 1050, 800). Для этих значений переменных целевая функция примет значение Z = 0.

Определение оптимального решения

Заполним симплекс-таблицу в соответствии с полученной моделью (6), как показано в табл. 3. (Указанные ниже вычисления удобно и проще выполнять в MS Excel.)

Таблица 3 (СТ-1)

1. Из отрицательных элементов последней строки симплекс-таблицы С-Т1 (табл. 3), соответствующих переменным x ₁÷ x ₂, выберем максимальный по модулю элемент. Им является элемент -37,6, который соответствует переменной x ₂. следовательно, небазисная переменная x ₂ должна быть введена в базис.

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

1050/30 = 35,

1050/35 = 30,

800/40 = 20.

Запишем частные от деления во вспомогательный столбец δ (табл. 4).

Таблица 4 (СТ-1)

3. Выберем элемент, который дает минимальное частное от деления: 20. Он соответствует третьей строке с базисной переменной x ₅. Следовательно, переменная x ₅ должна быть выведена из базиса, а переменная x ₂ введена. Элемент, находящийся на пересечении выбранной строки и выбранного столбца называется разрешающим элементом: 40 (табл. 4).

4. Разделим элементы третьей строки на разрешающий элемент (на 40). Результат запишем в третью строку симплекс-таблицы С-Т2 (табл. 5). Таблица 5 (СТ-2)

4. Построение первой строки С-Т2:

элементы полученной третьей строки С-Т2 умножим на коэффициент первого элемента выделенного столбца С-Т1 (на 30) и вычтем из соответствующих элементов первой строки СТ-1. Получим первую строку С-Т2 (табл. 6).

5. Построение второй строки С-Т2:

элементы полученной третьей строки С-Т2 умножим на коэффициент второго элемента выделенного столбца С-Т1 (на 35) и вычтем из соответствующих элементов второй строки СТ-1. Получим вторую строку С-Т2 (табл. 6).

6. Построение четвертой строки С-Т2:

элементы полученной третьей строки С-Т2 умножим на коэффициент четвертого элемента выделенного столбца С-Т1 (на -37,6) и вычтем из соответствующих элементов четвертой строки СТ-1. Получим четвертую строку С-Т2 (табл. 6).

Таблица 6 (СТ-2)

7. Проверка, является ли полученное решение (табл. 6) допустимым.

Если в столбце значений базисныхпеременных (свободных членов) все элементы неотрицательные, полученное решение является допустимым.

Полученное решение (табл. 6) является допустимым, так как в столбце свободных членов все значения базисных переменных положительные.

8. Проверка на оптимальность

Целевая функция имеет максимальное значение, если все коэффициенты в строке целевой функции будут положительными. Полученное решение (табл. 6) не является оптимальным, так как имеется один отрицательный элемент, равный -8,85.

Переходим к выполнению пункта 1.

1. Из отрицательных элементов последней строки симплекс-таблицы С-Т2 (табл. 7), соответствующих переменным x ₁÷ x ₂, выберем максимальный по модулю элемент. Им является элемент -8,85 (он единственный), который соответствует переменной x ₁. Следовательно, небазисная переменная x ₁ должна быть введена в базис. Таблица 7 (СТ-2)

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

450/20 = 22,5

350/12,5 = 28

20/0,5 = 40.

3. Выберем элемент, который дает минимальное частное от деления: (22,5). Он соответствует первой строке с базисной переменной x ₃. Следовательно, переменная x ₃ должна быть выведена из базиса, а переменная x ₁ введена. Элемент, находящийся на пересечении выбранной строки и выбранного столбца является разрешающим элементом: 20.

4. Разделим элементы первой строки на разрешающий элемент. Результат запишем в первую строку симплекс-таблицы С-Т3 (табл. 8).

Таблица 8 (СТ-3)

5. Построение второй строки С-Т3:

элементы полученной первой строки С-Т3 умножим на коэффициент второго элемента выделенного столбца С-Т2 (на 12,5) и вычтем из соответствующих элементов второй строки СТ-2. Получим вторую строку С-Т3 (табл. 9).

Таблица 9 (СТ-3)

6. Построение третьей строки С-Т3:

элементы полученной первой строки С-Т3 умножим на коэффициент третьего элемента выделенного столбца С-Т2 (на 0,5) и вычтем из соответствующих элементов третьей строки СТ-2. Получим третью строку С-Т3 (табл.9).

7. Построение четвертой строки С-Т3:

элементы полученной первой строки С-Т3 умножим на коэффициент четвертого элемента выделенного столбца С-Т2 (на -8,85) и вычтем из соответствующих элементов четвертой строки СТ-2. Получим четвертую строку С-Т3 (табл. 9).

7. Проверка, является ли полученное решение (табл. 9) допустимым. В столбце значений базисныхпеременных (свободных членов) все элементы неотрицательные, полученное решение является допустимым.

8. Проверка на оптимальность.

Целевая функция имеет максимальное значение, если все коэффициенты в строке целевой функции будут положительными. Полученное решение (табл. 9) является оптимальным, так как в четвертой строке нет ни одного отрицательного элемента.

Таблица. 10 (СТ-3)

Максимальное значение целевой функции Z = 951,13 достигается при значениях x ₁ = 22,5, x ₂ = 8,75 (табл. 10). Результат выделен заливкой.