Методические указания и варианты индивидуальных заданий для студентов заочного факультета, страница 2

,                                          (4)

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

        .                                    (5)

Решение. Найдем множество  решений неравенств. Для этого построим три прямые:

                                                            

Прямая  разбивает плоскость на две полуплоскости. Стрелочками отметим ту полуплоскости, которая удовлетворяет неравенству . Для этого достаточно проверить хотя бы одну точку этой полуплоскости, например, начало координат . Пересечение полуплоскостей составит множество допустимых решений задачи D.

Построим теперь линии уровня функции F, т.е прямые  для различных p. На рисунке показана прямая, соответствующая значению . На части этой прямой, лежащей внутри этой области, значение функции F равно 14.

Параллельно переместим эту прямую в направлении вектора . Свое наибольшее на множестве  значение функция F примет в вершине многоугольника точке . Для того чтобы найти ее координаты достаточно решить систему уравнений:

Откуда мы находим , . Итак,  максимальное на множестве  значение функции F равно , которое она принимает в точке с координатами , .

Построение симплекс-таблицы

Определение 4. Задача линейного программирования называется канонической, если она имеет следующий вид.

Задача 2. Найти минимум линейной функции:

,                               (6)

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

                                              (7)

,

или в матричной форме

,                                                                  (8)

, .                                                                   (9)

Определение 5. Мы будем говорить, что задача линейного программирования (1,2) сведена к некоторой канонической задаче линейного программирования (возможно с другим числом переменных и ограничений), если по решению первой задачи можно построить решение второй задачи и наоборот.

Пример 4. Свести задачу линейного программирования

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

                                                  (10)

, к канонической задаче.

Перенесем члены неравенств в одну часть так, чтобы полученные выражения были неотрицательны:

Введем дополнительные переменные , ,  по формулам:

                                             (11)

Таким образом, каждому решению  системы неравенств (10) будет соответствовать решение  системы уравнений (11), причем все его компоненты будут неотрицательны. И наоборот каждому неотрицательному решению  системы (11) будет соответствовать решение  системы (10).

Если функция F принимает в некоторой точке максимальное значение, то в этой точке функция (–F) принимает свое минимальное значение. Причем эти значения будут равны с точностью до знака. Таким образом, вместо максимума функции  на множестве D можно искать на этом множестве минимум функции .

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

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

.

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

Минимальное значение функции , в точке с координатами:

, , , , .

Определение 6. Набор из m различных переменных системы уравнений (7) называется базисным, если все переменные из этого набора могут быть выражены только через оставшиеся переменные с помощью элементарных преобразований системы. Переменные, входящие в этот набор, называются базисными, а остальные свободными.

Определение 7. Решение системы (7) называется базисным (опорным планом), если значения всех свободных переменных равны нулю.

Пример 5. Найти базисное решение системы:

                                                     (12)

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

Определение 8. Симплекс-таблицей для канонической задачи (6), (7) называется следующая таблица: