Решение задач симплексным методом (стр. 2 из 4)

1. Определение переменных, для которых будет составляться математическая модель.

Так как требуется определить план производства изделий А и В, то переменными модели будут:

x1 - объём производства изделия А, в единицах;

x2 - объём производства изделия В, в единицах.

2. Формирование целевой функции.

Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x1 + 3x2 ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции : определить допустимые значения переменных x1 и x2 , максимизирующих целевую функцию F = 2x1 + 3x2 .

3. Формирование системы ограничений.

При определении плана производства продукции должны быть учтены ограничения на время, которое администрация предприятия сможет предоставить на изготовления всех изделий. Это приводит к следующим трём ограничениям :

x1 + 5x2 Ј 10 ; 3x1 + 2x2 Ј 12 ; 2x1 + 4x2 Ј 10 .

Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности :

x1 і 0 ; x2 і 0 .

Таким образом, математическая модель задачи представлена в виде : определить план x1 , x2 , обеспечивающий максимальное значение функции :

max F = max ( 2x1 + 3x2 )

при наличии ограничений :

x1 + 5x2 Ј 10 ;

3x1 + 2x2 Ј 12 ;

2x1 + 4x2 Ј 10 .

x1 і 0 ; x2 і 0 .

3.2 Решение задачи вручную

Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.

1. Приведение задачи к форме :

x1 + 5x2 Ј 10 ;

3x1 + 2x2 Ј 12 ;

2x1 + 4x2 Ј 10 .

x1 і 0 ; x2 і 0 .

2. Канонизируем систему ограничений :

x1 + 5x2 + x3 = 10 ;

3x1 + 2x2 + x4 = 12 ;

2x1 + 4x2 + x5 = 10 .

x1 і 0 ; x2 і 0 .

A1 A2 A3 A4 A5 A0

3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам :

d0 =

- текущее значение целевой функции

C	2	3	0	0	0
Б	Cб	A0	A1	A2	A3	A4	A5
A3	0	10	1	5	1	0	0
A4	0	12	3	2	0	1	0
A5	0	10	2	4	0	0	1
d	0	-2	-3	0	0	0

di =

- расчёт симплекс-разностей, где j = 1..6 .

Так как при решении задачи на max не все симплекс-разности положительные, то оптимальное решение можно улучшить.

4. Определяем направляющий столбец j*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А2

5. Вектор i*, который нужно вывести из базиса, определяется по отношению :

min

при аi j > 0

В данном случае сначала это А3 .

5. Заполняется новая симплекс-таблица по исключеню Жордана - Гаусса :

а). направляющую строку i* делим на направляющий элемент :

a i j = a i j / a i j , где j = 1..6

б). преобразование всей оставшейся части матрицы :

a ij = aij - a i j Ч aij , где i № i* , j № j*

C	2	3	0	0	0
Б	Cб	A0	A1	A2	A3	A4	A5
A2	3	2	1/5	1	1/5	0	0
A4	0	8	13/5	0	-2/5	1	0
A5	0	2	6/5	0	-4/5	0	1
d	6	-7/5	0	3/5	0	0

В результате преобразований получаем новую симплекс-таблицу :

Повторяя пункты 3 - 5, получим следующие таблицы :

C			2			3			0			0			0
Б	Cб			A0			A1			A2			A3			A4			A5
A2	3			5/3			0			1			1/3			0			-1/6
A4	0			11/3			0			0			4/3			1			-13/6
A1	2			5/3			1			0			-2/3			0			5/6
d			8 1/3			0			0			-1/3			0			7/6

C	2	3	0	0	0
Б	Cб	A0	A1	A2	A3	A4	A5
A2	3	3/4	0	1	0	-1/4	3/8
A3	0	11/4	0	0	1	3/4	-13/8
A1	2	7/2	1	0	0	1/2	-1/4
d	9 1/4	0	0	0	1/4	5/8

Так как все симплекс-разности положительны, то оптимальное решение найдено :

X = ( 7/2 , 3/4 , 11/4 , 0 , 0 ) ( единиц )

max F = 9 1/4 ( рублей )

4.НАЗНАЧЕНИЕ ПРОГРАММЫ

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

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

Задание условий

Все условия задаются в колонке “A” первого листа(программа результат помещает в лист 2)

В третьей строке(”A3″) необходимо записать целеыую функцию на минимум или максимум(min или max после =) например:

3Ч1+2Ч2+4Ч3+2Ч4=min

В 5 строке необходимо записать количество знаков в дробной части чисел(или ничего то есть пусто или пробел(ы) )

начиная с 9 строки записываются ограничения по одной строке на каждое ограничениe. Hапример:

6Ч2+6Ч3+4Ч4=60
2Ч1+4Ч2+8Ч3+8Ч4<=80
4Ч1+4Ч2+12Ч4>=20
2Ч1+6Ч2+2Ч3+8Ч4=30
(можно выделить и занести все ограничения нашего примера в буфер и вставить в ячейку “9А”, программа автоматически разместит их в строчки, что располагаются ниже.)Содержимое последней строки ограничений(В нашем примере A13) должно быть пусто или пробел(ы) Переменные Xi по умолчанию считается не отрицательными.

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

Получение результата

Результат работы располагается на втором листе книги.

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

Для получения новой итерации следует перейти на первый лист(он называется “Initial data” и нажать кнопку для получения следующей итерации. Если промежуточные результаты не нужны, то следует последовательно нажимать на кнопку получения новой итерации, не переходя на второй лист и перейти на него только для просмотра окончательного результата.

6. ТЕКСТ ИСХОДНОГО МОДУЛЯ

Dim Ftarget As String ’целевая функция target function

Dim MaxX As Integer ‘максимальный индех Х в целевой функции

Dim MaxLi As Boolean ‘true-max; False-min

Dim AmRest As Integer ‘ Количество строк ограничений (Amount of the restrictions)

Private Type Tmy

IndX As Integer

KoefX As Double

End Type

‘Номер очередного обрабатываемого символа в строке

Dim Icurrent As Integer

Dim BgRight As Integer ’Номер байта начала правой части ограничения, иначе 0;

‘The Number of the byte begin right part of restriction, otherwise 0;

Dim Isx As String

Dim Rez() As Tmy

Dim NumIter As Integer ‘Номер итерации. Если равен нулю, канонический вид симплекс таблицы

‘Number to iterations. If is a zero, canonical type simplex tables

Dim MiCiXiAi() As Double ‘Два первых столбца этого массива заменяют первый столбец симплексной таблицы.

‘Первый столбец, это множитель “М”, вводимый для искуственных переменных для ограничений “>” или “=”

‘Второй столбец, это коэфициенты переменных в целевой функции

‘(номера этих переменных указаны в третьем столбце массива MiCiXiAi)

‘Четвертый столбец массива MiCiXiAi(”Alfa”), это последний столбец симплексной таблицы равный X0/Хi

‘Two first columns of this array change the first column of the simplex table.

‘First column, this multiplier “M”, introduced for illusory variables for restrictions “>” or “=”

‘Second column, this values from target function

‘Second column is values variables in target function

‘(number these variables is specified in one third column array MiCiXiAi)

‘Fourth column of the array MiCiXiAi(”Alfa”), this last column of the simplex table equal X0/Hi

Dim Tsimp() As Double ‘ the simplex table

Dim CleaDoub() As Double

Dim CleaTMY() As Tmy

Dim Icol As Integer ’ Ключевой столбец.The Key column.

Dim Irow As Integer ’ Ключевая строка. The Key line.

Dim AllPlans As String ’Все планы в текущей задаче. All plans in the current task.

Dim DirectCycle As Boolean ‘True-Прямой цикл; True-Direct cycle;

Private Sub ProcString(Strin As String, Ans() As Tmy, CalcMaxX As Boolean)

‘Выделение из “Strin” числовых данных. Одновременно вычисляем махимальный индех переменно Х

‘Separation from “Strin” numeric data. Simultaneously we calculate the Largest number variable X.

Dim Awork() As Tmy

Dim VaLi As Double

Dim i As Integer ’ index in awork

Strin = Replace(Strin, ” “, “”) ‘ Убрали лишьние пробелы в целевой функции

Strin = Trim(Strin)

Strin = Replace(Strin, “X”, “x”) ‘Заменим все х на маленькое английское

Strin = Replace(Strin, “Х”, “x”) ‘Русское большое на маленькое английское x

Strin = Replace(Strin, “х”, “x”) ‘Русское маленькое на маленькое английское x

Strin = Replace(Strin, “>=”, “>”) ‘

Strin = Replace(Strin, “<=”, “<”) ‘

BgRight = 0

i = 0

Icurrent = 1

Do While BgRight = 0

i = i + 1

ReDim Preserve Awork(i)

VaLi = ExtractDbl(Strin, Icurrent)

Awork(i).KoefX = VaLi

VaLi = ExtractDbl(Strin, Icurrent)

Awork(i).IndX = CInt(VaLi)

If CalcMaxX Then If MaxX < CInt(VaLi) Then MaxX = CInt(VaLi)

Loop

Ans = Awork

End Sub

Private Sub CommandButton1_Click()

Dim i As Integer

Dim j As Integer

Dim K As Integer

Dim Acell As String

Dim St1 As String * 1

Dim Vdbl As Double

NumIter = 0

MaxX = 0

AllPlans = “”

DirectCycle = True

CommandButton1.ForeColor = &H40C0& ’Оранжевый

CommandButton1.Caption = “Привести к каноническому виду”