[Olya-Olenka]

Здравствуйте!
Очень надеюсь на ваш совет, ибо мучаюсь с задачкой уже который час, перерыла кучу тематических сайтов в инете и приличную стопку старых конспектов((

Дана система уравнений:

5х1 + 6х2 <= 12000

5х1 + 3х2 <= 27000

9х1 + 12х2 = Z max

Необходимо решить симплекс-методом.

мои попытки решить задачку

Переведя эти значения в матрицу и умножив последнее уравнение на (-1), получаю:

5 6 1 0 | 12000
5 3 0 1 | 27000
-9 -12 0 0 | 0

Затем, сделав второй шаг, получаю 2ю матрицу:

5/6 1 1/6 0 | 2000
5/2 0 -1/2 1 | 8400
1 0 2 0 | 24000

В итоге оптиматльный ответ (0; 2000), при этом функция равна 24000.
Правильно ли я решаю? У меня сомнения... И стоило ли в самом начале умножать последнее уравнение на (-1)??? *решаю по имеющемуся примеру*

Заранее спасибо за помощь))

@темы: Линейное программирование

Comments

[Likeriya]

5 6 1 1 | 12000
5 3 0 1 | 27000
-9 -12 0 0 | 0
В 1-й строчке ошибка (при добавлении доп. переменных). Должно быть 5 6 1 0 | 12000
Дальше не проверяла

[Olya-Olenka]

В 1-й строчке ошибка (при добавлении доп. переменных). Должно быть 5 6 1 0 | 12000

ой, это я опечаталась. На черновике вместо лишней единички стоит нолик

спасибо, что заметили

[Likeriya]

Во 2-м шаге:
5/6 1 1/6 0 | 2000
5/2 0 -1/2 1 | 8400 -- почему 8400?
1 0 2 0 | 24000
Но ответ правильный, и итерации заканчиваются на 2-м шаге)

[Likeriya]

Могу порекомендовать хороший задачник с примерами решения, правда, он на украинском. Надо?

[Olya-Olenka]

5/2 0 -1/2 1 | 8400 -- почему 8400?
1 0 2 0 | 24000 -- это что и откуда?

(( при решении я пользовалась программой симплекс-метод *их в инете полно "всяких разных"*, 8400 и 24000 - это именно то, что выдала программа...((( Самостоятельно я пыталась решить при помощи метода Гаусса, но в ответе получались отрицательные значения, чего, по условию задачи, быть не может((

можно я вас еще спрошу, как именно получаются значения на втором шаге??
5/6 1 1/6 0 | 2000
5/2 0 -1/2 1 | 8400
1 0 2 0 | 24000
я про эти дробные значения?? извиняюсь за глупый вопрос, но никак не могу понять - пересмотрела примеры, но нигде не написано конркетно (а ля "первую строку умножаем на (-2) и вычитаем из нее вторую" - везде даются только матрицы с уже подсчитанными значениями(( вы моя последняя надежда(( Подскажите, пожааааааалуйста, по какому принципе считать, дальше постараюсь справиться...

[Olya-Olenka]

Могу порекомендовать хороший задачник с примерами решения, правда, он на украинском. Надо?

буду рада всему))) любой помощи))))
правда на украниском... я в нем не сильна... но да ладно - лучше, чем ничего))

[Likeriya]

www.twirpx.com/file/243875/ -- Зайченко О.Ю., Зайченко Ю.П. Дослідження операцій. Збірник задач
Там достаточно много тем, в начале каждой есть решение примера указанным методом

По поводу значений.
Для задачи максимизации в базис вводится вектор с наибольшей отрицательной дельтой (дельты у Вас записанны в последней строке). Как они считаются, Вам понятно?
Далее, для вводимого вектора Аі подсчитываются отношения А0/Аі, в нашем случае 12000/6 и 12000/3. Из отношений А0/Аі выбирается минимальное, это и будет выводимый вектор (т.е. тот, который мы заменяем). В нашем случае это х3 на х2.
Теперь пересчитываем строку х3, деля ее на Аіj. В нашем случае, это 6. Т.е. на месте "пересечения" вводимого и выводимого векторов должна образоваться 1.
Затем пересчитываем строку х4 (2-ю строку нашей симплекс-таблицы). В столбце Аі все значения, кроме Аіj, должны быть 0.
Т.е. умножаем полученную строку х2 на 3 (в нашем случае) и вычитаем ее из строки х4.
Считаем дельты, если все положительны -- ура, итерации закончены.
Иначе -- на следующий шаг.

Если что-то не понятно, спрашивайте

[Гость]

www.diary.ru/~eek/p70169845.htm
В книгах Лунгу, Банди есть примеры

[Olya-Olenka]

Спасибо огромнейшее!!))))))) кажется, разобралась)))))))))))))))))))) спасибо, спасибо, спасибо тысячу раз))))

[Robot]

Зайченко О.Ю., Зайченко Ю.П. Дослідження операцій / Исследование операций. Збірник задач. 2007 DJVU
В посібнику в систематизованому вигляді представлено задачі і вправи по всіх основних розділах курсу Дослідження операцій, включаючи лінійне, нелінійне, динамічне програмування, стохастичне програмування.
Нове видання суттєво розширене та доповнено новими розділами, що відображають сучасні напрями цієї дисципліни, серед яких: прийняття рішень в умовах невизначеності, задачі і методи нечіткого програмування, методи декомпозиції в задачах оптимізації, задачі і методи прийняття рішень у конфліктних ситуаціях, що включають методи теорії антагоністичних та кооперативних ігор двох осіб, а також багатокритеріальні задачі прийняття рішень як у чітких, так і в нечітких умовах.
Всі розділи посібника мають однакову структуру: спочатку викладається необхідний теоретичний матеріал, далі йдуть приклади застосування викладених методів та алгоритмів на конкретних задачах з детальними поясненнями процесу вирішення, а потім наведені численні вправи та задачі для самостійного розв’язання.
Теоретичний апарат, що викладається в посібнику, базується на підручнику Ю. П. Зайченко « Дослідження операцій », 7-ме вид., Київ. , 2006, – 816 с.
Підручник орієнтовано передусім на студентів бакалавратів «Прикладна математика», «Комп’ютерні науки», а також студентів економічних спеціальностей. Він буде корисний всім фахівцям, яким необхідно освоїти і використовувати математичний апарат оптимізації.
www.mediafire.com/?8dgpduk1f1wy6r1 (5,6 мб, djvu)
Зеркало