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 *
4.2.5. Значения целевых функций прямой и обратной задач
В отношениях двойственности задач ЛП, если одна задача является задачей максимизации, то вторая обязательно является задачей минимизации. С этой точки зрения существует такое соотношение между значениями целевых функций двух задач.
Для любой пары допустимых решений прямой и двойственной задач
Значение целевой функции (Значение целевой функции в задаче максимизации ) в задаче минимизации )
В точке оптимума это соотношение принимает вид строгого равенства. Отметим, что в этом соотношении не указывается, какая задача прямая, а какая двойственная - здесь важен только тип оптимизации.
Пример 4.2.3
В примере 4.2.1 прямая и двойственная задачи имеют допустимые решения х, = 0, х2 = 0, х3 = 8/3 и у, = 6, у2 = 0. Для этих решений значения целевых функций соответственно равны г =32/3 и w = 60. Для оптимальных решений х, = 26/5, х2 = 12/5, х3 = 0 и у, = 29/5, у2 = -2/5 имеем z = w = 54,8. Таким образом, приведенные значения целевых функций подтверждают сформулированное соотношение.
Из соотношения следует, что для всех допустимых решений прямой и двойственной задач значения целевой функции задачи минимизации всегда будут верхним пределом значений целевой функции задачи максимизации. Таким образом, итерационное решение задачи максимизации ведет к возрастанию значений целевой функции, а итерационное решение задачи минимизации - к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходим к точке "равновесия", где значения целевых функций задач максимизации и минимизации становятся равными.
УПРАЖНЕНИЯ 4.2.5
1. Определите интервалы изменения значений целевой функции в следующих задачах ЛП.
a) Минимизировать г = 5л:, + 2х2 при ограничениях
л:,-л:2>3, 2л:, + 3лг2>5, л:,, лс2>0.
b) Максимизировать z = хх + 5лс2 + Зх3 при ограничениях
л:, + 2х2 + х3 = 3, 2л:, - х2 = 4, л:,, х2, х3>0.
c) Максимизировать z = 2л:, + х2 при ограничениях
х, -х2<10, 2л:, <40, л:,, л:2>0.