Готовимся к зачёту и сессии

Обсуждение задач по математике, физике, экономическим, техническим и гуманитарным дисциплинам. Оказание услуг по выполнению студенческих контрольных и курсовых работ. Вы обязательно найдёте тех, с кем можно обсудить тот или иной вопрос по данной тематике!
 
ФорумФорум  ПорталПортал  КалендарьКалендарь  ЧаВоЧаВо  ПоискПоиск  ПользователиПользователи  ГруппыГруппы  РегистрацияРегистрация  Вход  
Последние темы
Поиск
 
 

Результаты :
 
Rechercher Расширенный поиск

Поделиться | 
 

 Решение задач линейного программирования симплекс- методом

Перейти вниз 
На страницу : 1, 2  Следующий
АвторСообщение
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Решение задач линейного программирования симплекс- методом   Ср Апр 20, 2011 6:27 pm

Задание следующее:
Решить задачу симплекс методом.
{ x1 + 2x2 +x3 + 2x4 = 16
{ 2x1 + x2 + 2x3 + x4 = 14
{ 2x1 + 2x2 - 2x3 + x4 = 4

x1,x2,x3,x4 => 0

F = 2x1+x2+x3+2x4 -> max

Из теории я поняла, что
а) задача должна быть записана в канонической форме (здесь она уже дана в канонической форме)
б) количество неизвестных должно быть больше количества уравнений (это соответствует)

решение:
Первым делом нужно найти допустимое базисное решение, которое бы максимизировала целевую функцию F, т.е необходимо найти оптимальное решение задачи.
Для это надо определить количество основных (базисных) переменных и неосновных. А вот только как это сделать, и как вычислить значения базинсных переменных через свободные я не поняла.... Количество базисных переменных обязательно должно равняться числу уравнений? и как определить какая переменная должна быть базисной а какая неосновной?
помогите пожалуйста,...)
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Ср Апр 20, 2011 6:41 pm

количество неизвестных должно быть больше количества (уравнений) ограничений, пусть даже в виде неравенств.
Это вовсе необязательно.
Что же касается канонического вида задачи — в Вашем случае система не содержит базиса. Метод искусственно базиса Вы будете изучать позже. На Вашей задаче нельзя начинать изучать симплекс-метод (это вовсе не означает, что задача не решается).
Рекомендую выбрать другую задачу с ограничениями-неравенствами вида ≥, и я смогу показать Вам симплекс-метод.
Поймите, что привести задачу к каноническому виду (в виде ограничений-равенств) и решить её симплекс-методом — это не одно и то же.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Чт Апр 21, 2011 7:17 am

Валентин, а другую задачу нет смысла выбирать, решать все-равно придется этуSmile
Я понимаю, что привести к каноническому виду и решать симплекс-методом это не одно и то же. В моем случае для решения задачи симплекс методом дана задача уже в такой форме.

В методичке была разобрана задача как пример решения симплекс-методом. С той задачей более ли менее было все понятно, там у всех базисных переменных был коэффициент один, и с ней было проще разобраться. Какие преобразования делать в таблицах я немного поняла. А вот в этой задаче зависла на самом начале, так как на образец она совсем не похожа.....
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Чт Апр 21, 2011 9:14 am

Напишу пока кратко и своими словами. Ограничения заданы уравнениями. Уравнений 3, переменных — четыре, переменные неотрицательны. Наибольшие и наименьшие значения мы ищем в угловых точках. При этом как минимум одна переменная обратится в ноль. Если мы не приме́ним метод искусственного базиса, придётся выбирать базисные переменные наудачу. И не факт, что с первой попытки мы получим допустимое (неотрицательное) решение.
Уточните, пожалуйста, требуемый от Вас метод: применять или не применять метод искусственного базиса. Если применять, то в каком виде: одноэтапный или двухэтапный?
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Чт Апр 21, 2011 9:47 am

Честно говоря, я сама запуталась.
Тема - решение задач симплекс-методом, следуящая тема метод искусственого базиса, а затем тема про двойственность задач линейного программирования.
В контрольной на эти 3 темы есть 2 задачи:
Первая это та, которую я выложила. Задание - решить симплекс-методом
Вторая на двойственность.

Поэтому я думаю, что при решении этой задачи метод искусственного базиса можно применять и наверное даже нужно.... Одноэтапный или двухэтапный не знаю...в чем разница?
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Чт Апр 21, 2011 11:23 am

Я лучше начну показывать с объяснениями. Пересказывать теорию — неблагодарное дело Smile
Задача не содержит базиса. Введём искусственные базисные переменные   x₅, x₆, x₇ ≥ 0. Добавим эти переменные в целевую функцию таким образом, чтобы их ненулевые (положительные) значения ухудшали целевую функцию. Поскольку целевая функция стремится к максимуму, — добавим их в целевую функцию с коэффициентами   −M, где   M → +∞ — бесконечно большое положительное число.
В итоге получим M-задачу линейного программирования. Это и есть одноэтапный (одномоментный) метод искусственного базиса.

{1·x₁ + 2·x₂ + 1·x₃ + 2·x₄ + 1·x₅ = 16
{2·x₁ + 1·x₂ + 2·x₃ + 1·x₄ + 1·x₆ = 14
{2·x₁ + 2·x₂ − 2·x₃ + 1·x₄ + 1·x₇ = 4
{xj ≥ 0   (j = 1, …, 7)

F = 2·x₁ + 1·x₂ + 1·x₃ + 2·x₄ − M·x₅ − M·x₆ − M·x₇ → max

Единичные коэффициенты я записал для Вашего же удобства, чтобы легче было внимательно и без ошибок заполнить симплекс-таблицу.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Пн Апр 25, 2011 5:56 pm

У меня получилась вот такая симплекс-таблица
[Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]

Теперь как я понимаю. надо найти разрешающий элемент. просматриваем последнюю строку, среди коэфф. надо выбрать наименьшее отрицательное число. так как функция стремиться к максимуму.
А что делать, если здесь два наименьших коэффициента?
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Пн Апр 25, 2011 6:27 pm

Симплекс-таблица составлена неверно. Она не соответствует M-задаче (одномоментному методу искусственного базиса). В частности, неверно найдено начальное значение целевой функции. Она на этом этапе должна быть равна −34·M.
Таблицы учат составлять (оформлять) по-разному, но считаются они одинаково. Например, можно включить в таблицу столбец с коэффициентами при базисных переменных. Не хватает в ней также строки с оценками Δ, либо неверно найдены сами оценки.
Покажите, пожалуйста, какого вида таблицы вам дают в учебнике или методичке. Как я всегда говорю, задачу надо не только правильно решить, но и успешно сдать, выполнив требования именно Вашего преподавателя.
И о рисунках в сообщениях. Желательно, чтобы картинки не исчезали, размещать их на фотохостингах с регистрацией. Например, пользуетесь ли Вы Яндекс-почтой постоянно? Если да — то почему бы не создать для форума специальный альбом в сервисе Яндекс-фоток?
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Ср Апр 27, 2011 1:38 pm

Чтобы не объяснять на пальцах в каком виде у нас даются симплекс-таблицы, размещаю ссылку на методичку. Вы в ней поймете полюбому больше, чем я Very Happy
[Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Ср Апр 27, 2011 2:47 pm

Составим симплекс-таблицу на основе M-задачи линейного программирования.

{1·x₁ + 2·x₂ + 1·x₃ + 2·x₄ + 1·x₅ = 16
{2·x₁ + 1·x₂ + 2·x₃ + 1·x₄ + 1·x₆ = 14
{2·x₁ + 2·x₂ − 2·x₃ + 1·x₄ + 1·x₇ = 4
{xj ≥ 0   (j = 1, …, 7)

F = 2·x₁ + 1·x₂ + 1·x₃ + 2·x₄ − M·x₅ − M·x₆ − M·x₇ → max





















2112−M−M−M
Базис (Б)Cбbx₁x₂x₃x₄x₅x₆x₇θ
x₅−M16121210016
x₆−M1421210107
x₇−M422−210012 (min)
Δ−34·M−5·M − 2−5·M − 1−1·M − 1−4·M − 2000
 
x₅−M14012³⁄₂10−½
x₆−M100−14001−1
x₁2211−1½00½Δ−24·M + 401−6·M − 3−³⁄₂·M − 100³⁄₂·M + 1
Симплекс-таблицу я заполнил не до конца. В частности, второй столбец и последнюю строку. До сих пор таблица понятна?


Последний раз редактировалось: Admin (Пн Май 16, 2011 8:21 am), всего редактировалось 14 раз(а)
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Ср Апр 27, 2011 4:32 pm

В принципе да.
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Ср Апр 27, 2011 6:28 pm

Уже хорошо. Заполним второй столбец коэффициентами при базисных переменных   x₅, x₆, x₇. Я заполнил. Теперь перейдём к вычислению оценок   Δ. Опишите, как Вы будете их вычислять.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Чт Апр 28, 2011 7:15 pm

Если честно, то что такое оценки Δ я даже не представляю. В методичке ни в одном из примеров не было такой строки...
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Чт Апр 28, 2011 7:40 pm

В Вашей методичке это соответствует последней строке таблицы. Мы же рассматриваем задачу посложнее — метод искусственного базиса. Как я говорил, шапку таблицы можно оформить и по-другому. И Вам будет полезно оформить потом симплекс-таблицы в соответствии с методичкой. Они даны у Вас в сокращённой форме, я же показываю в полной, так легче разобраться.
Начнём. Нужно столбец Cб скалярно умножить на соответствующий столбец коэффициентов при неизвестных в уравнениях и отнять в каждом столбце, кроме первого (нулевого) коэффициент при неизвестной в целевой функции.
Заполним нулевую ячейку:   Δ₀ = −M·16 − M·14 − M·4 = −34·M
Первая ячейка:   Δ₁ = −M·1 − M·2 − M·2 − 2 = −5·M − 2
В таблицу я дописал. Подсчитайте значения в остальных ячейках.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Сб Апр 30, 2011 12:53 pm

По аналогии заполняем:
Δ2 = −M·2 − M·1 − M·2 − 1 = −5·M − 1
Δ3 = −M·1 − M·2 + M·2 − 1 = −1·M − 1
Δ4 = −M·2 − M·1 − M·1 − 2 = −4·M − 2
Δ5 = −M·1− M·0 − M·0 − 0 = −1·M
Δ6 = −M·0− M·1 − M·0 − 0 = −1·M
Δ6 = −M·0− M·0 − M·1 − 0 = −1·M


Только я не поняла почему во втором столбце коэффициенты -М. В равентсвах они же с плюсом....
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Сб Апр 30, 2011 1:58 pm

Ошибки Ваши я подчеркнул. Можете их исправить.
Во второй столбец перенесены коэффициенты при неизвестных в целевой функции. Она стремится к максимуму. С минусом коэффициенты при искусственных базисных переменных взяты, чтобы они ухудшали целевую функцию до тех пор, пока не будут выведены из базиса.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Сб Апр 30, 2011 2:36 pm

во втором столбце взяты коэффициенты при неизвестных в целевой функции - теперь понятно. Просто я решила. что это коэффициенты при добавленных переменных в уравнениях. поэтому запуталась.
[/quote]столбец Cб скалярно умножить на соответствующий столбец коэффициентов при неизвестных в уравнениях и отнять в каждом столбце, кроме первого (нулевого) коэффициент при неизвестной в целевой функции.[quote]
к примеру для х5:
коэфф при неизв. в целевой функции -1 ? Δ5 = −M·1− M·0 − M·0 + 1 = −1·M + 1, так ?
или коэфф. -0 и будет Δ5 = −M·1− M·0 − M·0 + 0 = −1·M ....
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Сб Апр 30, 2011 4:45 pm

Сравните вычисление оценок в 1-4 столбцах и в 5-7, тогда поймёте свою ошибку.


Последний раз редактировалось: Admin (Пн Май 02, 2011 7:05 pm), всего редактировалось 1 раз(а)
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Пн Май 02, 2011 6:06 pm

Столбец Сб умножаем на соответствующий столбец коэффициентов при неизвестных в уравнениях и отнимаем в каждом столбце коэффициент при неизвестной в целевой функции
для х5, х6, х7 коэфф при неизв. в целевой функции -1
Δ5 = −M·1− M·0 − M·0 - (- 1) = −1·M + 1
Δ6 = −M·0− M·1 − M·0 - (- 1) = −1·M + 1
Δ7 = −M·0− M·0 − M·1 - (- 1) = −1·M + 1
так?
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Пн Май 02, 2011 7:05 pm

А разве коэффициенты при неизвестных   x₅, x₆, x₇   в целевой функции равны   −1?
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Пн Май 02, 2011 7:21 pm

F = 2·x₁ + 1·x₂ + 1·x₃ + 2·x₄ − M·x₅ − M·x₆ − M·x₇ → max а что не -1??
и во втором столбце были взяты кэффициенты при неизвестных в целевой функции.... -М везде было во втором столбце...
все, мозг распух я запуталась.... других вариантов у меня нет...

нет ну у меня еще есть вариант, что коэффициент - 0
Я уже раз десять сравнла вычисления во всех столбцах, ну не могу я найти ошибку....
помогите
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Пн Май 02, 2011 7:43 pm

Там коэффициенты   −M, а не   −1.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Вт Май 03, 2011 6:29 am

то есть получается
Δ5 = −M·1− M·0 − M·0 - (- М) = −1·M + М = 0
Δ6 = −M·0− M·1 − M·0- (- М) = −1·M + М = 0
Δ7 = −M·0− M·0 − M·1 - (- М) = −1·M + М = 0
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

Сообщения : 120
Дата регистрации : 2010-01-02
Откуда : Киев

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Вт Май 03, 2011 11:16 am

Правильно!
Как и следовало ожидать, оценки   Δ   для базисных переменных равны нулю. Допишем их в таблицу.
Какой предпримем следующий шаг?
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
ГаляСПБГТИ(ТУ)



Сообщения : 30
Дата регистрации : 2011-04-14

СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   Вт Май 03, 2011 7:11 pm

рискну предположить, что надо найти допустимое решение.
Вернуться к началу Перейти вниз
Посмотреть профиль
Спонсируемый контент




СообщениеТема: Re: Решение задач линейного программирования симплекс- методом   

Вернуться к началу Перейти вниз
 
Решение задач линейного программирования симплекс- методом
Вернуться к началу 
Страница 1 из 2На страницу : 1, 2  Следующий

Права доступа к этому форуму:Вы не можете отвечать на сообщения
Готовимся к зачёту и сессии :: Математика-
Перейти: