Главная Финансы деньги и налоги Философия Физика и энергетика Управление Схемотехника Стратегический менеджмент Статистика Соцобеспечение Семейное право Программирование компьютеры и кибернетика Охрана окружающей среды экология Основы права Медицина Криминалистика и криминология Коммуникации и связь Кибернетика Качество упр-е качеством КСЕ Информатика ВТ телекоммуникации Журналистика Государство и право Биографии Банковское дело Карта сайта	Рефераты. Линейное программирование	Отношение
		-3	-2						-
			2					6
		2						8
		-1							-
								2	-

Столбец, ассоциированный с вводимой переменной – ведущий столбец; строка, соответствующая исключаемой переменной – ведущая строка; на их пересечении – ведущий элемент.

Поиск нового базисного решения осуществляется методом исключения переменных (метод Жордана-Гаусса). Этот процесс включает в себя вычислительные процедуры двух типов.

Тип 1. Формирование ведущего уравнения

Новая ведущая строка = предыдущая ведущая строка/ведущий элемент

Тип 2. Формирование остальных уравнений

Новое уравнение = предыдущее уравнение – (коэффициент ведущего столбца предыдущего уравнения)*(новая ведущая строка)

Новая симплекс-таблица, полученная после проведения рассмотренных операций:

 

Решение

Отношение

-

-

-

-

-

-

xI – вводимая переменная (т.к. коэффициент в -уравнении -1/2). Исключаемая переменная s1, (отношение 4/3 – минимальное). Снова проведём вычисления двух типов. Последняя симплекс-таблица соответствует оптимальному решению задачи, т.к. в -уравнении ни одна из небазисных переменных не фигурирует с отрицательными коэффициентами.

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

4.2.3. Искусственное начальное решение

Для получения начального базисного решения мы использовали остаточные переменные. Однако когда исходное ограничение записано в виде равенства или имеет знак, нельзя сразу же получить НДБР. Поэтому были разработаны два метода, в которых используется «штрафование» искусственных переменных.

1.                 Метод больших штрафов (М-метод)

Рассмотрим линейную модель, приведённую к стандартной форме:

минимизировать

при ограничениях

В первом и втором уравнениях нет переменных, исполняющих роль остаточных. Поэтому введём в каждое из этих уравнений по одной из искусственных переменных R1 и R2:

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

минимизировать

при ограничениях

Теперь если

,то начальное допустимое решение:

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

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

получим выражение для :

Решение представлено в сводной таблице:

Итерация

Решение

Отношение

-

-

-

Страницы: 1, 2, 3, 4