Здравствуйте.
Есть задача: На основании графического анализа двойственной задачи:
1) Исследовать разрешимость данной задачи ЛП.
2) В случае разрешимости найти решение двойственной и исходной задачи (используя теорему двойственности)

f(x)=x1+4x2+x2->max
4x1+11x2+3x3=7
x1+x2-x3=0
xi>=0, i=1,2,3

Из исходной в двойственную я сделала, вот:
f(y)=7y1->min
4y1+y2>=1
11y1+y2>=4
3y1-y2>=1

А как построить график, я не знаю. Помогите пожалуйста с построением.

задан 12 Июн '14 16:17

изменен 12 Июн '14 17:01

10|600 символов нужно символов осталось
0

В тех случаях, когда речь идёт о двух переменных, задача имеет графическую интерпретацию на координатной плоскости. В данном случае будут две оси: $%Oy_1$% и $%Oy_2$%. Для начала рисуем графики трёх прямых: $%y_2=1-4y_1$%, $%y_2=4-11y_1$%, $%y_2=3y_1-1$%. Они соответствуют равенствам, которые получаются из неравенств. Поскольку нас интересуют именно неравенства, то с каждой из прямых мы связываем одну из полуплоскостей, которую прямая ограничивает. Для первых двух случаев это будет полуплоскость (с границей), расположенная выше проведённой прямой, так как неравенства имеют вид $%y_2\ge\ldots$%, а для третьего случая, соответственно, ниже прямой.

Множеством решений системы неравенств будет являться пересечение трёх полуплоскостей, и это многоугольная область (в данном случае, неограниченная). Граница области там будет состоять из двух лучей и одного отрезка; при этом надо найти координаты точек пересечения, что сделать нетрудно.

Теперь надо минимизировать значение функции $%7y_1$% в пределах данной области, а это значит найти точку области с наименьшей абсциссой, то есть "крайнюю левую". Из графиков эта точка сразу становится видна.

ссылка

отвечен 12 Июн '14 17:06

@falcao Спасибо. Но без рисунка не совсем понятно. Вот, я построила эти прямые. Не могли бы Вы на графике начертить то, что Вы написали, пожалуйста. http://uploads.ru/NTJBA.jpg

(12 Июн '14 17:48) ekaterina1

@ekaterina1: у Вас всё нарисовано верно, и осталось увидеть саму область. Нас интересует то, что расположено выше красной и выше синей прямой, и при этом ниже зелёной. Первые две прямые идут почти вертикально, поэтому "выше" почти что означает "правее", и для зелёной прямой "ниже" будет фактически означать "правее". То есть нужной нам областью будет та часть, которая расположена на рисунке правее все остальных. Её граница состоит из зелёного луча вверху, красного отрезка посередине, и синего луча внизу. Крайняя слева точка этой области -- пересечение красного с зелёным ($%4-11y_1=3y_1-1$%).

(12 Июн '14 18:18) falcao

@falcao Спасибо большое. А как теперь быть с пунктами 1 и 2. И что значит: В случае разрешимости найти решение двойственной и исходной задачи (используя теорему двойственности)? Т.е. решение двойственной задачи будет 4−11y1=3y1−1 -- точка минимума. А как найти решение исходной задачи -- точку максимума?

(12 Июн '14 18:40) ekaterina1

@ekaterina1: пункт 1 подразумевает, что в общем случае решения может и не быть. Скажем, если бы для $%y_1$% надо было найти максимум, а не минимум, то он бы нигде не достигался. Здесь минимум достигается, и этим устанавливается разрешимость задачи.

От оптимального решения двойственной задачи к решению исходной надо перейти по формулам, которые связывают между собой "иксы" и "игреки". Они должны быть в формулировках теоремы двойственности. Фактически, там надо будет решить систему линейных уравнений относительно "иксов". Значения целевой функции одинаковые; минимум и максимум меняются местами.

(12 Июн '14 19:04) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×58

задан
12 Июн '14 16:17

показан
1131 раз

обновлен
12 Июн '14 19:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru