Математические методы принятия управленческих решений

Условие задачи.

F= 10 x1+7x2+4x3―>max1+3x2+2x3 ≤ 12

x1+4x2+3x3 ≤ 60

x1+6x2+3x3 ≤ 40

x1-3≥0

. Расчеты вручную симплекс-методом с необходимыми пояснениями

Решение

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

· Целевая функция стремится к max;

· Ограничения в задаче должны иметь вид равенств; если ограничения имеют знак ≤, то в его левую часть необходимо добавить новую дополнительную переменную, такую, чтобы получилось равенство. Вновь введенную дополнительную переменную также ввести в целевую функцию с нулевыми коэффициентами;

· Условие неотрицательности распространить и на дополнительные переменные.

F= 10 x1+7x2+4x3 + х4+х5+х6―>max1+3x2+2x3 + х4 = 12

x1+4x2+3x3 + х5 = 60

x1+6x2+3x3 +х6 = 40

x1-6≥0

. Нахождение исходного базисного плана задачи линейного программирования.

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

Для нахождения такого базисного плана необходимо в каждом уравнении выбрать одну переменную с коэффициентом 1 и который не входит больше ни в какие уравнения. Остальные переменные будут свободные и их значение можно принять за 0.

m = 3, число уравнений;

n = 6, число неизвестных,

так как n>m, то система имеет бесчисленное множество решений.

В данном случае m - n = 6-3=3 неизвестных можно принять за нулевые.

х4 = 12

х5 = 60 исходный базисный план

х6 = 40

x1 = 0

x2 = 0 свободные переменные

x3 = 0

следовательно F = 0

. Построение исходного базисного плана

Итерация 0

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

Выполняется по последней строке таблицы. Если в последней строке все коэффициенты ≤ 0, то план является оптимальным.

В нашем случае (10, 7, 4 > 0), следовательно, план является не оптимальным.

. Выбираем переменную для включения в базисный план max (10, 7, 4) = 10, следовательно х1 включить в базис.

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

min (12/1, 60/3, 40/5) = 40/5, следовательно х6 исключить из базиса.

. Составляем новую симплексную таблицу

Итерация 1