Для откорма свиней на ферме в еженедельный рацион каждой свиньи требуется включать не менее

Для откорма свиней на ферме в еженедельный рацион каждой свиньи требуется включать не менее 6 ед. питательного вещества А, 8 ед. вещества В и 12 ед. вещества С. Для откорма можно использовать три вида кормов. Данные о содержании питательных веществ в одной весовой единице каждого из них приведены в таблице. Требуется составить наиболее дешевый рацион, если одна весовая единица корма I стоит 2 ден. ед., корма II – 3 ден. ед., корма III – 2,5 ден. ед.

Пусть необходимо взять корма I – х1, корма II – х2, корма III – х3, тогда ограничения
по веществу А:2x1+x2+3x3≥6,по веществу В: x1+2x2+1.5x3≥8,
по веществу С:3x1+4x2+2x3≥12,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0.
Стоимость рациона определяется как F(X)=2x1+3x2+2.5x3, который необходимо минимизировать.
Математическая модель имеет вид:
F(X) = 2x1+3x2+2.5x3 → min 2x1+x2+3x3≥6,x1+2x2+1.5x3≥8,3x1+4x2+2x3≥12,
х1>0,
х2>0,
х3>0.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.
2x1+x2+3x3-x4 = 6
x1+2x2+1.5x3-x5 = 8
3x1+4x2+2x3-x6 = 12
Введем искусственные переменные x: в 1-м равенстве вводим переменную x7; в 2-м равенстве вводим переменную x8; в 3-м равенстве вводим переменную x9;
2x1+x2+3x3-x4+x7 = 6
x1+2x2+1.5x3-x5+x8 = 8
3x1+4x2+2x3-x6+x9 = 12
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = 2x1+3x2+2.5x3+Mx7+Mx8+Mx9 → min
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x7 = 6-2x1-x2-3x3+x4
x8 = 8-x1-2x2-1.5x3+x5
x9 = 12-3x1-4x2-2x3+x6
которые подставим в целевую функцию:
F(X) = 2x1 + 3x2 + 2.5x3 + M(6-2x1-x2-3x3+x4) + M(8-x1-2x2-1.5x3+x5) +
+ M(12-3x1-4x2-2x3+x6) → min
илиF(X) = (2-6M)x1+(3-7M)x2+(2.5-6.5M)x3+(M)x4+(M)x5+(M)x6+(26M) → min
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
2 1 3 -1 0 0 1 0 0
1 2 1.5 0 -1 0 0 1 0
3 4 2 0 0 -1 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x7, x8, x9
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,0,0,0,6,8,12)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x7 6 2 1 3 -1 0 0 1 0 0
x8 8 1 2 1.5 0 -1 0 0 1 0
x9 12 3 4 2 0 0 -1 0 0 1
F(X0) 26M -2+6M -3+7M -2.5 -M -M -M 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1

. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:
min (6 : 1 , 8 : 2 , 12 : 4 ) = 3
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9 min
x7 6 2 1 3 -1 0 0 1 0 0 6
x8 8 1 2 1.5 0 -1 0 0 1 0 4
x9 12 3 4 2 0 0 -1 0 0 1 3
F(X1) 26M -2+6M -3+7M -2.5 -M -M -M 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x9 плана 0 на разрешающий элемент РЭ=4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СТЭ - (А∙В)/РЭ
СТЭ - элемент старого плана,
РЭ - разрешающий элемент (4),
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x7 3 5/4 0 5/2 -1 0 1/4 1 0 -1/4
x8 2 -1/2 0 0.5 0 -1 1/2 0 1 -1/2
x2 3 3/4 1 1/2 0 0 -1/4 0 0 1/4
F(X1) 9+5M 1/4+3/4M 0 -1+3M -M -M -3/4+3/4M 0 0 3/4-13/4M
Итерация №1.
1