Определение оптимального решения на основе симплекс-таблиц

1. Строится исходная симплекс-таблица. Общий вид симплекс-таблицы

показан в табл. 1.

Таблица 1

Базис х 1 х 2 … хп х п+ 1 хn+ 2 … хк Решение

L – с 1 – с 2 … –сп 0 0 0 0 0

х п +1 а 11 а 12 … а 1 п 1 0 0 0 b 1

хn +2 а 21 а 22 … а 1 п 0 1 0 0 b 2

… … … … … … … … … …

хк ат 1 ат2 … атп 0 0 0 1 bт

Симплекс-таблица строится по следующим правилам:

• в первой строке перечисляются все переменные задачи, как исходные

(х 1, х 2,..., хn), так и дополнительные, введенные при приведении к

канонической форме (хn+ 1, хn+ 2,..., хk). Для задач, содержащих только

ограничения «меньше или равно», дополнительные переменные хn+ 1, хn+ 2,...,

хk – это остаточные переменные;

• в первой колонке таблицы («Базис») перечисляются переменные,

составляющие начальный базис задачи. Их количество всегда равно

количеству ограничений. Для задач, содержащих только ограничения

«меньше или равно», начальный базис состоит из остаточных переменных

хn+ 1, хn+ 2,..., хk. В этой же колонке указывается обозначение целевой функции

L;

• в строке целевой функции указываются коэффициенты целевой

функции с обратным знаком. Для переменных, не входящих в целевую

функцию (например, для остаточных переменных хn+ 1, хn+ 2,..., хk) указываются

нули;

• в строках базисных переменных указываются коэффициенты

ограничений, в которые входят эти переменные. Для переменных, не

входящих в ограничения, указываются нулевые коэффициенты;

• в последнем столбце («Решение») указываются значения базисных

переменных (они равны правым частям ограничений), а также начальное

значение целевой функции (0).

Если таблица построена правильно, то в столбце каждой базисной

переменной должна присутствовать только одна единица (в строке

ограничения, в которое входит эта переменная); остальные коэффициенты –

нулевые.

2. Проверяется условие окончания решения задачи. Если в строке

целевой функции (L -строке) все коэффициенты неотрицательны, это

означает, что оптимальное решение найдено. В противном случае

выполняется следующий шаг.

3. Определяется переменная для включения в базис. В качестве такой

переменной выбирается переменная, которой соответствует максимальный

по модулю отрицательный коэффициент в L - строке. Включение в базис

(т.е. увеличение) такой переменной приводит к наиболее быстрому росту

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

называется ведущим (разрешающим).

3Вычислить определитель методом треугольников.

БИЛЕТ 23

1)Метод Крамера (формулы Крамера) — способ решения систем линейных уравнений, у которых количество переменных равно количеству уравнений. Применение метода Крамера возможно, если определитель, составленный из коэффициентов при переменных, не равен нулю. В таком случае система имеет единственное решение. Создан Габриэлем Крамером в 1751 году.

Для системы линейных уравнений с неизвестными (над произвольным полем)

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

(i-ый столбец матрицы системы заменяется столбцом свободных членов).

В другой форме правило Крамера формулируется так: для любых коэффициентов c1, c2, …, cn справедливо равенство:

В этой форме формула Крамера справедлива без предположения, что отлично от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы и, либо набор состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

3) Задание. Вычислить определитель

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

Определитель равен нулю, так как вторая и третья строки являются пропорциональными.

 

Ответ.

БИЛЕТ 24