Содержание

1. Цель работы

2. Постановка задачи

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

4. Программная реализация

4.1. Описание основных процедур и функций

4.2. Блок-схемы основных процедур

4.3. Листинг

5. Контрольный пример

1.Цель работы.

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

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

2.Постановка задачи.

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

3.Описание метода.

Для решения производственных задач линейного программирования существует множество методов. Рассмотрим один из них.

Симплексный метод

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

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

ƒ = C0 + C1x1 + C2x2 + .+ Cnxn

и система m линейных уравнений с n неизвестными. Это называется системой ограничений:

a11x1 + a12x2 + .+ a1nxn = b1

a21x1 + a12x2 + .+ a2nxn = b2

.

am1x1 +am2x12 + .+ amnxn = bm

Целевую функцию представим в виде:

ƒ - C1x1-C2x2 - .-Cnxn = C0

Составим симплекс-таблицу.В дальнейшем будем считать, что ранг матрицы системы ограничений равен r.В системе ограничений выбран базис(основные неизвестные)x1,x2, .xn и коэффициенты в правой части не отрицательны.

В этом случае система ограничений будет иметь вид:

x1 + .+ a1,r+1xr+1 + .+ a1nxn = b1

x2 + a2,r+1xr+1 + .+ a2nxn = b2

.

xr+ ar,r+1xr+1 + .+ arnxn = br

Тогда целевая функция имеет вид:

ƒ + Cr+1xr+1 + Cr+2xr+2 - .- Cnxn = C0

Нахождение оптимального плана симплексным методом включает следующие этапы:

1. Находят опорный план.

2. Составляют симплекс-таблицу. В общем виде:

3. В нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент Со). Если таких чисел нет, то данное базисное решение является оптимальным.

4. Пусть элемент Сj<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует.

5. Если положительный коэффициент в j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число aij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение bi/aij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.

6. В новой симплекс-таблице в столбце базисных неизвестных вместо xi пишется xj. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками.

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

4.Программная реализация.

4.1.Описание основных процедур и функций

-procedureMain – главная процедура, вызывающая все остальные.

-functionRes – поиск отрицательных значений в строке F

-procedureMinPlusDate – отыскание положительных коэффициентов в главном столбце и наименьшего частного при делении базисных неизвестных на коэффициенты в главном столбце

-proceduredivizion – деление главной строки на соответствующий коэффициент

-procedureAdding – получение нулей, путём сложения главной строки, умноженной на соответствующий коэффициент с другими строками

4.2.Блок-схемы основных процедур