Вариант 25. Контрольное задание по теме 3 Линейное программирование. 3
 Скачать 1.21 Mb.
|
|
2. Решаем задачу по критерию Z2 Z2= x1+ 3x2– 2x3→min; x1+ 3x2+2x3≥1, 2x1–x2+x3≤25, x1+ 2x2≤24,  x1, x2, x3 ≥0. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≥) вводим базисную переменную x7 со знаком минус. 1x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 + 0x7 = 1 2x1-1x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 = 25 1x1 + 2x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 = 24 25x1 + 1x2-3x3 + 0x4 + 0x5 + 0x6-1x7 = 370.6 Введем искусственные переменные x: в 1-м равенстве вводим переменную x8; в 4-м равенстве вводим переменную x9; 1x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 1 2x1-1x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 25 1x1 + 2x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 24 25x1 + 1x2-3x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 1x9 = 370.6 Для постановки задачи на минимум целевую функцию запишем так: F(X) = x1+3x2-2x3+Mx8+Mx9 → min За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Из уравнений выражаем искусственные переменные: x8 = 1-x1-3x2-2x3+x4 x9 = 370.6-25x1-x2+3x3+x7 которые подставим в целевую функцию: F(X) = x1 + 3x2-2x3 + M(1-x1-3x2-2x3+x4) + M(370.6-25x1-x2+3x3+x7) → min или F(X) = (1-26M)x1+(3-4M)x2+(-2+M)x3+(M)x4+(M)x7+(371.6M) → min Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных: x8, x5, x6, x9. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,25,24,0,1,370.6)
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x8 в план 1 войдет переменная x1 Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=1 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x1 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 . Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
После преобразований получаем новую таблицу:
|