Решение задачи с помощью прямых расчетов, согласно указанному методу

Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.

Приведем систему ограничений к системе неравенств смысла ?, умножив соответствующие строки на (-1).

Определим минимальное значение целевой функции.

F (X) = 5×1 + 6×2 + 7×3 + 4×4.

при следующих условияхограничений.

• — x1 — x2 — 4×4?-26
• — 2×1 — 3×3 — 5×4?-30
• — x1 — 2×2 — 4×3 — 6×4?-24

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x5. В 2-м неравенстве смысла (?) вводим базисную переменную x6. В 3-м неравенстве смысла (?) вводим базисную переменную x7.

• -1×1−1×2 + 0×3−4×4 + 1×5 + 0×6 + 0×7 = -26
• -2×1 + 0×2−3×3−5×4 + 0×5 + 1×6 + 0×7 = -30
• -1×1−2×2−4×3−6×4 + 0×5 + 0×6 + 1×7 = -24

Матрица коэффициентов A = a (ij) этой системы уравнений имеет вид:

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

Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x5, x6, x7.

Полагая, что свободные переменные равны 0, получим первый опорный план.

Базисное решение называется допустимым, если оно неотрицательно.

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

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

2. Определение новой свободной переменной.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 2-ая строка, а переменную x6 следует вывести из базиса.

3. Определение новой базисной переменной.

Минимальное значение и соответствует 4-му столбцу, т. е. переменную x4 необходимо ввести в базис.

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

4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Представим расчет каждого элемента в виде таблицы:

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

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

2. Определение новой свободной переменной.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 1-ая строка, а переменную x5 следует вывести из базиса.

3. Определение новой базисной переменной.

Минимальное значение и соответствует 6-му столбцу, т. е. переменную x6 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-4/5).

4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Представим расчет каждого элемента в виде таблицы:

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

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

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так:

x4 = 61/2.

F (X) = 4*6 ½ = 26.

Анализ полученных результатов

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

Минимальная стоимость данного вещества F (X) = 4*6 ½ = 26.