( Столбец коэффициентов ограничений, соответствующий

переменной R

(2/5 -1/5

( Столбец коэффициентов ! хг правых частей ограничений ) \х,

1/5 2/5

2/5 -1/5 1/5 2/5

-1/51 2/5

12/5 26/5

Теперь применим формулу 2 для вычисления коэффициентов в г-строке. Оптимальные значения двойственных переменных у2) =(29/5,-2/5) вычислены в примере 4.2.1 двумя различными методами. Эти значения используются для вычисления коэффициентов в г-строке.

Коэффициент при xi = y1 + 2y2-5 = 29/5 + 2х(-2/5) -5 = 0. Коэффициент при х2 = 2j/, - у2 - 12 = 2х(29/5) - (-2/5) -12 = 0. Коэффициент при х3 = г/, + Зу2 - 4 = 29/5 + Зх(-2/5) - 4 = 3/5. Коэффициент при xt = уг - 0 = 29/5 - 0 = 29/5. Коэффициент при R = y2- (-М) = -2/5 - (-М) = -2/5 + М.

Важно отметить, что формулы 1 и 2 можно применять на любой симплекс-итерации как к прямой, так и к двойственной задаче.

УПРАЖНЕНИЯ 4.2.4

1. В задаче из примера 4.1.2 с помощью программы TORA (выполнив команду Iterations oM-method) определите элементы симплекс-таблицы первой итерации. Затем с помощью формул 1 и 2 найдите значения всех элементов оптимальной симплекс-таблицы.

2. Дана следующая задача ЛП.

Максимизировать г = 4лс1 + 14х2

при ограничениях

2x1 + 7x2 + x3 = 21, 1хх + 2хг + xt = 2l,

jc х2, JCg, х4 0.

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

f 1/7 0 ,-2/7 1,

(0 1/2 1 -7/2 J

а) Базисные переменные (х2, xt), обратная матрица:

Ь) Базисные переменные (х2, хг), обратная матрица =

ч * г7/45 -2/451

c) Базисные переменные (х2, XJ, обратная матрица = I

( 1/2 0\

d) Базисные переменные (лс xt), обратная матрица =

1-7/2 \/

3. Дана следующая задача ЛП.

Максимизировать z = Зле, + 2х2 + 5х3

при ограничениях

х, + 2хг + х3 + х4 = 30, Зл + гл + хбО, х, + 4х2 + х6 = 20, х х2, х3, х4, х5, х6 > 0. Проверьте оптимальность и допустимость следующих базисных решений.

(I -1/2 0)

а) Базисные переменные (х4, х3, х6), обратная матрица =

0 1/2 0 0 0 1

Ь) Базисные переменные (х2, х3, х,), обратная матрица =

с) Базисные переменные (х2, х3, х6), обратная матрица =

1/4 -1/8 1/8 4

3/2 -1/4 -3/4

1-1 1/2 1/2,

1/2 -1/4 0)

0 1/2 0

-2 1 1

4. Дана следующая задача ЛП.

Минимизировать z - 2х, + х2

при ограничениях

Зхг + х2 - х3 = 3, 4х, + Зх2 - х4 = 6, х, + 2х2 + х6 = 3, л- х2, х3, х4, х5 0.

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

3/5 -1/5 0

Базисные переменные (хр х2, х6), обратная матрица = -4/5 3/5 0

[ 1 -11,

5. Дана следующая задача ЛП.

Максимизировать z = 5х, + 12х2 + 4х3

при ограничениях

х, + 2х2 + х3 + х4 = 10, 2х,-х2 + 3х3 = 2, x х2, х3, х4 0.

а) Найдите наилучшее решение среди следующих базисных допустимых решений.

(\ -1/3

<° i/з/

2/5 -1/5 .1/5 2/5 У

i) Базисные переменные (х4, х3), обратная матрица = и) Базисные переменные (х2, х,), обратная матрица =

Ш) Базисные переменные (х2, х,), обратная матрица =

Ь) Присутствует ли среди них оптимальное решение? 6. В следующей таблице представлено оптимальное решение задачи максимизации с тремя ограничениями типа < и неотрицательными переменными х, и х2. Переменные х3, х4 и xs являются дополнительными (остаточными) переменными, соответствующими ограничениям задачи. Двумя различными способами, используя целевые функции прямой и двойственной задач, найдите оптимальное значение целевой функции исходной задачи.

7. Рассмотрите следующую задачу ЛП.

Максимизировать z = 5л:, + 2х2 + Зх3

при ограничениях

л:, + 5х2 + 2х3 <Ь

*i 5х2 ~ &хг Ь2>

х х2, ха>0.

Определите значения констант Ь, и Ь2, при которых симплекс-таблица с оптимальным решением имеет следующий вид.

Константы аЬ, с, d и е можно найти на основе данных исходной задачи и условий оптимальности и допустимости решения, представленного в симплекс-таблице.

a) Найдите значения правых частей неравенств исходной задачи, т.е. константы Ь, и Ь2.

b) Найдите значения констант а, Ь, с, d, е.

c) Найдите оптимальное решение двойственной задачи. 8. Дана следующая задача ЛП.

Максимизировать z = 2хг + 4х2 + 4х3 - 3xt при ограничениях

х, + х2 + х3 = 4, х, + 4х2 + х4 = 8, х х2, х3, х4>0.

С помощью двойственной задачи проверьте, что базисное решение (х х2) не оптимально.

3/7 -\т

1/7 2/7 J *