Основные теоремы двойственности

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

КУРСОВАЯ РАБОТА

По дисциплине Математические методы

Тема: Основные теоремы двойственности

Саранск 2008г.

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

По дисциплине Математические методы

Тема: Основные теоремы двойственности

Курсовая работа выполняется на 41 листе и включает следующие разделы:

1 Двойственные задачи в линейном программировании

2 Виды двойственных задач

2.1 Симметричные двойственные задачи

2.2 Несимметричные двойственные задачи

3 Теоремы двойственности

4 Реализация двойственности на Visual Basic for Application

Введение

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

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

1  Двойственные задачи в линейном программировании

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной.

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

В качестве примера рассмотрим задачу использования ресурсов: предприятие имеет t видов ресурсов в количестве b_i (i = 1, 2, ..., m) единиц, из которых производится n видов продукций. Для производства 1 единицы i- й продукции расходуется a_ij единиц t-гo ресурса, а ее стоимость составляет c_i единиц. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении.

Обозначим через x_j (j =1,2, ..., n) количество единиц j-й продукций, Тогда исходную задачу сформулируем так.

Найти вектор X =(x₁, x₂, …, x_n), который удовлетворяет ограничениям:

x_j 0 (j =1,2, ..., n)

и доставляет максимальное значение линейной функции:

F(x) = c₁x₁ + c₂x₂ + … + c_nx_n,

Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через у_i (j =1,2, ..., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j-й продукции, равна . Стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство , j =1,2, ..., n. Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом.

Найти вектор Y =(y₁, y₂, …, y_n), который удовлетворяет ограничениям:

y_j 0 (j =1,2, ..., n),

и доставляет минимальное значение функции:

f = b₁y₁ + b₂y₂ + … + b_my_m>min

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

Исходная задача. Сколько и какой продукции x_j (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях c_j (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b_i (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении?

Двойственная задача. Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b_i и величинах стоимости единицы продукции с_i минимизировать общую стоимость затрат?

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

2 Виды двойственных задач

2.1 Симметричные двойственные задачи

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

Исходная задача. Найти матрицу Х = (x₁, x₂, …, x_n), которая удовлетворяет системе ограничений AX>A_n, X>0 и минимизирует линейную функцию Z = CX.

Двойственная задача. Найти матрицу Y = (y₁, y₂, …, y_n), которая удовлетворяет системе ограничений YA C, Y 0 и максимизирует функцию F = YA_m.

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

Исходная задача: Z = x₁ + 2x₂ + 3x₃ >min при ограничениях:

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду AX>A_n. Для этого второе неравенство следует умножить на -1.

Двойственная задача. Найти максимум функции f = 2y₁+ 3y₂ + 6y₃ + 3y₄ при ограничениях

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

Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов. Двойственную задачу решаем симплексным методом (таблица 1). Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), f_max = 21/2. Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A₅, A₆, A₇: x₁ = 3/2 + 0 = 3/2; x₂ = 9/2 + 0 = 9/2; x₃ = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Z_min =21/2.

Таблица 1

i	Базис	С базиса	An	2	3	6	3	0	0	0
				A1	A2	A3	A4	A5	A6	A7
1 2 3	A5 A6 A7	0 0 0	1 2 3	2 2 -1	-1 1 4	1 1 -2	2 -1 -2	1 0 0	0 1 0	0 0 1
m + 1	Zi - Cj	0	-2	-3	-6	-3	0	0	0
1 2 3	A3 A6 A7	6 0 0	1 1 5	2 0 3	-1 2 6	1 0 0	2 -1 2	1 -1 2	0 1 0	0 0 1
m + 1	Zi - Cj	6	10	-9	0	9	6	0	0
1 2 3	A3 A2 A7	6 3 0	3/2 ? 2	2 0 3	0 1 0	1 0 0	3/2 -1/2 4	? -1/2 5	? ? 3	0 0 1
m + 1	Zi - Cj	21/2	10	0	0	9/2	3/2	9/2	0

2.2 Несимметричные двойственные задачи

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

Исходная задача. Найти матрицу-столбец X = (x₁, x₂, …, x_n), которая удовлетворяет ограничениям AX = A₀, Х 0 и минимизирует линейную функцию Z = СХ.

Двойственная задача. Найти матрицу-строку Y = (y₁, y₂, …, y_m), которая удовлетворяет ограничениям YA С и максимизирует линейную функцию f = YA_0.

В обеих задачах C = (c₁, c₂, …, c_n) - матрица-строка, A_n = (b₁, b₂, …, b_m) -матрица-столбец, А = (a_ij) - матрица коэффициентов системы ограничений.

Для составления несимметричной двойственной задачи используются те же правила, что и для составления симметричной двойственной задачи, но с учетом особенностей:

1. Если задача имеет канонический вид, то ограничения двойственной задачи будут неравенства. Если в целевой функции исходной задачи требуется найти минимум, то знак неравенства - ?, а если требуется найти максимум, то знак неравенства - ?.

2. Переменные у_i для канонической задачи произвольны по знаку.

3 Теоремы двойственности

Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение: min Z = max f.

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

Доказательство. Предположим, что исходная задача обладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис состоит из т первых векторов A₁, A₂, ..., A_m. Тогда последняя симплексная таблица имеет вид:

Таблица 2

i	Базис	С базиса	A0	C1	C2	…	Cm	Cm+1	…	cn
				A1	A2	…	Am	Am+1	…	An
1 2 . . . m	A1 A2 . . . Am	C1 C2 . . . Cm	x1 x2 . . . xm	1 0 . . . 0	0 1 . . . 0	... ... . . . .	0 0 . . . 1	x1, m+1 x2, m+1 . . . xm, m+1	… … . . . …	x1n x2n . . . xmn
m+1	Zi - Cj	Z0	Z1 - C1	Z2 - C2	...	Zm - Cm	Zm+1 - Cm+1	…	Zn - Cn

Пусть D -- матрица, составленная из компонент векторов окончательного базиса A₁, A₂, ..., A_m, тогда таблица 2 состоит из коэффициентов разложения векторов A₁, A₂, ..., A_n исходной системы по векторам базиса, т. е. каждому вектору A_j в этой таблице соответствует такой вектор X_j, что A_j = DX_j (j= 1,2, ,.., n).

Для оптимального плана получаем A₀ = DX*, где X* = (x*₁, x*₂, …, x*_m). Обозначим через матрицу, составленную из коэффициентов разложения векторов А_j (j = 1, 2, ..., n), записанных в таблице 2. Тогда, учитывая соотношения A_j = DX_j (j= 1,2, ,.., n) и A_n = DX*, получаем:

A = D, D^-1A =,

A₀=DX*; D^-1A₀ = X*,

min Z= C*X*,

= C*-C 0,

где С* = (C*₁, C*₂, …, C*_m), С = (C₁, C₂, …, C_m, C_m+1, …, C_n), a = (C*X₁ -C₁; С*Х₂ - С₂, ..., C*X_n - C_n) = (Z₁ - С₁; Z₂ - C₂; ..., Z_n - C_n) - вектор, компоненты которого неположительные, так как они совпадают с Z_j - C_j 0, соответствующими оптимальному плану.

Оптимальный план исходной задачи имеет вид X* = D^-1 А₀, поэтому оптимальный план двойственной задачи ищем в виде Y* = C*D^-1.

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения YA С запишем в виде неравенства YA - С 0, в левую часть которого подставим Y*. Тогда на основании Y* = C*D^-1, A = D, D^-1A = и = C*--C 0 получим Y* А - С = С* D^-1А - С = С* - С 0, откуда находим Y*A С.

Так как Y* удовлетворяет ограничениям YA С, то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f (Y*) = Y*A_n.

Учитывая соотношения:

A₀=DX*; D^-1A₀ = X*,

min Z= C*X*

Y* = C*D^-1,

имеем f (Y*) = Y*A₀ = C*D^-1 A₀ = C*X* = min Z(X).

Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи.

Докажем теперь, что Y* является оптимальным планом. Умножим AX = A₀, Х 0 на любой план Y двойственной задачи, а YA С - на любой план X исходной задачи: YAX=YA₀=f (Y), YAX СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство f (Y) Z (X).

Этим же соотношением связаны и экстремальные значения максимума функции f (Y) min Z (Х). Из последнего неравенства заключаем, что максимальное значение линейной функции достигается только в случае, если max f (Y) = min Z (X), но это значение f (Y) достигает при плане Y*, следовательно, план Y* -- оптимальный план двойственной задачи.

Также можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотношение max f (Y) = min Z (X).

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из f (Y) Z (X) следует, что f (Y) - . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда из f (Y) Z (X) получаем, что Z (X) +. Это выражение также лишено смысла, поэтому исходная задача не имеет решений.

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

Исходная задача. Найти минимальное значение линейной функции Z = x₂ - x₄ - 3x_5, при ограничениях:

x_ij 0 (j = 1, 2, …, 6)

Здесь матрица-строка С = (0;. 1; 0; -1; -3, 0), матрица-столбец

Двойственная задача. Найти максимум линейной функции f = y₁ + 2y₂ +5y₃ при ограничениях:

Решение исходной задачи находим симплексным методом (таблица 3)

Таблица 3

i	Базис	С базиса	A0	0	1	0	-1	-3	0
				A1	A2	A3	A4	A5	A6
1 2 3	A1 A3 A6	0 0 0	1 2 5	1 0 0	2 -4 3	0 1 0	-1 2 0	1 -1 1	0 0 1
m + 1	Zi - Cj	0	0	-1	0	1	3	0
1 2 3	A5 A3 A6	-3 0 0	1 3 4	1 1 -1	2 -2 1	0 1 0	-1 1 1	1 0 0	0 0 1
m + 1	Zi - Cj	-3	-3	-7	0	4	0	0
1 2 3	A5 A4 A6	-3 -1 0	4 3 1	2 1 -2	0 -2 3	1 1 -1	0 1 0	1 0 0	0 0 1
m + 1	Zi - Cj	-15	-7	1	-4	0	0	0
1 2 3	A5 A4 A2	-3 -1 1	4 11/3 1/3	3 -1/3 -2/3	0 0 1	1 1/3 -1/3	0 1 0	1 0 0	0 2/3 1/3
m + 1	Zi - Cj	-46/3	-19/3	0	-11/3	0	0	-1/3

Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Z_min = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y* = C*D^-1, где матрица D^-1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A₅, A₄, A₂, значит:

D = (A₅, A₄, A₂) =

Обратная матрица D^-1 образована из коэффициентов, стоящих в столбцах A₁, A₃, A₆ четвертой итерации

D^-1 =

Из этой же итерации следует С* = (-3; -1; 1). Таким образом:

Y = С*D^-1 = (-3; -1; 1) *

Y* = (-19/3; -11/3; -1/3),

т. е. y_i = С*Х_i

где Х_i -- коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.

Таким образом, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базис, если к ней прибавить соответствующее значение коэффициента линейной функции:

у₁ = - 19/3 + 0 = -19/3; y₂ = -11/3 + 0 = -11/3; у₃ = -1/3+0 = -1/3. При этом плане max f = -46/3.

двойственный задача линейный

4 Реализация двойственности на Visual Basic for Application

При нажатии на кнопку Start (рисунок А.1) появляется форма (рисунок А.2), где в текстовые поля вводятся значения количества переменных и уравнений. Вводимые значения должны целыми числами от 2 до 20. Также на форме при помощи Option Button выбирается направление функции (максимум или минимум). При нажатии кнопки Ok в процедуре Private Sub CommandButton1_Click() происходит проверка введенных значений:

If Not IsNumeric(TextBox1.Text) Or Val(TextBox1.Text) < 2 Or Val(TextBox1.Text) > 20 Or Not IsNumeric(TextBox2.Text) Or Val(TextBox2.Text) < 2 Or Val(TextBox2.Text) > 20 Then

MsgBox ("Значение количества переменных и количества уравнений - целое число не большее 20")

TextBox1.Text = ""

TextBox2.Text = ""

ElseIf OptionButton1.Value = False And OptionButton2.Value = False Then

MsgBox ("Выберите направление функции")

Else

n = Int(TextBox1.Text)

m = Int(TextBox2.Text)

End if

Если значения, введенные на форму, не соответствуют ограничениям (т.е. если введен текст или не выбрано направление), то появляется сообщение об ошибке (рисунок А.3) или сообщение о необходимости выбрать направление функции (рисунок А.4). Если введенные значения соответствуют ограничениям, то начинается ввод коэффициентов целевой функции через окно ввода (рисунок А.5), а потом коэффициентов системы ограничений (рисунок А.6) и свободных членов (рисунок А.7). Если в окно ввода введено неправильное значение появляется сообщение об ошибке (рисунок А.8).

После окончания ввода происходит построение целевой функции двойственной задачи и ее вывод на лист Excel (рисунок А.9):

p = 0

k = 1

For i = 1 To m

p = p + 2

k = k + 2

b = InputBox("Ввод свободных членов" & " " & i & " уравнения")

Cells(m + 7, p).HorizontalAlignment = xlCenter

Cells(m + 7, k).HorizontalAlignment = xlCenter

построение функции двойственной задачи

Cells(m + 7, p) = b

Cells(m + 7, k) = "y" & i

Next i

Далее выполняется построение системы ограничений двойственной задачи:

k = 0

s = 1

For j = 1 To n

k = 0

For i = 1 To m

k = k + 1

Cells(m + 9 + s, k) = Cells(i + 2, j + 3)

Cells(m + 9 + s, k).HorizontalAlignment = xlCenter

Next i

s = s + 1

Next j

прорисовка надписей

For i = 1 To m

Cells(m + 9, i) = "y" & i

Next i

После окончания ввода и построения двойственной задачи необходимо нажать кнопку Podschet для начала решения исходной задачи симплекс методом, которое происходит в прцедуре Private Sub CommandButton2_Click(). Сначала считается ?j для свободных членов и строка коэффициентов:

f = 0

For i = 1 To m

f = f + Cells(i + 2, 1) * Cells(i + 2, 3)

Next i

ActiveSheet.Cells(m + 3, 3).Value = f

s = 0

For j = 1 To n + m

For i = 1 To m

s = s + Cells(i + 2, 1) * Cells(i + 2, j + 3)

Next i

dtj = s - Cells(1, j + 3)

ActiveSheet.Cells(m + 3, j + 3).Value = dtj

s = 0

Next j

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

ReDim ai(i, j)

ReDim bi(i)

For i = 1 To m

For j = 1 To n + m

If i + 2 <> kls Then

pr = Cells(i + 2, j + 3) * al - Cells(kls, j + 3) * Cells(i + 2, kl)

ai(i, j) = pr / al

prb = Cells(i + 2, 3) * al - Cells(kls, 3) * Cells(i + 2, kl)

bi(i) = prb / al

End If

Next j

Next i

For i = 1 To m

For j = 1 To n + m

If i + 2 <> kls Then

Cells(i + 2, j + 3).Value = ai(i, j)

Cells(i + 2, 3).Value = bi(i)

End If

Next j

Next i

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

For j = 1 To n + m

a = Cells(kls, j + 3).Value / al

Cells(kls, j + 3).Value = a

Next j

b = Cells(kls, 3) / al

Cells(kls, 3).Value = b

Далее выполняется подсчет значения целевой функции, если возможно, и вывод при помощи окна сообщения (рисунок А.10) или сообщение об отсутствии решений (рисунок А.11).

Для очистки текстовых полей и листа необходимо нажать кнопку Clear, а для выхода - кнопку Exit.

Если необходимо получить справку, нужно нажать кнопку Help (рисунок А.1), а чтобы вернуться обратно - кнопку Back на листе 2.

Заключение

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

Список использованных источников

Акулич И.Л. Математические методы и компьютерные технологии решения оптимизационных задач / И. Л. Акулич, В. Ф. Стрельчонок - 3 изд., стереотип - Рига: Академия, 2000 - 270 с.

Агальцов В.П. Математические методы в программировании/ Агальцов В.П., И. В. Волдайская - Москва: Форум, 2006 - 224 с. (Профессиональное образование).

Приложение А

Иллюстрации

Рисунок А.1 - Вид рабочего листа

Рисунок А.2 - Вид формы

Рисунок А.3 - Ошибка при неправильном вводе количества переменных или количества уравнений

Рисунок А.4 - Сообщение об ошибке при отсутствии направления

Рисунок А.5 - Ввод коэффициентов функции

Рисунок А.6 - Ввод коэффициентов системы



Рисунок А.7 - Ввод свободных членов

Рисунок А.8 - Сообщение об ошибке при неправильном вводе в InputBox

Рисунок А.9 - Двойственная задача

Рисунок А.10 - Вывод ответа

Рисунок А.11- Сообщение об отсутствии решений

Приложение Б

Программный код

Option Explicit

Dim n As Integer 'количество переменных

Dim m As Integer 'количество уравнений

Dim i As Integer 'циклическая переменная

Dim j As Integer 'циклическая переменная

Dim al As Double 'ключевой элемент

Dim b As String 'свободные члены, преобразуется в Double

Dim a As String 'кэффициенты огр, преобразуется в Double

Dim f As Double 'значение целевой функции

Dim c As Double

Dim o() As Integer 'массив для поиска ключевого элемента

Dim s As Double

Dim p As Integer

Dim kl As Integer 'ключевой столбец

Dim kls As Integer 'ключева строка

Dim k As Integer

Dim dtj As Double

Dim ai() As Double 'новые элементы таблицы

Dim bi() As Double 'новые свободные члены

Dim pr As Double

Dim prb As Double

Dim max As Double

Dim min As Double

Dim h As Variant

Dim r() As Double 'массив для поиска ключевого элемента

Dim x As String 'коэффициенты функции, преобразуется в Double

Private Sub CommandButton1_Click()

'перехват ошибок

If Not IsNumeric(TextBox1.Text) Or Val(TextBox1.Text) < 2 Or Val(TextBox1.Text) > 20 Or Not IsNumeric(TextBox2.Text) Or Val(TextBox2.Text) < 2 Or Val(TextBox2.Text) > 20 Then

MsgBox ("Значение количества переменных и количества уравнений - целое число не большее 20")

TextBox1.Text = ""

TextBox2.Text = ""

ElseIf OptionButton1.Value = False And OptionButton2.Value = False Then

MsgBox ("Выберите направление функции")

Else

n = Int(TextBox1.Text)

m = Int(TextBox2.Text)

'заполнение шапки симплексной таблицы

With ActiveSheet

Cells(2, 1).Value = "c(i)"

Cells(2, 2).Value = "БП"

Cells(2, 3).Value = "b"

Cells(2, 1).Font.FontStyle = "полужирный"

Cells(2, 2).Font.FontStyle = "полужирный"

Cells(2, 3).Font.FontStyle = "полужирный"

End With

создание надписи "двойственная задача"

For j = 1 To 3

Cells(m + 5, j).Select

With Selection.Font

Name = "Times New Roman"

FontStyle = "полужирный"

Size = 12

End With

With Selection

VerticalAlignment = xlBottom

End With

Cells(m + 5, j).Select

Cells(m + 5, 3) = "Двойственная задача"

Next j

ActiveSheet.Cells(m + 7, 1).Value = "F (y) ="

With Cells(m + 7, 1).Font

Name = "Times New Roman"

FontStyle = "полужирный"

Size = 12

End With

End If

ввод коэффициентов целевой функции и заполнение таблицы

For j = 1 To n

1 x = InputBox("Ввод коэффициентов целевой функции")

перехват ошибок

If Not IsNumeric(x) Or x = "" Then

h = MsgBox("Введите другое значение", vbOKCancel)

If h = vbOK Then

GoTo 1

Else

End

End If

End If

If CDbl(x) < -1000 Or CDbl(x) > 1000 Then

h = MsgBox("Введите другое значение", vbOKCancel)

If h = vbOK Then

oTo 1

Else

End

End If

End If

ActiveSheet.Cells(1, j + 3).Value = CDbl(x)

ActiveSheet.Cells(2, j + 3).Value = "x(" & j & ")"

Cells(2, j + 3).Font.FontStyle = "полужирный"

Next j

ввод кэффициентов системы ограничений

For i = 1 To m

For j = 1 To n

перехват ошибок

2 a = InputBox("Ввод коэффициентов " & " " & i & " системы ограничений")

If Not IsNumeric(a) Or a = "" Then

h = MsgBox("Введите другое значение", vbOKCancel)

If h = vbOK Then

GoTo 2

Else

End

End If

End If

If CDbl(a) < -1000 Or CDbl(a) > 1000 Then

h = MsgBox("Введите другое значение", vbOKCancel)

If h = vbOK Then

GoTo 2

Else

End

End If

End If

Cells(i + 2, j + 3).Value = CDbl(a)

Next j

Next i

For i = 1 To m

For j = n + 1 To n + m

If j <> n + i Then

a = 0

ElseIf j = n + i Then

a = 1

End If

Cells(i + 2, j + 3).Value = a

ActiveSheet.Cells(i + 2, 1).Value = 0

ActiveSheet.Cells(1, j + 3).Value = 0

ActiveSheet.Cells(2, j + 3).Value = "x(" & j & ")"

Cells(2, j + 3).Font.FontStyle = "полужирный"

ActiveSheet.Cells(i + 2, 2).Value = "x(" & n + i & ")"

Next j

Next i

ввод свободных членов

p = 0

k = 1

For i = 1 To m

p = p + 2

k = k + 2

3 b = InputBox("Ввод свободных членов" & " " & i & " уравнения")

перехват ошибок

If Not IsNumeric(b) Or b = "" Then

h = MsgBox("Введите другое значение", vbOKCancel)

If h = vbOK Then

GoTo 3

Else

End

End If

End If

If CDbl(b) < -1000 Or CDbl(b) > 1000 Then

h = MsgBox("Введите другое значение", vbOKCancel)

If h = vbOK Then

GoTo 3

Else

End

End If

End If

ActiveSheet.Cells(i + 2, 3).Value = CDbl(b)

With Cells(m + 7, p).Font

Name = "Times New Roman"

FontStyle = "полужирный"

Size = 12

ColorIndex = 5

End With

With Cells(m + 7, k).Font

Name = "Times New Roman"

FontStyle = "обычный"

Size = 12

End With

равнивание по центру

Cells(m + 7, p).HorizontalAlignment = xlCenter

Cells(m + 7, k).HorizontalAlignment = xlCenter

построение функции двойственной задачи

Cells(m + 7, p) = b

Cells(m + 7, k) = "y" & i

Next i

построение системы ограничений

k = 0

s = 1

For j = 1 To n

k = 0

For i = 1 To m

k = k + 1

Cells(m + 9 + s, k) = Cells(i + 2, j + 3)

Cells(m + 9 + s, k).HorizontalAlignment = xlCenter

With Cells(m + 9 + s, k).Font

Name = "Times New Roman"

FontStyle = "полужирный"

Size = 12

ColorIndex = 5

End With

Next i

s = s + 1

Next j

прорисовка надписей

For i = 1 To m

Cells(m + 9, i) = "y" & i

Next i

вывод свободных членов двойственной задачи

For j = 1 To n

Cells(m + 9 + j, m + 2) = Cells(1, j + 3)

Cells(m + 9 + j, m + 1) = "c" & j

Cells(m + 9 + j, m + 1).HorizontalAlignment = xlCenter

Cells(m + 9 + j, m + 2).HorizontalAlignment = xlCenter

With Cells(m + 9 + j, m + 2).Font

Name = "Times New Roman"

FontStyle = "полужирный"

Size = 12

ColorIndex = 5

End With

Next j

End Sub

Private Sub CommandButton2_Click() 'процедура очистки

TextBox1.Text = ""

TextBox2.Text = ""

ActiveSheet.Cells.Clear

OptionButton1.Value = False

OptionButton2.Value = False

End Sub

Private Sub CommandButton3_Click() 'выход

h = MsgBox("Exit", vbQuestion + vbOKCancel)

If h = vbOK Then

UserForm1.Hide

End If

End Sub

Private Sub CommandButton4_Click() 'подсчет

вывод надписи

ActiveSheet.Cells(m + 3, 2).Value = "dtj"

Cells(m + 3, 2).Font.FontStyle = "полужирный"

подсчет значения функции

4 f = 0

For i = 1 To m

f = f + Cells(i + 2, 1) * Cells(i + 2, 3)

Next i

ActiveSheet.Cells(m + 3, 3).Value = f

нахождение индексной строки

s = 0

For j = 1 To n + m

For i = 1 To m

s = s + Cells(i + 2, 1) * Cells(i + 2, j + 3)

Next i

dtj = s - Cells(1, j + 3)

ActiveSheet.Cells(m + 3, j + 3).Value = dtj

s = 0

Next j

поиск отрицательных элементов индексной строки

k = 0

If OptionButton1.Value = True Then

For j = 1 To n + m

If Cells(m + 3, j + 3) < 0 Then

k = k + 1

End If

Next j

вывод ответа, если количество равно нулю

If k = 0 Then

h = MsgBox("F(x)=" & Cells(m + 3, 3))

MsgBox ("Исходная задача имеет решение, следовательно двойственная задача тоже имеет решение")

MsgBox ("Решение исходной задачи на максимум являктся решением двойственной задачи на минимум")

End

поиск ключевого столбца

ElseIf k <> 0 Then

min = Cells(m + 3, 4): kl = 4

For j = 1 To n + m

If Cells(m + 3, j + 3) <= min And Cells(m + 3, j + 3) < 0 Then

min = Cells(m + 3, j + 3): kl = j + 3

End If

Next j

End If

поиск положительных элементов индексной строки

ElseIf OptionButton2.Value = True Then

For j = 1 To n + m

If Cells(m + 3, j + 3) > 0 Then

k = k + 1

End If

Next j

max = Cells(m + 3, 4): kl = 4

вывод ответа, если количество равно нулю

If k = 0 Then

h = MsgBox("F(x)=" & Cells(m + 3, 3))

MsgBox ("Исходная задача имеет решение, следовательно двойственная задача тоже имеет решение")

MsgBox ("Решение исходной задачи на минимум являктся решением двойственной задачи на максимум")

End

поиск ключевого столбца

ElseIf k <> 0 Then

For j = 1 To n + m

If Cells(m + 3, j + 3) >= max And Cells(m + 3, j + 3) > 0 Then

max = Cells(m + 3, j + 3): kl = j + 3

End If

Next j

End If

End If

поиск ключевой строки

k = 0

ReDim r(i)

ReDim o(i)

For i = 1 To m

If Cells(i + 2, kl) > 0 Then

r(i) = Cells(i + 2, 3) / Cells(i + 2, kl)

o(i) = i + 2

Else

r(i) = 0: o(i) = 0: k = k + 1

End If

Next i

If k = m Then

MsgBox ("Решений нет")

MsgBox ("Двойственная задача тоже не имеет решения")

End

ElseIf m - k = 1 Then

r i = 1 To m

If r(i) <> 0 Then

min = r(i): kls = o(i)

End If

Next i

Else

min = r(1): kls = o(1)

If r(1) = 0 Then

For i = 1 To m

If r(i) <> 0 Then

min = r(i)

End If

Next i

End If

определение ключевого элемента

For i = 1 To m

If r(i) < min And r(i) <> 0 Then

min = r(i): kls = o(i)

End If

Next i

End If

al = Cells(kls, kl).Value

правило прямоугольника

ReDim ai(i, j)

ReDim bi(i)

For i = 1 To m

For j = 1 To n + m

If i + 2 <> kls Then

pr = Cells(i + 2, j + 3) * al - Cells(kls, j + 3) * Cells(i + 2, kl)

ai(i, j) = pr / al

prb = Cells(i + 2, 3) * al - Cells(kls, 3) * Cells(i + 2, kl)

bi(i) = prb / al

End If

Next j

Next i

For i = 1 To m

r j = 1 To n + m

If i + 2 <> kls Then

Cells(i + 2, j + 3).Value = ai(i, j)

Cells(i + 2, 3).Value = bi(i)

End If

Next j

Next i

элементы ключевой строки

For j = 1 To n + m

a = Cells(kls, j + 3).Value / al

Cells(kls, j + 3).Value = a

Next j

b = Cells(kls, 3) / al

Cells(kls, 3).Value = b

For i = 1 To n + m

If i + 2 = kls Then

Cells(i + 2, 1).Value = Cells(1, kl).Value

Cells(i + 2, 2).Value = Cells(2, kl).Value

End If

Next i

GoTo 4

End Sub

Private Sub UserForm_Initialize()

CommandButton1.Default = True

End Sub

Размещено на Allbest.ru