Задача 14.19

Введите исходные данные целые числа и (или) любые дроби (например -0.15 -1/5 2.12 10)   линейная функция   Начало формы Конец формы L = * x1 + * x2 + * x3 + * x4   найти наибольшее наименьшее значение функции   ограничивающие условия   * x1 + * x2 + * x3 + * x4 <= = >=   * x1 + * x2 + * x3 + * x4 <= = >=   на все переменные наложено ограничение x i 0 новые исходные данные             Найдем наименьшее значение линейной функции   L = x1 + x2 + x3 + x4   при следующих ограничениях       x1 +   x2 +   x3             x1 +   x2 +   x3 +   x4     Решение:   Умножим коэффициенты исходной функции на -1. G = - x1 - x2 - x3 - x4 Будем искать наибольшее значение получившийся функции. Обратите внимание, что максимальное значение рассматриваемой функции равно наименьшему значению исходной функции по модулю, но значения противоположны по знаку. Другими словами, получившийся ответ мы должны будем умножить на -1. В двух словах смысл того, что мы будем делать. Нам необходимо найти начальное опорное (абсолютно произвольное) решение для функции G, которое бы удовлетворяло системе наложенных ограничений. Далее, применяя симплекс таблицы, мы будем получать решения, при которых значение функции будет, как минимум, не убывать. И так до тех пор, пока не достигнем оптимально решения, при котором функция достигает своего максимума. Если, конечно, рассматриваемая нами линейная функция обладаем максимальным значением при заданной системе ограничений. Перед применением симплекс таблиц, необходимо преобразовать систему линейных ограничений и рассматриваемую нами функцию G к вполне определенному виду. · Свободные члены системы ограничений должны быть неотрицательными.   Свободные члены системы ограничений неотрицательные. · Система ограничений должна быть приведена к каноническому виду. От левой части неравенства 1 системы ограничений отнимаем неотрицательную переменную x5 - преобразуем неравенство 1 в равенство. От левой части неравенства 2 системы ограничений отнимаем неотрицательную переменную x6 - преобразуем неравенство 2 в равенство.     x1 +   x2 +   x3       -   x5       =       x1 +   x2 +   x3 +   x4       -   x6 =   Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.   Разделим почленно уравнение 2 системы ограничений на 13.       x1 +   x2 +   x3       -   x5       =     1/13 x1 + 6/13 x2 + 9/13 x3 +   x4         -1/13 x6 = 4/13     · Определимся с начальным опорным решением.   Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:   В уравнении 1 нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную r1. Очевидно, переменная r1 будет являться базисной переменной, т.к. входит в уравнение 1 с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.   Переменная x4 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е x4 - базисная переменная.       x1 +   x2 +   x3       -   x5       +   r1 =     1/13 x1 + 6/13 x2 + 9/13 x3 +   x4         -1/13 x6       = 4/13   Переменные, которые не являются базисными называются свободными переменными. Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное решение. X нач = (0, 0, 0, 4/13, 0, 0, 8) Для получения единичного базиса нам пришлось ввести искусственные переменные, поэтому наше начальное решение является псевдорешением.   Для нахождения начального опорного решения функции G, сначала придется решить вспомогательную задачу. Введем в рассмотрение вспомогательную функцию W:   W = - r1   Найдем наибольшее значение функции W. Схема решения вспомогательной задачи абсолютно аналогична схеме описанной выше. Есть только одно исключение: вспомогательная задача всегда имеет решение. В процессе решения данной задачи возможны два варианта. Если максимальное значение вспомогательной функции W равно нулю, т.е. все искусственные переменные обращаются в нуль - это будет свидетельствовать о том, что мы нашли начальное опорное решение функции G. В противном случае, не существует решений, удовлетворяющих системе ограничений нашей задачи.   · Функция G и вспомогательная функция W не должны содержать базисных переменных.   Из уравнения 1 последней системы выразим r1 и подставим в выражение функции W, получим   W = -8 + 3 x1 + 2 x2 + x3 - x5   Значение функции W для начального решения: W (X нач) = -8   Вернемся к рассмотрению функции G.   G = - x1 - x2 - x3 - x4   Из уравнения 2 последней системы выразим x4 и подставим в выражение функции L, получим   L = -4/13 -12/13 x1 -7/13 x2 -4/13 x3 -1/13 x6 Функция G и вспомогательная функция W не содержат базисных переменных.   Для составления начальной симплекс таблицы мы выполнили все условия. Обратите внимание: При составлении исходной симплекс таблицы, коэффициенты при переменных функции G записываются с противоположными знаками, а свободный член со своим знаком. Для функции W правило аналогичное.   Шаг 1   За ведущий выберем столбец 1, так как -3 наименьший элемент в W строке. Элемент W строки, принадлежащий столбцу свободных членов не рассматриваем.   За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1.   базисные переменные x1 x2 x3 x4 x5 x6 r1 свободные члены отношение r1 -     x4 -         G -         - W -     -     -     -     -   Разделим элементы строки 1 на 3.   базисные переменные x1 x2 x3 x4 x5 x6 r1 свободные члены отношение r1 -         x4 -         G -         - W -     -     -     -     -   От элементов строки 2 отнимает соответствующие элементы строки 1.   От элементов строки G отнимает соответствующие элементы строки 1, умноженные на 12/13.   От элементов строки W отнимает соответствующие элементы строки 1, умноженные на -3.   Элементы столбца r1 можно не пересчитывать, так как переменная r1 больше не является базисной.   базисные переменные x1 x2 x3 x4 x5 x6 свободные члены x1 -         x4 -         G -         -         W X 1 = (8/3, 0, 0, 4/39, 0, 0) W =     Значение функции W для данного решения: W (X 1) = 0   Строка W нам больше не нужна.   · Мы нашли начальное опорное решение функции G.   X нач. = (8/3, 0, 0, 4/39, 0, 0) G = -36/13 + 1/13 x2 -4/13 x5 -1/13 x6   Значение функции для данного решения: G (X нач.) = -36/13   Шаг 2   За ведущий выберем столбец 2, так как -1/13 наименьший элемент в G строке. Элемент G строки, принадлежащий столбцу свободных членов не рассматриваем.   За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2.   базисные переменные x1 x2 x3 x4 x5 x6 свободные члены отношение x1 -         x4 -         G -         -         -   Разделим элементы строки 2 на 16/39.   базисные переменные x1 x2 x3 x4 x5 x6 свободные члены отношение x1 -         x4 -         G -         -         -   От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2/3.   От элементов строки G отнимает соответствующие элементы строки 2, умноженные на -1/13.   базисные переменные x1 x2 x3 x4 x5 x6 свободные члены x1 -         -         -         x2 -         G -         X 1 = (5/2, 1/4, 0, 0, 0, 0) G = -11/4 -1/8 x3 -3/16 x4 -5/16 x5 -1/16 x6   Значение функции G для данного решения: G (X 1) = -11/4   Учитывая, что все x i 0, по условию задачи, наибольшее значение функции G равно свободному члену -11/4, т.е. мы получили оптимальное решение.   Теперь можем записать ответ.   Ответ: X опт = (5/2, 1/4, 0, 0, 0, 0) Значение функции: L = 11/4

Литература:

Красе М. С. Чупрынов Б. П. Математика для экономистов. — СПб.: Питер. 2005. — С.259-301

Ссылка для скачивания: http://booksshare.net/index.php?author=krass-ms&book=2005&category=math&id1=4