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

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

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

Поделиться | 
 

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

Перейти вниз 
На страницу : Предыдущий  1, 2
АвторСообщение
5ballov
Admin
avatar

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

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

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



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

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

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

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

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

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



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

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

находим разрешающий элемент
Х = {16/1; 14/2; 4/2} = min {16;7;2;} = 2

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

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

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

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



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

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

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

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

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

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



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

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

а почему во второй таблице вместо оставшихся базисных переменных х5 и х6 записаны х4 и х5?
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

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

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

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



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

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

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

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

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

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



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

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

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

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

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

Заполним первую строку таблицы. В предыдущей таблице элемент первого (направляющего) столбца   a₁₁ = 1. Это значит, что из первой строки предыдущей таблицы нужно вычесть один раз третью (направляющую) строку новой таблицы.
Вычислим:
16 − 1·2 = 14;   1 − 1·1 = 0;   2 − 1·1 = 1;   1 − (−1)·1 = 2
2 − 1· ½ = ³⁄₂;   1 − 0 = 1;   0 − 0 = 0;   0 − ½ = −½
Занесём найденные значения в новую таблицу (составленную под предыдущей).
Ещё немного — и первый шаг завершён.


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



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

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

то есть для второй строки:
элемент первого (направляющего) столбца a₁₁ = 2.
Это значит, что из второй строки предыдущей таблицы нужно вычесть два раза третью строку новой таблицы.
14− 2·2 = 10;
2 − 2·1 = 0
1 − 2·1 = -1;
2 − 2·(-1) = 4;
1 − 2·0,5 = 0;
0 − 2·0 = 0;
1 − 2·0 = 1;
0 − 2·0,5 = -1;

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

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

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

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



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

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

Δ0= -М * 14 - М *10 +2*2 = -24М +4
Δ1= -М * 0 - М *0 +2*1 -2 = 0
Δ2= -М * 1 + М *1 +2*1 -1 = 1
Δ3= -М * 2 - М *4 - 2*1 -1 = -6М-3
Δ4= -М * 3/2 - М *0 +2*1/2 -2 = -3/2 М +1 = -3/2 M - 1
Δ5= -М * 1 - М *0 +2*0 -(-М) = 0
Δ6= -М * 0 - М *1 +2*0 -(-М) = 0
Δ7= -М * 1/2 + М *1 +2*1/2 -(-М) = 1,5М +1
наименьшая оценка -6М-3 соответственно выбираем столбец х3
Вернуться к началу Перейти вниз
Посмотреть профиль
5ballov
Admin
avatar

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

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

Подправил, дописал. Теперь небольшая пауза перед началом следующей итерации.
1) Обратите внимание, что оценки   Δ   в базисных столбцах равны нулю. Это для проверки правильности вычислений.
2) Переменную   x₇   мы ввели в базис искусственно. Теперь она из базиса выведена. Её оценка   Δ₇   стала положительной. Эта переменная нам больше не нужна. Вычёркиваем из таблицы столбец   x₇.
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
5ballov
Admin
avatar

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

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













2112−M−M
БCбbx₁x₂x₃x₄x₅x₆θ
x₅−M14012³⁄₂10
x₆−M100−14001
x₁2211−1½00Δ−24·M + 401−6·M − 3−³⁄₂·M − 100
Вернуться к началу Перейти вниз
Посмотреть профиль http://5ballov.pp.ua/
Спонсируемый контент




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

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

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