Математика \ Математическое моделирование систем и процессов

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

, .

Следовательно, план является допустимым для задачи (15, 16). Вычислим теперь значение целевой функции на этом плане. У нас получиться:

Это значение совпадает с сосчитанным ранее значением целевой функции прямой задачи. А поэтому приведенный нами план двойственной задачи (23) будет оптимальным.

Пример решения задачи

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

В математических символах эта задача имеет следующий вид:

1. Запишем эту задачу в матричной форме. Для этого умножим первое и третье неравенство системы на –1. У нас получиться следующая система неравенств:

Следовательно, наша задача в матричной форме примет вид:

, , где

; ; ; (24)

2. Для построения канонической задачи введем дополнительные переменные и запишем систему ограничений задачи в виде

Окончательно, каноническая задача линейного программирования для нашей задачи имеет вид:

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

. (25)

(III)

3. Для того чтобы решить начальную задачу геометрически, построим прямые

;

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

(II)

(I)

Построим прямую L:

и будем ее передвигать в направлении вектора

. Свое максимальное значение на множестве

функция

примет в точке

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

Функция принимает свое максимальное на множестве значение равное в точке с координатами ; .

4. Если за базисные переменные канонической задачи (25) взять переменные , то соответствующий базисный план будет недопустим. Для построения начального плана введем искусственную переменную и составим вспомогательную задачу.