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

Раздел Науковедение
/
Алгоритм симплекс-метода

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

Выберите учебное заведение

Алгоритм симплекс-метода

Алгоритм симплекс-метода - раздел Науковедение, Дисциплин ОСНОВЫ СИСТЕМНОГО АНАЛИЗА Пусть Рассматриваемая Злп Решается На Нахождение Максимума Целевой Функции....

Пусть рассматриваемая ЗЛП решается на нахождение максимума целевой функции.

Алгоритм симплекс-метода состоит в выполнении следующих шагов.

1. Составить первую симплекс-таблицу, исходя из условий задачи.

2. Проверить критерий оптимальности. Если он выполняется, то опорный план является оптимальным, т.е. он имеет значение = (0, 0, …, 0, b₁, b₂, …, b_m). Соответствующее значение целевой функции определяется соотношением z = z₀.

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

3. Определить переменную, которую необходимо ввести в базис. Для этого в оценочной строке определить наибольший по абсолютной величине отрицательный элемент. Столбец, содержащий наибольшую по абсолютной величине отрицательную оценку, помечается стрелкой и называется разрешающим столбцом (s-й столбец). Он помечается вертикальной стрелкой.

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

5. Определить переменную, которую необходимо вывести из базиса. Для этого определяется строка, содержащая наименьшее симплексное отношение. Она помечается стрелкой. Эта строка является разрешающей (r-я строка).

6. Выделить разрешающий элемент, стоящий на пересечении разрешающей строки и разрешающего столбца.

7. Перейти к новой симплексной таблице, в которой переменные x_r и x_s меняются местами.

8. Заполнить клетки новой симплексной таблицы следующим образом.

· В клетке, соответствующей разрешающему элементу старой таблицы, записать обратную величину .

· Все остальные элементы r-й строки вычислить делением соответствующих элементов старой таблицы на разрешающий элемент:

· Все остальные элементы s-го столбца вычислить делением соответствующих элементов старой таблицы на разрешающий элемент с изменением знака частного на противоположный:

· Остальные элементы новой симплексной таблицы вычислить по правилу прямоугольника:

· Столбец симплексных отношений остается незаполненным. Он заполняется при необходимости перехода к новой симплексной таблице.

9. Перейти к пункту 2.

Развернуть

Открыть в широком формате

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

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

Дисциплин ОСНОВЫ СИСТЕМНОГО АНАЛИЗА

ЛУГАНСКИЙ НАЦИОНАЛЬНЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ... Кафедра физико математических дисциплин...

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

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

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

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

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

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

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

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

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

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

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

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

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

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