рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Симплексным методом

Симплексным методом - раздел Науковедение, Основы системного анализа Решение Злп Графическим Методом Является Наглядным И Удобным В Случае Двух Пе...

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

 

В зависимости от вида ограничений различают две формы общей модели ЗЛП: каноническую и стандартную.

ЗЛП называется канонической, если ограничения представлены в виде равенств:

z = c1x1 + c2x2 + … + cnxn

xj ³ 0, j = 1, 2,…, n, m < n.

Эти соотношения можно записать в векторной форме:

xj ³ 0; i = 1, 2,…, m; j = 1, 2,…, n; m < n.

ЗЛП называется стандартной, если ограничения представлены в виде неравенств, содержащих знаки ≤ или ≥. В векторной форме эти соотношения имеют вид:

;

или ;

xj ³ 0, i = 1, 2,…, m, j = 1, 2,…, n, m < n.

Необходимо найти такие значения x1, x2, … , xn, которые обращают в максимум целевую функцию.

Любая стандартная ЗЛП может быть приведена к ЗЛП в каноническом виде с помощью введения неотрицательных переменных xn+i, которые называют дополнительными. В целевую функцию они входят с нулевыми коэффициентами. В ограничения, содержащие знаки , дополнительные переменные входят с коэффициентом «1», а в ограничения, содержащие знаки ≥, дополнительные переменные входят с коэффициентом «–1»:

i = 1, 2, …, m ;

или

i = 1, 2, …, m.

При сведении стандартной ЗЛП, имеющей ограничения со знаком , к ЗЛП в каноническом виде, коэффициенты при переменных xn+i образуют систему m линейно независимых векторов, представляющую базис.

Переменные xn+1, xn+2, …, xn+m называются базисными переменными, а остальные – свободными.

Замечание: Если в системе ограничений из коэффициентов при m переменных xn+1, xn+2, …, xn+m невозможно составить единичную матрицу m-го порядка, то необходимо выбрать базис и найти разложение всех векторов по этому базису.

Из математической модели ЗЛП следует, что в допустимом решении X0 базисные переменные равны правым частям соответствующих ограничений, а свободные переменные равны нулю: X0 = (0, 0, …, 0, b1, b2, …, bm).

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

Симплекс-методом ЗЛП решается за конечное число шагов (итераций). На первом шаге отыскивается исходный опорный план, содержащий не более m ненулевых компонент, где m – число строк. На каждом последующем шаге осуществляется нахождение нового опорного плана со значением целевой функции не хуже, чем на предыдущем шаге.

Условия задачи, а также все вычисления при решении ЗЛП симплекс-методом будем оформлять в виде симплекс-таблиц (таблица 1).

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

В клетке оценочной строки, соответствующей свободным членам, записывается значение целевой функции z0 при первоначальном опорном плане.

– Конец работы –

Эта тема принадлежит разделу:

Основы системного анализа

Луганский национальный аграрный университет.. Кафедра физико математических дисциплин..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Симплексным методом

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ
  Контрольную работу необходимо выполнить в отдельной ученической тетради, на внешней обложке которой необходимо указать изучаемую дисциплину, номер академгруппы, фамилию и инициалы с

Решаемой графическим методом
Пусть дана задача линейного программирования (ЗЛП) с целевой функцией z = c1x1 + c2x2 и ограничениям

Алгоритм симплекс-метода
Пусть рассматриваемая ЗЛП решается на нахождение максимума целевой функции. Алгоритм симплекс-метода состоит в выполнении следующих шагов.   1. Составить первую симп

Решение.
Составим математическую модель задачи. Обозначим x1, x2, x3 соответственно количество изделий видов А, В, С.

Постановка и методика решения М-задачи
Симплекс-метод удобно применять, когда все ограничения ЗЛП содержат неравенства ≤. В этом случае дополнительные переменные образуют базис и исходный опорный план очевиден. В противном случае,

Формализация распределительной задачи
  Транспортной (распределительной) задачей называется задача определения оптимального плана перевозок груза из заданных пунктов отправления в заданные пункты п

Метод северо-западного угла
Заполнение распределительной таблицы начинается с левого верхнего (северо-западного) угла, и продолжается при продвижении по строке вправо или по столбцу вниз. В клетку (1; 1) записывают величину

Решение транспортной задачи методом потенциалов
Для решения транспортной задачи используют метод потенциалов (модифицированный распределительный метод). Потенциалами называются числа

Плана перевозок
Предполагается, что транспортная задача решается на минимум целевой функции.   1. Осуществляется выбор перспективной клетки с наибольшей по модулю отрицательной оценкой:

Постановка и методика решения открытой транспортной задачи
Любая транспортная задача, у которой суммарная величина запасов равна суммарному объему потребления, называется закрытой и всегда имеет решение. В противном случае задача на

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги