|
|
Алгоритм решения канонической задачи ЛП симплексным методом (метод Данцига). ⇐ ПредыдущаяСтр 2 из 2 Основная задача ЛП называется канонической, если система уравнений каноническая, а целевая функция выражена через свободные неизвестные. Рассмотрим алгоритм решения канонической задачи ЛП симплексным методом: Дано:общая задача ЛП Минимизировать при условиях:
Это общая задача ЛП. Переходим к каноническому виду:
При условиях
Здесь
Исходная симплексная таблица
Пустые клетки соответствуют нулям. Столбец контрольной суммы ( Итерация 1
Коэффициенты данной симплексной таблицы вычисляются таким образом, чтобы в разрешающем столбце исходной таблицы все элементы, кроме разрешающего, стали нулевыми. Например, для того что бы в исходной таблице в уравнении 2
Итерация 2
Итерация 3
Выписав из последней симплексной таблицы выражение для целевой функции Решая задачу максимизации
  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
;
;
.
, а 
переменные. Задача ЛП каноническая. Нетрудно убедиться, что r(A) = r(R), т.е. система ограничений совместна. Кроме того, r(A) = 4, n = 6. Составим исходную симплексную таблицу.
) включает в себя алгебраические суммы коэффициентов каждой строки и служит для контроля арифметических действий при последующем преобразовании данной таблицы. Последняя строка таблицы называется индексной. При ее заполнении свободный член целевой функции выписывается со своим знаком, а коэффициенты при неизвестных (оценки) – с противоположным. Выберем так называемый разрешающий столбец с положительной оценкой. Но таких столбцов два. Выбираемстолбец с оценкой 5. Далее выбирается так называемая разрешающая строка. Из отношений свободных членов к положительным коэффициентам разрешающего столбца (
) выбираем наименьшее т.е. 
. Это отношение и соответствует разрешающей строке.Коэффициент 3, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. Выведем 
из базиса, а 
(провокатор) введем в базис. В результате получим новые наборы базисных и свободных переменных. Необходимо выразить базисные переменные и целевую функцию через свободные переменные. Для этогоразрешающую строку в исходной симплексной таблице делим на разрешающий элемент. Результат заноситься в новую симплексную таблицу “Итерация 1”.
. Алгебраическим сложением коэффициентов строки убеждаемся, что арифметической ошибки нет.В полученной таблице «Итерация 1» выбирается положительная оценка. В частности, столбец, соответствующий оценке 7, будет разрешающим. Затем выбирается разрешающая строка и т.д. Столбец контрольной суммы для простоты можно опустить. Продолжим решение.В итоге получим следующие симплексные таблицы:
убедимся, что базисное решение 
является оптимальным (все оценки в индексной строке отрицательны), а 
.
при тех же условиях, что и раньше, получим 
. Оптимальное решение этой задачи оптимизации совпадает с оптимальным решением задачи минимизации 
.