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

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

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

Пусть задача в канонической форме имеет исходный опорный план

По определению 2.3 вектор решения X = (b1, b2 _ъ......, b_т, 0,...,0) является опорным планом задачи (2.21). Этому плану соответствует следующее значение целевой функции:

Для исследования опорного плана на оптимальность и для определения направления его улучшения на основании целевой функции строится «нулевое» приведенное уравне­ние. Это уравнение получается после исключения базисных переменных из выражения целевой функции.

Подставляя x1, х₂, …, х_т из системы ограничений (2.21) в целевую функцию, получим «нулевое» приведенное урав­нение в следующем виде:

где

Коэффициенты а 0j называются оценками соответствую­щих небазисных переменных (или оценками оптимальнос­ти). Оценки позволяют охарактеризовать опорный план в виде следующих теорем-признаков возможных ситуаций.

ТЕОРЕМА 1. Если то опорный план является оптимальным (признак оптимальности опорного плана).

ТЕОРЕМА 2. Если для некоторого j и все
соответствующие этому индексу j величины , то значение целевой функции не ограничено сверху
на множестве планов.

ТЕОРЕМА 3. Если для некоторых индексов о и для каждого из этих j по крайней мере одно из чисел , то можно перейти к новому опорному плану, при котором значение целевой функции увеличивается.

Вычислительный процесс удобно вести в симплекс-таб­лицах. Исходная симплекс-таблица для задачи (2.21) с учетом «нулевого» уравнения (2.22) представлена в табл. 2.6. «Нулевое» уравнение записано в нижней части таблицы.

Под симплекс-таблицей понимается табличная форма представления математической модели в канонической фор­ме с опорным планом и оценками оптимальности.

Итак, алгоритм симплекс-метода включает в себя следую­щие основные шаги.

1. Выбор разрешающего столбца j, для которого . Пусть j=k. Следовательно, в базис вводится вектор коэффициентов переменной х_к.

2. Выбор разрешающей строки i=l, по наи­меньшему отношению элементов опорного плана к положительным элементам разрешающего столбца, т. е. для всех . Следовательно, из базиса исключается переменная x_t. Выбранное число _; называет­ся разрешающим элементом.

3. Пересчет всех элементов симплекс-таблицы по форму­лам Жордана — Гаусса:

— элементы нового опорного плана и новое значение целевой функции вычисляются но формулам:

— остальные элементы по формулам

Новая итерация начинается с п. 1.

В процессе решения в пп. 1 и 2 алгоритма учитываются указанные три признака возможных ситуаций.

Основной алгоритм симплекс-метода можно дополнить еще двумя признаками:

1. Если при выборе разрешающей строки (п. 2) мини­мальное отношение не единственное, то новый опорный план вырожденный, т. е. одна или несколько ба­зисных переменных равны нулю. В этом случае при перехо­де от одного опорного плана к другому значение целевой функции может остаться неизменным в течение нескольких итераций.

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

Многие задачи линейного программирования в канони­ческой форме не имеют исходного опорного плана. В этом случае применяется метод искусственного базиса.

Пусть следующая задача в канонической форме не имеет исходного опорного плана:

Определение:Задача вида

где М — некоторое достаточно большое положительное чис­ло, называется расширенной задачей по отношению к за­даче (2.23) — (2.25).

Расширенная задача имеет опорный план b1;...; b_т). Базисные переменные , на­зываются искусственными. Так как расширенная задача имеет опорный план, то ее можно решать симплекс-методом.

ТЕОРЕМА 4. Если в оптимальном плане X* расши­ренной задачи (2.26) — (2.28) значения искусственных пе­ременных , то X* является оптималь­ным планом задачи (2.23) — (2.25).

ТЕОРЕМА 5. Если в оптимальном плане X* расши­ренной задачи (2.26) — (2.28) хотя бы одна искусственная переменная отлична от нуля, то система ограничений (2.24) — (2.25) исходной задачи несовместна (область до­пустимых решений пустая).

Таким образом, теоремы 4 и 5 дополняют алгоритм симплекс-метода новыми условиями, которые учитываются при использовании искусственных переменных в исходной задаче.

II. Практическая часть

1. Задача 1.

‘ В модуле

Public Type struct_tov

tov As String * 1

cost As String * 1

kol As String * 1

country As String * 1

End Type

Dim c As Integer

Dim min, ind_min As Integer

Dim i, i2 As Integer

Private Sub Command1_Click()

Caption = get_cost("E")

End Sub

Public Function get_cost(country As String) As Integer

Dim t As struct_tov

get_cost = 0

Open App.Path & "\db.txt" For Random As #1 Len = Len(t)

c = LOF(1) / Len(t)

For i = 1 To c

Get #1, i, t

If t.country = country Then get_cost = get_cost + CInt(t.kol) * CInt(t.cost)

Next i

Close #1

End Function

2. Задача 2.