Контрольная работа: Программная реализация симплекс-метода

Область называется областью допустимых значений (ОДЗ) задач линейного программирования. Соотношения (2), (3) называются системами ограничений задачи ЛП. Так как , то можно ограничиться изучением задачи одного типа.

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

Другая форма представления задачи ЛП – каноническая. Она имеет вид:

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

2. Описание метода решения

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

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

Рассмотрим задачу ЛП в канонической форме. Будем искать решение задачи (6), (7), (8).

(6)

(7)

(8)

0.Положим k = 1. Взяв переменные за свободные и положив их равными нулю, а , переобозначив в , - за базисные, находим первую крайнюю точку:

.

1.Заполним начальную допустимую симплекс-таблицу

	…			…
		…		0	…	0	0
		…		1	…	0
…	…	…	…	…	…	…	…
		…		0	…	1

где - вектор коэффициентов целевой функции,

- вектор свободных членов,

- матрица коэффициентов.

2.Если для k-той крайней точки все , то эта точка оптимальная, переход на пункт 7.

В остальных случаях переход к пункту 3.

3.Находим ведущий столбец . Правило выбора: выбираем столбец, в котором самый минимальный коэффициент среди отрицательных:

4.Находим ведущую строку по правилу:

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

Таким образом, ведущий элемент .

5.Выполняем один шаг метода Гаусса: выводим переменную с индексом из числа базисных, а переменную с индексом вводим в базис. Новые элементы ведущей строки находятся по формуле:

Новые значения элементов остальных строк матрицы: