Математика 19

<

092613 1921 191 Математика 19Задание 3

 

Построить двойственные задачи к следующим ЗЛП в симметричной форме и решить обе задачи.

 

092613 1921 192 Математика 19

 

092613 1921 193 Математика 19

 

Решение:

 

Построим двойственную задачу

1. Все неравенства системы надо привести к виду 092613 1921 194 Математика 19, но они уже в этом виде.

2. Составим расширенную матрицу системы092613 1921 195 Математика 19, в которую включим:

а) матрицу коэффициентов при переменных матрицы 092613 1921 196 Математика 19;

б) столбец свободных членов системы ограничений;

в) строку коэффициентов при переменных в линейной функции.

 

092613 1921 197 Математика 19

 

3. Найти матрицу 092613 1921 198 Математика 19, транспонированную к матрице 092613 1921 199 Математика 19.

 

092613 1921 1910 Математика 19

 

4. Сформулируем двойственную задачу на основании полученной матрицы 092613 1921 1911 Математика 19

 

092613 1921 1912 Математика 19

 

092613 1921 1913 Математика 19

 

Решим обе задачи

 

092613 1921 1914 Математика 19

 

092613 1921 1915 Математика 19

 

Воспользуемся графическим методом решения (рисунок )

092613 1921 1916 Математика 19

Рисунок 3 – Графическим метод решений

Прямые ограничения092613 1921 1917 Математика 19означают, что область решений будет лежать в первой четверти декартовой системы координат (см. рисунок).

 

Определим множество решений первого неравенства:

 

092613 1921 1918 Математика 19

 

Оно состоит из решения уравнения и строгого неравенства.

 

092613 1921 1919 Математика 19

092613 1921 1920 Математика 19

Построим прямую 092613 1921 1921 Математика 19 по двум точкам (0;-11) и (092613 1921 1922 Математика 19; 0) , которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим её цифрой I. По отношению к данной прямой начало координат находится в верхней полуплоскости. Подставим координаты (0; 0) в неравенство 092613 1921 1923 Математика 19, получим заведомо неверное 0>11, т.е. оно не выполняется. Следовательно, областью решений служит нижняя полуплоскость (см. рисунок).

<

 

Определим множество решений второго неравенства:

 

092613 1921 1924 Математика 19

 

Оно состоит из решения уравнения и строгого неравенства.

 

092613 1921 1925 Математика 19

092613 1921 1926 Математика 19

 

Построим прямую 092613 1921 1927 Математика 19 по двум точкам (0;092613 1921 1928 Математика 19) и (-11; 0) , которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим её цифрой II. По отношению к данной прямой начало координат находится в нижней полуплоскости. Подставим координаты (0; 0) в неравенство 092613 1921 1929 Математика 19, получим заведомо неверное 0>11, т.е. оно не выполняется. Следовательно, областью решений служит верхняя полуплоскость (см. рисунок).

Как видно из рисунка область решений представляет из себя незамкнутую многоугольную область. Построим линию уровня для целевой функции 092613 1921 1930 Математика 19Отметим её на рисунке пунктиром. Для определения направления движения к оптимуму построим вектор q, координаты которого являются частными производными функции Z, т.е. q={-1; -1}, или пропорциональный ему вектор. Для наглядности возьмем вектор 4q={-4; -4}. При максимизации целевой функции необходимо двигаться в направлении вектора q, а при минимизации – в противоположном направлении. Так как эта задача на минимум, то надо двигаться в противоположном направлении. Однако область допустимых решений в этом направлении неограниченна, следовательно, функции Z при данных ограничениях не имеет конечного минимума.

 

Решение двойственной задачи

 

092613 1921 1931 Математика 19

 

092613 1921 1932 Математика 19

 

Решим графическим методом (рисунок 4).

 

092613 1921 1933 Математика 19

 

Рисунок 4 – Решение графическим методом

 

Прямые ограничения092613 1921 1934 Математика 19означают, что область решений будет лежать в первой четверти декартовой системы координат (см. рисунок).

 

Определим множество решений первого неравенства:

 

092613 1921 1935 Математика 19

 

Оно состоит из решения уравнения и строгого неравенства.

 

092613 1921 1936 Математика 19

092613 1921 1937 Математика 19

 

Построим прямую 092613 1921 1938 Математика 19 по двум точкам (0;-1) и (092613 1921 1939 Математика 19; 0) , которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим её цифрой I. По отношению к данной прямой начало координат находится в верхней полуплоскости. Подставим координаты (0; 0) в неравенство 092613 1921 1940 Математика 19, получим заведомо неверное 0<-1, т.е. оно не выполняется. Следовательно, областью решений служит нижняя полуплоскость (см. рисунок).

Определим множество решений второго неравенства:

092613 1921 1941 Математика 19

Оно состоит из решения уравнения и строгого неравенства.

 

092613 1921 1942 Математика 19

092613 1921 1943 Математика 19

Построим прямую 092613 1921 1944 Математика 19 по двум точкам (0;092613 1921 1945 Математика 19) и (-1; 0) , которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим её цифрой II. По отношению к данной прямой начало координат находится в нижней полуплоскости. Подставим координаты (0; 0) в неравенство 092613 1921 1946 Математика 19, получим заведомо неверное 0<-1, т.е. оно не выполняется. Следовательно, областью решений служит верхняя полуплоскость (см. рисунок).

Как видно из рисунка область решений представляет из себя незамкнутую многоугольную область. Построим линию уровня для целевой функции 092613 1921 1947 Математика 19. Отметим её на рисунке пунктиром. Для определения направления движения к оптимуму построим вектор p, координаты которого являются частными производными функции F, т.е. p={11; 11}. }, или пропорциональный ему вектор. Для наглядности возьмем пропорциональный вектору p вектор {1; 1}.Так как эта задача на максимум, то надо двигаться в направлении вектора. Однако область допустимых решений в этом направлении неограниченна, следовательно, функция F при данных ограничениях не имеет конечного максимума.

Ответ: исходная задача не имеет конечного минимума, а двойственная ей конечного максимума.

<

Комментирование закрыто.

WordPress: 22.32MB | MySQL:124 | 1,279sec