Внимание! ​more-diplom.ru не продает дипломы, аттестаты об образовании и иные документы об образовании. Все услуги на сайте предоставляются исключительно в рамках законодательства РФ.

  more-diplom

Помогаем студентам

 ​ ​работаем на территории РФ

   ЗАКАЗАТЬ РАБОТУ

Математическое программирование

Память. Виды памяти и их особенности

Способности длительно хранить информацию о событиях внешнего мира и реакциях организма и многократно использовать её в сфере сознания для организации последующей деятельности. В наиболее простой форме

Институт опеки и попечительства

Последние 10 лет в России прослеживается устойчивая тенденция увеличения количества семей, не обеспечивающих должных условий для воспитания и содержания своих детей. Итак, данное исследование актуальн

Забота государства о престарелых людях

Развитию социального обслуживания пожилых и нетрудоспособных предаётся в наше стране с каждым годом всё большее значение , оно рассматривается как крайне необходимое дополнение к денежным выплатам, зн

Иисус Христос и язычники в Евангелии

Положение, однако, оказалось более сложным. 1. Контрасты в словах и действиях а) Проявления обособленности. - Даже во время пребывания на чужой земле Иисус при возвещении Евангелия и совершении чудес

Технико-экономические показатели работы ТЭС

Технико-экономисчекие показатели ТЭС являются важнейшими показателями работы энергетического оборудования. Не зря когда распалось РАО ЕЭС России и станции продавались в частные руки, именно ими интере

Социальное управление

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

Основные понятия химии

Вещества состоят из мельчайших частиц молекул, которые находятся в непрерывном движении. При повышении температуры скорости движения молекул увеличиваются, при снижении уменьшаются. Молекулы различны

Леонард Эйлер

Деятельность Эйлера многогранна и разностороння. Он занимался почти всем, что интересовало в то время математиков. С.И. Вавилов Лучше несколько потерпеть от сурового климата страны льдов, в которой пр

Скачать работу - Математическое программирование

Симплексной форме ЗЛП соответствует симплекс - матрица : 1 0 ... 0 ... 0 a 1,r+1 ... a 1s ... a 1n b 1 0 1 ... 0 ... 0 a 2,r+1 ... a 2s ... a 2n b 2 ................................................................. 0 0 ... 1 ... 0 a i,r+1 ... a is ... a in b i ................................................................. 0 0 ... 0 ... 1 a r,r+1 ... a rs ... a rn b r 0 0 ... 0 ... 0 c r+1 ... c s ... c n b 0 Заметим, что каждому базису (системе базисных неизвестных ) соответствует своя симплекс - матрица , базисное решение х = ( b 1 ,b 2 , ... ,b r , 0, ... ,0) и базисное значение целевой функции f(b 1 ,b 2 , ... ,b r , 0, ... ,0) = b 0 ( см.

Последний столбец !). Критерий оптимальности плана . Если в последней (целевой) строке симплекс-матрицы все элементы неположительны, без учета последнего b 0 , то соответствующий этой матрице план оптимален, т.е. с j 0 (j = r+1, n) => min f (b 1 , ... ,b 2 ,0, ... ,0) = b 0 . Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец ( S -й), в котором последний элемент с s > 0, a все остальные элементы неположительны, то ЗЛП не имеет оптимального плана, т.е. с s > 0 , a is 0 ( i= 1,r ) = > min f = - . Если в симплекс-матрице не выполняются оба критерия, то в поисках оптимума надо переходить к следующей матрице с помощью некоторого элемента a is > 0 и следующих преобразований (симплексных): 1) все элементы i -й строки делим на элемент a + is ; 2) все элементы S -го столбца, кроме a is =1, заменяем нулями ; 3) все остальные элементы матрицы преобразуем по правилу прямоугольника, что схематично показано на фрагменте матрицы и дано в формулах: a kl ` = a kb a is - a il a ks = a kl - a il a ks ; a is a is b k ` = b k a is - b i a ks ; c l ` = c l a is - c s a il a is a is Определение . Элемент a is + называется разрешающим, если преобразование матрицы с его помощью обеспечивает уменьшение (невозрастание) значения, целевой функции ; строка и столбец, на пересечении которых находится разрешающий элемент, также называются разрешающими.

Критерий выбора разрешающего элемента. Если элемент a is + удовлетворяет условию b i = min b k a is 0 a ks 0 + где s 0 - номер выбранного разрешающего столбца, то он является разрешающим. 4. Алгоритм симплекс-метода (по минимизации). 1) систему ограничений и целевую функцию ЗЛП приводим к симплексной форме ; 2) составим симплекс-матрицу из коэффициентов системы и целевой функции в симплексной форме ; 3) проверка матрицы на выполнение критерия оптимальности ; если он выполняется, то решение закончено ; 4) при невыполнении критерия оптимальности проверяем выполнение критерия отсутствия оптимальности ; в случае выполнения последнего решение закончено - нет оптимального плана ; 5) в случае невыполнения обоих критериев находим разрешающий элемент для перехода к следующей матрице, для чего : а) выбираем разрешающий столбец по наибольшему из положи тельных элементов целевой строки ; б) выбираем разрешающую строку по критерию выбора разрешающего элемента ; на их пересечении находится разрешающий элемент ; 6) c помощью разрешающего элемента и симплекс-преобразований переходим к следующей матрице ; 7) вновь полученную симплекс-матрицу проверяем описанным выше способом (см. п. 3) Через конечное число шагов, как правило получаем оптимальный план ЗЛП или его отсутствие Замечания. 1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения при симплекс-преобразованиях. 2) преобразования - вычисления удобно начинать с целевой строки ; если при этом окажется, что выполняется критерий оптимальности, то можно ограничиться вычислением элементов последнего столбца. 3) при переходе от одной матрицы к другой свободные члены уравнений остаются неотрицательными ; появление отрицатель ного члена сигнализирует о допущенной ошибке в предыдущих вычислениях. 4) правильность полученного ответа - оптимального плана - проверяется путем подстановки значений базисных неизвестных в целевую функцию ; ответы должны совпасть. 5. Геометрическая интерпретация ЗЛП и графический метод решения (при двух неизвестных) Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы.

Целевая функция f = c 1 x 1 + c 2 x 2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с 1 ,с 2 ). Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают. На этих утверждениях основан графический метод решения ЗЛП. 6. Алгоритм графического метода решения ЗЛП. 1) В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений ; 2) найти полуплоскости решения каждого неравенства системы (обозначить стрелками) ; 3) найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей ; 4) построить вектор n (с 1 ,с 2 ) по коэффициентам целевой функции f = c 1 x 1 + c 2 x 2 ; 5) в семействе параллельных прямых целевой функции выделить одну, например, через начало координат ; 6) перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении вектора n и min f при движении в противоположном направлении. 7) найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы). 7. Постановка транспортной задачи.

Приведем экономическую формулировку транспортной задачи по критерию стоимости: Однородный груз, имеющийся в m пунктах отправления (производства) А 1 , А 2 , ..., А m соответственно в количествах а 1 , а 2 , ..., а m единиц, требуется доставить в каждый из n пунктов назначения (потребления) В 1 , В 2 , ..., В n соответственно в количествах b 1 , b 2 , ..., b n единиц.

Стоимость перевозки (тариф) единицы продукта из A i в B j известна для всех маршрутов A i B j и равна C ij (i=1,m; j=1,n) . Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозиться и запросы всех пунктов потребления удовлетворяются (закрытая модель), а суммарные транспортные расходы минимальны.

Условия задачи удобно располагать в таблицу, вписывая в клетки количество перевозимого груза из A i в B j груза X ij > 0 , а в маленькие клетки - соответствующие тарифы C ij : 8. Математическая модель транспортной задачи. Из предыдущей таблицы легко усматривается и составляется математическая модель транспортной задачи для закрытой модели Число r = m + n - 1 , равное рангу системы (1), называется рангом транспортной задачи. Если число заполненных клеток ( X ij ¹ 0) в таблице равно r , то план называется невырожденным, а если это число меньше r , то план вырожденный - в этом случае в некоторые клетки вписывается столько нулей (условно заполненные клетки), чтобы общее число заполненных клеток было равно r . Случай открытой модели а i ¹ b j легко сводится к закрытой модели путем введения фиктивного потребителя B n+1 c потребностью b n+1 = a i - b j , либо - фиктивного поставщика А m+1 c запасом a m+1 = b j - a i ; при этом тарифы фиктивных участников принимаются равными 0. 9. Способы составления 1-таблицы (опорного плана). I. Способ северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью вывозиться груз из А i , либо полностью удовлетворяется потребность B j . Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы a i и не удовлетворяются потребности b j . В заключение проверяют, что найденные компоненты плана X ij удовлетворяют горизонтальным и вертикальным уравнениям и что выполняется условие невырожденности плана. II. Способ наименьшего тарифа.

Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу. 10. Метод потенциалов решения транспортной задачи.

Определение: потенциалами решения называются числа a i ® A i , b j ® B j , удовлетворяющие условию a i + b j = C ij (*) для всех заполненных клеток ( i,j) . Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n неизвестными, имеющую бесчисленное множество решений; для ее определенности одному неизвестному придают любое число (обычно a 1 =0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности. Если известны потенциалы решения X 0 транспортной задачи и для всех незаполненных клеток выполняются условия a i + b j C i j , то X 0 является оптимальным планом транспортной задачи. Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличились.

НАШИ КОНТАКТЫ

Адрес

работаем на территории РФ

НОМЕР ТЕЛЕФОНА

8-800-120-79-10

График

пн-пт с 9:00-18:00 сб,вс - выходной 

Email

zakaz@​more-diplom.ru

ОБРАТНАЯ СВЯЗЬ

ДОСТУПНО 24 ЧАСА В ДЕНЬ!
Thank you! Your message has been sent.
Unable to send your message. Please fix errors then try again.