Версия для печати темы

Автор: Yano4k@ 22.2.2011, 16:23

Решить задачу ЛП: минмизировать функцию W = 4x1+ 6x2, при ограничениях x1 + 2x2>=1; x1 - x2>=3.
Решение:
1) Исследуем систему ограничений x1 + 2x2>=1; x1 - x2>=3.
x1 = 3+x2
3+x2+2x2 = 1
3x2 = -2
x2 = -(2/3), что не удовлетворяет общей задаче ЛП. (х>0)
и что это значит? Оптимально решения нет??? Подскажите плиз(((
Заранее спасибо!

Автор: tig81 22.2.2011, 16:27

1. Каким методом надо решить задачу?
2. Объясните, как вы исследуете систему ограничений? Я такого никогда не делала и не совсем поняла как и зачем.

Автор: Тролль 22.2.2011, 16:28

А с чего Вы взяли, что x1 + 2x2 = 1?

Автор: tig81 22.2.2011, 16:30

Ага, у меня такой же вопрос.

Автор: Yano4k@ 22.2.2011, 19:19

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

Автор: tig81 22.2.2011, 19:20

Решайте им же.

Но не из системы же ограничений?!

Автор: Yano4k@ 22.2.2011, 19:27

Ой, блин, это я торможу!
x1 >= 3+x2
3+x2+2x2 >= 1
3x2 >= -2
x2 >= -(2/3), тогда

x1>=3-(2/3)
x1>=2(1/3), следовательно

x>=2(1/3) ???
И че это???




Почему не из системы?
1) Находим все х.
2) Подставляем их в W
3) Далее геометрический метод( ограничиваем полуплоскости и т. д. )
Так?

Автор: tig81 22.2.2011, 19:30

И че это?

Вам надо решить систему или найти оптимальный план?

???

пункт 3 ставите на первое место. Откройте любую книгу по матпрогу и посмотрите про графический метод решения задач линейного программирования.

Автор: Yano4k@ 22.2.2011, 21:26

Кажется, дошло! Нужно построить эти прямые? Которые в системе ограничений?

Автор: tig81 22.2.2011, 21:50

В системе ограничений не прямые, т.к. там не знаки равенства.
www.google.ru - Линейное программирование Графический метод

Автор: Yano4k@ 23.2.2011, 8:53

1) Построим на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств:
х1-1+2х2 = 0
х1 = 0; х2 = 0,5
х2 = 0; х1 = 1

x1-3-x2 = 0
x1 = 0; x2 = -3
x2 = 0; x1 = 3

x1 = 0
x2 = 0

2) Найдем полуплоскости, определяемые каждым из ограничений задачи.
У меня получается, что ОДР нет!

Автор: tig81 23.2.2011, 8:55

Показывайте как строили, надо смотреть рисунок.

Автор: Yano4k@ 23.2.2011, 9:38

ОДР не существует???


Эскизы прикрепленных изображений

Автор: tig81 23.2.2011, 9:48

По-моему, замечательно существует.
1. А в условии нет, что х1, х2>=0, не дописали?
2. Сделайте штриховку побольше и разными цветами. Посмотрите, в какой области будет штриховка всех цветов.

Автор: Yano4k@ 23.2.2011, 10:28

Такое ОДР???


Прикрепленные изображения

Автор: tig81 23.2.2011, 10:31

А картинку еще меньше можно сделать?

Автор: Yano4k@ 23.2.2011, 10:34

Можно
Ну у меня только 2 Кб осталось! Не видно?

Автор: tig81 23.2.2011, 10:37

Так не прикрепляйте к сообщению, я, кажется уже писала вам такое. Залейте картинку на www.radikal.ru, а сюда вторую ссылку.

А вам видно?

Автор: Yano4k@ 23.2.2011, 10:49

здесь
http://s46.radikal.ru/i113/1102/ce/b798cf03ed5e.png

Автор: tig81 23.2.2011, 10:57

Т.е. искомая область - это которая выделена фиолетовым? Так тогда там нет красной штриховки.

Автор: Yano4k@ 23.2.2011, 12:10

http://s012.radikal.ru/i320/1102/5d/0d8c59c3b80a.jpg

Автор: tig81 23.2.2011, 12:31

Да.

Автор: Yano4k@ 23.2.2011, 13:07

Далее, я построила прямую W и определила, что ее нужно сдвигать в левую сторону( не буду уж чертеж выкладывать).

Так как ОДР незамкнутая, оптимального решения нет.
Так я понимаю?

Автор: tig81 23.2.2011, 13:53

W не прямая, а функция, а вы строите прямую W=С.

Ну в левую сторону некорректно сказано. Надо еще построить градиент, или второе название, вектор нормали. И сдвигать по его направлению или в противоположном.

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

Автор: Yano4k@ 23.2.2011, 14:07

Ну это все понятно! А нам вроде говорили, что " если ОДР незамкнутая, то ОР нет!" независимо на минимум или на максимум!

Значит, ОР явл. х1 = 3, х2 = 0, W = 12

Автор: tig81 23.2.2011, 14:31

неправильно говрили. В данном случае решение есть.

Сложно сказать, показывайте полное решение.

Автор: Yano4k@ 23.2.2011, 15:11

График: http://i061.radikal.ru/1102/e2/88cec0d7b7f0.png

На графике видно, что оптимальным решением будем являться точка (3;0).
W(min) = 4*3 + 6*0 = 12.

Автор: tig81 23.2.2011, 16:15

То, что вроде видно из графика, еще не означает, что верно. Надо все показать. Но судя по всему про графический метод решения вы явно не дочитали.

Автор: Yano4k@ 23.2.2011, 18:14

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

Я так и сделала, перемещала прямую в сторону направления вектора нормали. В результате нашла точку, в которой целевая функция принимает минимальное значение. Определила её оординаты и вычислила значение моей функции в этой точке.
W(min) = 4*3 + 6*0 = 12.

Автор: Yano4k@ 27.2.2011, 12:44

Скажите пожалуйста, правильно я решила или нет???