Симплекс-метод решения задач линейного программирования

Основные данные о работе

Версия шаблона	2.1
ЦДОР	Арзамасский
Вид работы	Творческое эссе
Название дисциплины	Методы оптимизации
Тема	Симплекс-метод решения задач линейного программирования
Фамилия	Стешин
Имя	Сергей
Отчество	Олегович
№ контракта	10300100609017

 

Основная часть

Определение ЗЛП

 

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

 

                                                  (9.1)

 

при условиях

 

	(9.2)
	(9.3)
	(9.4)

 

где - заданные постоянные величины и .

Функция (9.1) называется целевой функцией (или линейной формой) задачи (9.1)-(9.4), а условия (9.2)-(9.4) – ограничениями данной задачи.

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

 

                                               (9.5)

при выполнении условий:

 

	(9.6)
	(9.7)

где .

 

Первый алгоритм симплекс метода

 

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

 

 

Пусть известен начальный  опорный план с базисом , т.е. - базисные компоненты, - небазисные компоненты.

Вычисления удобно выполнять, заполняя следующую симплекс-таблицу:

 

			C		…		…
№		P	B		…		…		t
1					…		…
…	…	…	…	…	…	…	…	…
					…		…
…	…	…	…	…	…	…	…	…
m					…		…
					…		…

 

Порядок вычислений по первому алгоритму:

Шаг 1. Найти обратную к матрицу .

Шаг 2. Вычислить коэффициенты разложения векторов условий по базису , используя расчётную формулу:

 

 

и заполнить ими столбцы  симплекс-таблицы нулевой итерации.

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

Полученными значениями заполнить  -ю строку симплекс-таблицы.

Шаг 4. Проверить оптимальность опорного плана.

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

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

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

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

 

,

 

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

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

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

Шаг 6. Заполнить новую симплекс-таблицу в следующей последовательности.

На  -тых позициях столбцов и записать соответственно и , а на остальных позициях этих столбцов оставить прежние элементы.

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

 

 

 

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

Этим завершается построение новой симплекс-таблицы.

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

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

Алгоритм обратной матрицы

 

Опишем алгоритм применительно  к решению ЗЛП, записанной в канонической форме с односторонними ограничениями:

 

 

Пусть известен начальный опорный  план с базисом , т.е. - базисные компоненты, - небазисные компоненты.

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

Вычисления удобно выполнять, используя две симплекс-таблицы:

 

 

Основная таблица

№		P			…			t
1					…			…
…	…	…	…	…	…	…	…	…
					…
…	…	…	…	…	…	…	…	…
					…			…
					…

 

Вспомогательная таблица

№			…
1			…
…	…	…	…	…
			…
			…
0			…
1			…
2			…
…	…	…	…	…

Порядок вычислений по второму алгоритму

Шаг 1. Найти обратную матрицу и заполнить её элементами столбцы , основной симплекс-таблицы.

Шаг 2. Вычислить значение линейной формы как скалярное произведение столбцов и основной таблицы. Результат занести в строку столбца основной симплекс-таблицы.

Шаг 3. Вычислить значения элементов вектора-строки по формуле , как скалярное произведение столбцов и основной симплекс-таблицы. Полученными значениями заполнить -ю строку основной симплекс-таблицы.

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

Шаг 5. Проверить оптимальность опорного плана.

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

Если среди оценок найдутся отрицательные ( ), то для построения нового опорного плана необходимо найти вектор, который будет вводиться в базис. Он определяется по номеру наименьшей отрицательной оценки и, таким образом, устанавливается разрешающий столбец .

Шаг 6. Вычислить коэффициенты разложения вектора по базису , используя формулу , как произведение -ой строки обратной матрицы из основной таблицы на столбец вспомогательной таблицы. Полученные значения занести в столбец основной симплекс-таблицы.

Шаг 7. Определить вектор, выводимый из базиса. Для этого необходимо заполнить столбец основной таблицы значениями путем деления элементов столбца основной таблицы на соответствующие им по номеру элементы столбца основной таблицы.

Если все  , то исходная задача неразрешима в силу неограниченности сверху линейной формы . На этом процесс решения ЗЛП завершается.

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

Шаг 8. Для заполнения новой основной таблицы вычислить по рекуррентным формулам новые значения параметров итерации.

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

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

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

 

 

Список использованных интернет-ресурсов

№ п/п	Наименование интернет-ресурса	Ссылка на конкретную используемую страницу интернет-ресурса
1	Найдётся всё	www.yandex.ru