4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x₂ .

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₆ плана 1 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂ .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
30-(10 • 5):3	0-(0 • 5):3	5-(3 • 5):3	1-(0 • 5):3	0-(-1 • 5):3	2-(1 • 5):3	0-(1 • 5):3	-2-(-1 • 5):3
10 : 3	0 : 3	3 : 3	0 : 3	-1 : 3	1 : 3	1 : 3	-1 : 3
0-(10 • -1):3	1-(0 • -1):3	-1-(3 • -1):3	0-(0 • -1):3	0-(-1 • -1):3	-1-(1 • -1):3	0-(1 • -1):3	1-(-1 • -1):3
(2-2M)-(10 • (-5+3M)):3	(0)-(0 • (-5+3M)):3	(-5+3M)-(3 • (-5+3M)):3	(0)-(0 • (-5+3M)):3	(-1M)-(-1 • (-5+3M)):3	(-2+1M)-(1 • (-5+3M)):3	(0)-(1 • (-5+3M)):3	(2-2M)-(-1 • (-5+3M)):3

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	131/3	0	0	1	12/3	1/3	-12/3	-1/3
x2	31/3	0	1	0	-1/3	1/3	1/3	-1/3
x1	31/3	1	0	0	-1/3	-2/3	1/3	2/3
F(X2)	162/3	0	0	0	-12/3	-1/3	12/3-1M	1/3-1M

1. Проверка критерия оптимальности.

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	131/3	0	0	1	12/3	1/3	-12/3	-1/3
x2	31/3	0	1	0	-1/3	1/3	1/3	-1/3
x1	31/3	1	0	0	-1/3	-2/3	1/3	2/3
F(X3)	162/3	0	0	0	-12/3	-1/3	12/3-1M	1/3-1M

Оптимальный план можно записать так:

x₃ = 13¹/₃

x₂ = 3¹/₃

x₁ = 3¹/₃

F(X) = 3•3¹/₃ + 2•3¹/₃ = 16²/₃

Составим двойственную задачу к прямой задаче.

2y₁ + y₂ + y₃≤2

3y₁ + 2y₂ - y₃≤3

30y₁ + 10y₂ → max

y₁ ≤ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = 1²/₃

y₃ = ¹/₃

Z(Y) = 30*0+10*1²/₃+0*¹/₃ = 16²/₃

БИЛЕТ№4

ЗАДАЧА №1

Фирма имеет возможность рекламировать свою продукцию, используя местные радио- и телевизионную сети. Затраты на рекламу в бюджете фирмы ограничены величиной 1000$ в месяц. Каждая минута радиорекламы обходится в 5$, а каждая минута телерекламы - в 100$. Фирма хотела бы использовать радиосеть, по крайней мере, в два раза чаще, чем сеть телевидения, но при этом фирма решила, что время радиорекламы не должно превышать двух часов. Опыт прошлых лет показал, что объем сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше сбыта, обеспечиваемого одной минутой радиорекламы. Определите оптимальное распределение финансовых средств, ежемесячно отпускаемых на рекламу, между радио- и телерекламой. Решение: Обозначим за хТ - количество финансовых средств, отпускаемых на телерекламу, а за хР - количество финансовых средств, отпускаемых на радиорекламу. Сразу же можем записать одно ограничение на общее количество средств, отпускаемых на рекламу: Количество минут, используемых для рекламы на радио, будет вычисляться следующим обра зом: , а количество минут, используемых для рекламы на телевидении : Для простоты будем считать, что время на рекламу можно покупать посекундно. Условие использования радиосети по крайней мере в два раза чаще, чем сеть телевидения, запишется следующим ограничением: Решение о том, что время радиорекламы не должно превышать двух часов, запишется в виде: А теперь запишем целевую функцию. По условию задачи мы должны найти оптимальное значение распределения финансовых средств, чтобы эффективность от рекламы была максимальной. Если эффективность одной минуты радиорекламы обозначить за единицу, то эффективность одной минуты телерекламы будет равна двадцатипяти. Получим следующую функцию: Из условия задачи естественно вытекают ещё два ограничения: Сведем все ограничения и целевую функцию в одну систему: Приведем систему к стандартному виду и учтем тот факт, что симплекс-метод используется для системы, которую надо минимизировать. Возьмем в качестве свободных переменных хТ и хР, а в качестве базисных примем z1, z2 и z3, умножив при этом второе ограничение на -1. Составим начальную симплекс-таблицу и решим систему. Таким образом, получили, что на радиорекламу надо тратить 90,90$, а на телерекламу - 909,09$, что в минутах составляет на радио - 18,18 минуты, а на телевидении - 9,9 минуты. Тот же результат можно получить и графически. Точка А соответствует оптимуму системы уравнений. Теперь перейдем от прямой задачи к двойственной. Обозначим переменные двойственной задачи за y1, y2, y3, т. е. количество переменных равно количеству ограничений в прямой задаче. При этом переменные двойственной задачи считаются неограниченными по знаку. Поставим каждому ограничению прямой задачи переменную из двойственной. Теперь составим целевую функцию двойственной задачи. Значения при переменных в целевой функции берутся из правых частей ограничений прямой задачи, при этом рядом каким-либо значением ставится та переменная, которая соответствует данному ограничению. Направление улучшения целевой функции двойственной задачи противоположно направлению улучшения целевой функции прямой задачи. Получим: Теперь каждому ограничению двойственной задачи поставим в соответствие переменную прямой задачи. Т. е. будем считать, что первому ограничению двойственной задачи соответствует, например, переменная хР из прямой задачи. Получим следующее ограничение: Обратим внимание на то обстоятельство, что в правой части ограничения стоит значение при хР из целевой функции прямой задачи. Таким же образом составим остальные ограничения для двойственной задачи, которым будут соответствовать переменные хТ, z1, z2, z3 из прямой задачи. Необходимо отметить тот факт, что порядок выбора переменных прямой задачи для составления ограничений двойственной произволен и не влияет на решение задачи, а будет влиять лишь на расположения ограничений в задаче. Собрав все полученные ограничения, мы можем записать: Из третьего, четвертого и пятого ограничения видно, что последнее ограничение избыточно. Избавившись от избыточности, получим следующий вид двойственной задачи: Теперь эту задачу можно решать как прямую, т.е. сначала ее необходимо перевести в задачу стандартного вида, затем построить начальную симплекс-таблицу и решить задачу симплекс-методом. Решение: Приведем задачу к стандартному виду: Решим систему симплекс-методом. Возьмем в качестве базисных переменных переменные y3 и -y2. Выведем y3 из целевой функции и y2 из первого ограничения. Для этого выразим y2 из второго ограничения, подставим его в первое. Затем из первого уравнения выразим y3, и подставим в целевую функцию. В итоге получим: Получаем следующее оптимальное решение двойственной задачи: Далее будет показано, что между прямой и двойственной задачами существует тесная взаимосвязь. Фактически, имея оптимальную симплекс-таблицу одной задачи, можно получить оптимальное решение другой, не производя громоздких вычислений и не используя симплекс-метод. Заинтересованность в определении оптимального решения прямой задачи путем решения двойственной к ней задачи обусловлена тем, что вычисления, необходимые для решения двойственной задачи, могут оказаться менее сложными, чем для прямой задачи. Напомним, что трудоемкость вычислений при решении задач ЛП в большей степени зависит от числа ограничений, чем от количества переменных. Поэтому, если в двойственной задаче ограничений меньше, чем в прямой, как правило, целесообразнее решать двойственную задачу и полученный результат использовать для нахождения оптимального решения прямой задачи. Оптимальное решение прямой задачи можно получить непосредственно из симплекс-таблицы для двойственной задачи, если воспользоваться следующим уравнением: Покажем, что оптимальное решение прямой задачи в свою очередь так же непосредственно определяется из симплекс-таблицы для оптимального решения двойственной задачи. Заметим, что переменные xP и хТ связаны с первым и вторым ограничениями двойственной задачи соответственно и, следовательно, с искусственными переменными u1 и u2. (**) Следовательно, Таким образом, получим тот же результат, который приведен в симплекс-таблице для оптимального решения прямой задачи. Анализ сопоставления результатов, полученных при решении прямой и двойственной задачи, позволяет сформулировать интересный вывод. На итерации, приводящей к оптимуму, Это равенство справедливо всегда и фактически соответствует оптимальным значениям переменных обеих задач.

ЗАДАЧА №2

Для плану визначити, чи він є оптимальним для наступної задачі (застосовуючи теореми двоїстості й не розв’язуючи задачі симплексним методом):

Розв’язання. Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках:

1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.

2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.

3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.

Запишемо двоїсту задачу до прямої задачі лінійного програмування:

;

Перевіримо запропонований план на оптимальність.

  . Підставимо його в систему обмежень прямої задачі:

Три обмеження виконуються, і тому є допус­тимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = -2*3-0+1+3 = -2.

Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x₁ = 3 > 0; x₃ = 1 > 0; x₄ = 3 > 0 то згідно з другою частиною другої теореми двоїстості можна записати обмеження як рівняння і визначити у₁ у₂ у₃:

Підставимо ці значення в друге обмеження системи двоїстої задачі:

- ;

.

F = 2*-0,66+6*-0,33+2*0,66 = -2 =Z

Для визначених значень це обмеження виконується, і тому відповідний план у = (-0,66; -0,33;0,66) є допустимим планом двоїстої задачі. Внаслідок цього наше допущення, що є оптимальним планом прямої задачі, виявилося вірним.

БИЛЕТ№5

ЗАДАЧА №1

ЗАДАЧА №2

Для плану визначити, чи він є оптимальним для наступної задачі (застосовуючи теореми двоїстості й не розв’язуючи задачі симплексним методом):

Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках:

1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.

2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.

3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.

Запишемо двоїсту задачу до прямої задачі лінійного програмування:

;

Перевіримо запропонований план на оптимальність.

  . Підставимо його в систему обмежень прямої задачі:

Три обмеження виконуються, і тому є допус­тимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 2*3-0+1*4-6*3 = -8.

Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x₁ = 3 > 0; x₃ = 1 > 0; x₄ = 3 > 0 то згідно з другою частиною другої теореми двоїстості можна записати обмеження як рівняння і визначити у₁ у₂ у₃:

Підставимо ці значення в друге обмеження системи двоїстої задачі:

- ;

.

План опт.

F = 15*0-4*2=-8 =Z

Для визначених значень це обмеження виконується, і тому відповідний план у = (2; 0; 2) є допустимим планом двоїстої задачі. Внаслідок цього наше допущення, що є оптимальним планом прямої задачі, виявилося вірним.

БИЛЕТ№6

ЗАДАЧА №1

ЗАДАЧА №2

Підприємство виготовляє продукцію видів А, В і С, для чого використовує три види ресурсів І, II, III. Норми витрат усіх ресурсів на одиницю кожної продукції та обсяги ресурсів на підприємстві наведено в табл.1. Відома ціна одиниці продукції кожного виду: А - 10 ум.од., В -14 ум.од. і С - 12 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший доход.

Вид ресурсу	Норма витрат на одиницю продукції за видами			Запас ресурсу
	А	В	С
І II III	4 3 1	2 1 2	1 3 5	180 210 244

Остання симплекс-таблиця, що містить оптимальний план задачі, має такий вигляд

Базис	Сб	А0	9	10	16	0	0	0
			X1	X2	X3	X4	X5	X6
X2 X5 X3	14 0 12	82 80 16	19/8 23/8 -3/4	1 0 0	0 0 1	5/8 1/8 -1/4	0 1 0	-1/8 -5/8 1/4
		1340	57/4	0	0	23/4	0	5/4

З наведеної останньої симплексної таблиці початкової задачі запишіть оптимальні плани і ; визначте дефіцитні й недефіцитні ресурси, рентабельну та збиткову продукцію.

Розв’язання

Мат. Модель має вигляд:

Оптимальный план можно записать так:

x₂ = 82

x₅ = 80

x₃ = 16

Х0 =(0;82;16;0;80)

F(X) = 14•82 + 12•16 = 1340

Составим двойственную задачу к прямой задаче.

4y₁ + 3y₂ + y₃≥10

2y₁ + y₂ + 2y₃≥14

y₁ + 3y₂ + 5y₃≥12

180y₁ + 210y₂ + 244y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 5³/₄

y₂ = 0

y₃ = 1¹/₄

Y0 = ( 23/4 ; 0 ; 5/4)

Z(Y) = 180*5³/₄+210*0+244*1¹/₄ = 1340

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

Подставим оптимальный план прямой задачи в систему ограниченной математической модели:

4*0 + 2*82 + 1*16 = 180 = 180

3*0 + 1*82 + 3*16 = 130 < 210

1*0 + 2*82 + 5*16 = 244 = 244

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).

2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0.

Неиспользованный экономический резерв ресурса 2 составляет 80 (210-130).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃>0).

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