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

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

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

 
 

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

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

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

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

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

Организационно-ознакомительная  часть

Нарисуйте таблицу с нужным числом строк и столбцов, нажав соответствующую кнопку. Заполните первую строчку таблицы коэффициентами f(x), левый столбец - номерами базисных переменных, внутренние поля таблицы - элементами расширенной матрицы системы. Для оценки правых частей используйте кнопку «ОЦЕНИТЬ Своб/Xn», выделив любой элемент соответствующего столбца, при этом оценки появятся в правом столбце. Выбирайте разрешающий элемент (начиная со 2-го шага) в нижней строке таблицы.  Для совершения симплекс-перехода выделите разрешающий элемент и нажмите кнопку «SIMPLEX» . Последняя клетка столбца «Своб» содержит текущее значение целевой функции.

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

Текст программы 

Private Sub DrawTab_Click() 'Нарисовать таблицу

m = Val(InputBox("Задайте  число уравнений (не>20):"))

If m < 1 Or m > 20 Then

    MsgBox ("Неверно  задано число уравнений!")

    GoTo 1

End If

n = Val(InputBox("Задайте  число переменных (не>20):"))

If n < 1 Or n > 20 Then

    MsgBox ("Неверно  задано число переменных!")

    GoTo 1

End If

For i = 1 To m + 3

    Cells(i, 1).Select

    With Selection.Borders(xlEdgeLeft)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(i, 1).Borders(xlEdgeRight)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(i, 1).Borders(xlEdgeTop)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(i, 1).Borders(xlEdgeBottom)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

   

    With Cells(i, n + 3).Borders(xlEdgeLeft)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(i, n + 3).Borders(xlEdgeRight)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(i, n + 3).Borders(xlEdgeTop)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(i, n + 3).Borders(xlEdgeBottom)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

Next i

For j = 1 To n + 3

    With Cells(1, j).Borders(xlEdgeLeft)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(2, j).Borders(xlEdgeLeft)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(m + 3, j).Borders(xlEdgeLeft)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(1, j).Borders(xlEdgeRight)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(2, j).Borders(xlEdgeRight)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(m + 3, j).Borders(xlEdgeRight)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(1, j).Borders(xlEdgeTop)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(2, j).Borders(xlEdgeTop)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(m + 3, j).Borders(xlEdgeTop)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(1, j).Borders(xlEdgeBottom)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(2, j).Borders(xlEdgeBottom)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

    With Cells(m + 3, j).Borders(xlEdgeBottom)

            .LineStyle = xlContinuous

            .Weight = xlMedium

    End With

Next j

For j = 2 To n + 1

    Cells(2, j).Value = "X" + Str$(j - 1)

Next j

Cells(2, n + 2).Value = "Своб"

Cells(2, n + 3).Value = " Своб /Xn"

Cells(1, 1).Value = "f(x)"

Cells(2, 1).Value = "Переменные"

Cells(m + 3, 1).Value = "f(x) после подстановки"

Columns("A:A").Select

Selection.Columns.AutoFit

Cells(1, 1).Select

Cells(100, 100).Value = m

Cells(100, 101).Value = n

Cells(25, 1).Value = "Заполните  таблицу данными, затем выберите  наименьшее отрицательное значение  в поле: 'f(x)' и нажмите: 'Оценить Своб/Xn'"

1

End Sub 

Private Sub SXn_Click() 'SXn

Cells(25, 1).Value = ""

If Cells(100, 100).Value = "" Or Cells(100, 101).Value = "" Then

    MsgBox ("Не задано число уравнений и/или переменных!" + Chr(13) + "Воспользуйтесь кнопкой НАРИСОВАТЬ ТАБЛИЦУ")

    GoTo 1

End If

m = Cells(100, 100).Value

n = Cells(100, 101).Value 
 

adr$ = ActiveCell.Address

l = Len(adr)

p = InStr(2, adr, "$")

adrR$ = Right(adr, l - p)

adrC$ = Mid(adr, 2, l - Len(adrR$) - 2)

   

y = Asc(adrC$) - 65 

If y < 1 Or y > n Then

    MsgBox ("Выбран столбец вне пределов таблицы!")

    GoTo 1

End If 

For i = 1 To m

    If Cells(i + 2, y + 1).Value = 0 Then

        Cells(i + 2, n + 3).Value = ""

        Else

        Cells(i + 2, n + 3).Value = Cells(i + 2, n + 2).Value / Cells(i + 2, y + 1).Value

    End If

Next i

Cells(25, 1).Value = "Выберите наименьшее значение в столбце: 'Своб/Xn', затем выберите разрешающий элемент и нажмите 'SIMPLEX'"

1

End Sub 

Private Sub Simplex_Click() 'Симплекс-преобразование

Cells(25, 1).Value = ""

If Cells(100, 100).Value = "" Or Cells(100, 101).Value = "" Then

    MsgBox ("Не задано число уравнений и/или переменных! Воспользуйтесь кнопкой НАРИСОВАТЬ ТАБЛИЦУ")

    GoTo 1

End If

m = Cells(100, 100).Value

n = Cells(100, 101).Value

ReDim a(m, n), c(n), b(m), w(m) 
 

adr$ = ActiveCell.Address

l = Len(adr)

p = InStr(2, adr, "$")

adrR$ = Right(adr, l - p)

adrC$ = Mid(adr, 2, l - Len(adrR$) - 2)