Искусственное начальное решение. Метод больших штрафов. Метод больших штрафов


-.

, . , .

-, . F(X) = 2x1+x2+3x3 - (. M-). x1+2x2+x3≤1000 3x1+5x2+2x3≤1500 x1≥100 x2≥100 x3≥200 ( ). 1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 1000 3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = 1500 1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 = 100 0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 = 100 0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 = 200 x. 1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1000 3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1500 1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 100 0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 0x9 + 1x10 + 0x11 = 100 0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 + 0x9 + 0x10 + 1x11 = 200 : F(X) = 2x1+x2+3x3 - Mx9 - Mx10 - Mx11 => max , , , , . , . , , . : x9 = 100-x1+x6x10 = 100-x2+x7x11 = 200-x3+x8: F(X) = 2x1 + x2 + 3x3 - M(100-x1+x6) - M(100-x2+x7) - M(200-x3+x8) => max F(X) = (2+1M)x1+(1+1M)x2+(3+1M)x3+(-1M)x6+(-1M)x7+(-1M)x8+(-400M) => max A = a(ij) :

1 2 1 1 0 0 0 0 0 0 0
3 5 2 0 1 0 0 0 0 0 0
1 0 0 0 0 -1 0 0 1 0 0
0 1 0 0 0 0 -1 0 0 1 0
0 0 1 0 0 0 0 -1 0 0 1
, . : x4, x5, x9, x10, x11, , 0, : X1 = (0,0,0,1000,1500,0,0,0,100,100,200)
x1x2x3x4x5x6x7x8x9x10 x11
0 x4 100012110000000
x5150035201000000
x910010000-100100
x10100 0 1 0 0 0 0 -1 0 0 1 0
x11 200 0 0 1 0 0 0 0 -1 0 0 1
F(X0) -400M -2-1M -1-1M -3-1M 0 0 1M 1M 1M 0 0 0

.

x1x2x3x4x5x6x7x8x9x10x11
0x4100012110000000
 x5150035201000000
 x910010000-100100
 x10100010000-10010
 x112000010000-1001
F(X0)0-2-1-300000000
M -400-1-1-100111000
-.
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
1 x4 1000 1 2 1 1 0 0 0 0 0 0 0 1000
x5 1500 3 5 2 0 1 0 0 0 0 0 0 750
x9 100 1 0 0 0 0 -1 0 0 1 0 0 0
x10 100 0 1 0 0 0 0 -1 0 0 1 0 0
x11 200 0 0 1 0 0 0 0 -1 0 0 1 200
F(X1) -400M -2-1M -1-1M -3-1M 0 0 1M 1M 1M 0 0 0 0
0. , , x3, . Di : , 5- 1 . x 1 x3 , x3 1, x11 0 =1 1 1. x3 1 . , 1 x3 x3 . 1, , . , . = - (*)/ - , - (1), - , . :
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
2 x4 800 1 2 0 1 0 0 0 1 0 0 -1 800
x5 1100 3 5 0 0 1 0 0 2 0 0 -2 366.67
x9 100 1 0 0 0 0 -1 0 0 1 0 0 100
x10 100 0 1 0 0 0 0 -1 0 0 1 0 0
x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
F(X2) 600-200M -2-1M -1-1M 0 0 0 1M 1M -3 0 0 3+1M 0
1. , , x1, . Di : , 3- 1 . x 2 x1 , x1 2, x9 1 =1 2 1. x1 2 . , 2 x1 x1 . 2, , . :
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
3 x4 700 0 2 0 1 0 1 0 1 -1 0 -1 350
x5 800 0 5 0 0 1 3 0 2 -3 0 -2 160
x1 100 1 0 0 0 0 -1 0 0 1 0 0 0
x10 100 0 1 0 0 0 0 -1 0 0 1 0 100
x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
F(X3) 800-100M 0 -1-1M 0 0 0 -2 1M -3 2+1M 0 3+1M 0
2. , , x2, . Di : , 4- 1 . x 3 x2 , x2 3, x10 2 =1 3 1. x2 3 . , 3 x2 x2 . 3, , .
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
4 x4 500 0 0 0 1 0 1 2 1 -1 -2 -1 500
x5 300 0 0 0 0 1 3 5 2 -3 -5 -2 150
x1 100 1 0 0 0 0 -1 0 0 1 0 0 0
x2 100 0 1 0 0 0 0 -1 0 0 1 0 0
x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
F(X4) 900 0 0 0 0 0 -2 -1 -3 2+1M 1+1M 3+1M 0
3. , , x8, . Di : , 2- 2 . x 4 x8 , x8 4, x5 3 =2 4 1. x8 4 . , 4 x8 x8 . 4, , . : : - -:
x1x2x3x4x5x6x7x8x9x10x11
5x43500001-0.5-0.5-0.500.50.50
x815000000.51.52.51-1.5-2.5-1
x110010000-100100
x2100010000-10010
x335000100.51.52.50-1.5-2.50
F(X5)135000001.52.56.50-2.5+1M-6.5+1M1M
: x1 = 100, x2 = 100, x3 = 350 F(X) = 2*100 + 1*100 + 3*350 = 1350

math.semestr.ru

8. Метод больших штрафов

На этом шаге мы рассмотрим М-метод решения задач линейного программирования. 

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

    Переменная Ri, с помощью достаточно большого положительного числа М, штрафуется путем ввода в целевую функцию выражения –MRi в случае максимизации целевой функции и выражения +MRi — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Ri. Далее следует применить симплекс-метод.

    При использовании М-метода следует обратить внимание на следующие два обстоятельства.

  1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения.

  2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.

    На следующем шаге рассмотрим решение задачи линейного программирования М-методом.

9. Тз линейного программирования. Постановка задачи

Транспортная задача линейного программирования формулирует­ся следующим образом.

Имеется m пунктов отправления (ПО): A1, A2, …, Am, в ко­торых сосредоточены запасы какого-то однородного груза в количест­ве соответственно a1, a2, …, am единиц. Кроме того, имеется пунктов назначения (ПН): B1, B2, …, Bn подавших заявки соот­ветственно на b1, b2, …, bn, единиц груза.

Предполагается, что сумма всех заявок равна сумме всех запа­сов:

ai =bj (3.1)

Известна стоимость Сij перевозки единицы груза от каждого пункта отправления Ai до каждого пункта назначения Вj. Таблица (матрица) стоимостей перевозки Сij задана:

Требуется составить такой план перевозок, при котором все заявки были бы выполнены, и при этом общая стоимость всех пере­возок была минимальна.

При такой постановке задачи показателем эффективности плана перевозок является стоимость; поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.

Дадим этой задаче математическую формулировку. Обозначим xij- количество груза, отправляемого из i-го пункта отправле­ния в j-й пункт назначения Bj .

Неотрицательные переменные, число которых равно m*n, должны удовлетворять следующим ус­ловиям.

I. Суммарное количество груза, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это дает т условий-равенств:

x1j=a1,

x2j=a2, (3.2)

………….

xmj=am,

2. Суммарное количество груза, доставляемое в каждый пункт назначения изо всех пунктов отправления, должно быть равно заяв­ке, поданной данным пунктом. Это дает n условий-равенств:

xi1=b1,

xi2=b2, (3.3)

…………

xin=bn,

Условия (3.2), (3.3) называются "балансовыми условиями".

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

L= Сij xij = min (3.4)

Функции (3.4), являющаяся целевой функцией линейна, ограни­чения-равенства (3.2), (3.3) также линейны. Перед нами – типичная задача линейного программирования с ограничениями - равенствами, называемая основной задачей линейного программирования (ОЗЛП).

Данная задача имеет некоторые особенности, позволяющие ре­ шить ее вручную простыми табличными методами. Во-первых, все коэффициенты при переменных в уравнениях (3.2), (3.3) равны едини­це. Во-вторых, не все m+n уравнений задачи являются независимыми. Действительно, складывая между собой все уравнения (3.2) и все уравнения (3.3), мы должны получить одно и то же в силу условия (3.1). Таким образом, условия (3.2), (3.3) связаны одной линейной зависимостью и фактически из этих уравнений только m , а не n являются линейно независимыми. Значит, ранг r системы уравнений (3.2), (3.3) равен

r=m+n-1

а, следовательно, можно разрешить эти уравнения относительно m+n-1 базисных переменных, выразив их через остальные, свобод­ные, количество которых равно

K=mn-(m+n-1) = (m-1) (n-1)

Как известно, в задаче линейного программирования оптималь­ное решение достигается в одной из вершин области допустимых ре­шений (ОДР), где, по крайней мере, K переменных обращаются в нуль. Значит, в нашем случае для оптимального плана перевозок, по край­ней мере (m-1)(n-1) значений xij должны быть равны нулю.

Условимся о терминологии. Значения xij количества единиц груза, направляемых из пункта Ai в пункт Bj, будем называть перевозками.

Любую совокупность значений xij (i=1,m; j=1,k) будем на­зывать планом перевозок или просто планом.

План xij будем называть допустимым, если он удовлетворяет условиям (3.2), (3.3): все заявки удовлетворены, все запасы исчерпаны.

Допустимый план будем называть опорным, если в нем отличны от нуля не более r=m+n-1 базисных перевозок xij, а остальные перевозки равны нулю.

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

Перейдем к изложению табличных методов решения транспортной задачи (ТЗ), которые сводятся к более простым операциям с так на­зываемой транспортной таблицей, где в определенном порядке записаны все исходные условия ТЗ.

Образец транспортной таблицы дан в табл. 3.1, где стоимости перевозок единицы груза из ПО Ai в ПН Bj помещаются в правом верхнем углу каждой клетки таблицы, о тем, чтобы в самой клетке при составлении плана помещать перевозки xij. Таблица 3.1

ПОПН

B1

B2

Bn

Запасы

A1

C11

C12

C1n

a1

A2

C21

C22

C2n

a2

Am

Cm1

Cm2

Cmn

a

заявки

b1

b2

bn

ai bj

В правом столбце помещены запасы товара в каждом ПО, в ниж­ней строке - заявки, поданные каждым ПН. В правой нижней клетке таблицы записывается сумма запасов, равная сумме заявок.

Как показано выше, в каждом опорном плане, включая оптималь­ный, будут отличны от нуля не более чем m+n-1 перевозок. Клетки таблицы, в которых записываются эти отличные от нуля пере­возки, условимся называть базисными, а остальные (пус­тые) - свободными.

Таким образом, решение ТЗ свелось к следующему. Найти такие значения положительных перевозок, которые, будучи проставлены в базисных клетках транспортной таблицы, удовлетворяли бы следую­щим условиям:

- сумма перевозок в каждой отроке таблицы должна быть равна запасу данного ПО;

- сумма перевозок в каждом столбце должна быть равна заявке данного ПН;

- общая стоимость перевозок - минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной табл. 3.1. При описании этих преобразований будем пользоваться нумерацией клеток таблицы, подобной нумерации клеток шахматной доски. Клеткой AiBj или, короче, клеткой (i, j) будем называть клетку, стоящую в i-й строке и j-м столбце транспортной таблицы.

Решение транспортной задачи, как и воякой задачи линейного программирования, начинается о нахождения опорного решения (опор­ного плана). Существуют различные способы построения опорного плана, из которых мы остановимся на простейшем, так называемом "способе северо-западного угла". Пояснить его проще всего будет на конкретном примере.

Частные случаи транспортной задачи

В рассмотренных выше случаях число заявок равнялось числу запасов. Чаще всего бывает не так.

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

2) Число заявок превышает число запасов. В этом случае вво­дится фиктивный пункт производства с нулевыми стоимостями перевоз­ки. Задача решается также обычно, только некоторые пункты потребления не дополучат требуемое, но стоимость всей операции все равно получится минимальной.

studfiles.net

Искусственное начальное решение. Метод больших штрафов.

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

Начальная форма задачи: Стандартная форма задачи:

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

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

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

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

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

Ба-

зис

сz

bi

θ

Замечания

Результи-

рующая

строка

zопт

Результи-

рующая

строка

zопт

Результи-

рующая

строка

zопт

Результи-

рующая

строка

zопт

studfiles.net

2. метод больших штрафов (М –метод)

2 . 5. МЕТОД БОЛЬШИХ ШТРАФОВ (М –метод)

Если в исходной задаче ЛП хотя бы одно ограничение имеет знак = или > , то сразу получить начальное допустимое решение неудается. Действительно , пусть требуется найти такие X1 и Х2 , которые обеспечивают max L = 2X1 + X2при ограничениях

Х1 + 2Х2 = 6 ;

Х1 – Х2 > 2 ;

Х1

Х1 , Х2. > 0 .

В стандартной форме эта задача имеет вид :

max L = 2Х1 + Х2 ;

Х1 + 2Х2 = 6 ;

Х1 – Х2 – Х3 = 2 ;

Х1 + Х4 = 5;

Х1 , Х2 , Х3 , Х4 > 0 .

Имеем три уравнения (m = 3) и четыре неизвестных n = 4. Это означает , что каждому базисному решению соответствует одна

( n – m = 1) небазисная ( равная нулю ) переменная . Приравняем , например , Х1 нулю , получаем Х4 = 5 ; Х2 = 3 ; Х3 = -5 , но это решение не является допустимым ( Х3 не является неотрицательной ).

Для простого получения начального допустимого решения разработан метод больших штрафов или М – метод. Суть его в следующем. В уравнения, которые в исходном виде были записаны со знаками >- и = вводят искусственные неотрицательные переменные R і.

Для рассматриваемого примера имеем:

min L = 3 Х 1 + Х 2 + MR 1 ;

5 Х 1 + 4 Х 2 –Х 3 + R 1 =25 ;

Х 1 + Х 4 = 3 ;

Х 1, Х 2, Х 3, Х 4, R 1 > 0 .

За использование этих переменных в составе целевой функции вводят штраф, используя большой положительный коэффициент М. На конечной стадии оптимизации переменные R i должны принять нулевое значение, при этом не будет их влияния на целевую функцию. Очевидно, что в задаче максимизации коэффициент М вводится в целевую функцию со знаком минус, а в задаче минимизации со знаком плюс. Это обусловит недопустимость положительных значений искусственных переменных в оптимальном решении.

После введения искусственных переменных легко получается начальное допустимое решение путём приравнивания к нулю n-m переменных . В рассматриваемом примере n – m = 5 – 2 = 3. Приравнивая нулю Х 1, Х 2 и Х 3 получаем R 1 = 25 и Х 4 = 3 .

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

В рассматриваемой примере

R 1 = 25 - 5 Х 1 – 4 Х 2 + Х 3 .

Тогда

L = 3 Х 1 + Х 2 + MR 1 = 3 Х 1 + Х 2 + М ( 25 – 5 Х 1 – 4 Х 2 +

Х 3 ) = ( 3 – 5 М ) Х 1 + ( 1- 4 М ) Х 2 +МХ 3 +25М.

Симплекс – таблица, соответсвующая начальному допустимому решению , имеет вид

БП Х1 Х2

Х3

Х4 R1 Решение
R1 5 4 -1 0 1 25
Х4 1 0 0 1 0 3 Ведущая строка

L

-3+5М -1+4М 0 0 25М

Ведущий столбец

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

БП Х1 Х2 Х3 Х4 R1 Решение
R1
0 4 -1 -5 1 10 Ведущая строка
Х1 1 0 0 1 0 3
L 0 -1+4М 3-5М 0 9+10М
Х2 0 1 -1/4 -5/4 1/4 2,5
Х1 1 0 0 1 0 3
L 0 0 -1/4 7/4 ¼-М 11,5

Оптимальное решение следующее : Х1 = 3; Х2 = 2,5 ;

min L = 11,5.

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

zavantag.com

, ( ≥ ). , . ( - ), , , 0, , "" , . :
  1. - .
  2. .
. ( ). Word Excel. xi ≥ 0 . xi , , .

. , . F(X) = 3x3 - 2x4 - x5 : 2x1 + x2 + x3 + x4 + 3x5=5 3x1 + 2x3 - x4 + 6x5=7 x1 - x3 + 2x4 + x5=2

-. x. 2x1 + 1x2 + 1x3 + 1x4 + 3x5 + 1x6+ 0x7 + 0x8 = 5 3x1 + 0x2 + 2x3-1x4 + 6x5 + 0x6+ 1x7 + 0x8 = 7 1x1 + 0x2-1x3 + 2x4 + 1x5 + 0x6+ 0x7 + 1x8 = 2

: F(X) = - Mx6 - Mx7 - Mx8 => max , . , , . : x6 = 5-2x1-x2-x3-x4-3x5x7 = 7-3x1-2x3+x4-6x5x8 = 2-x1+x3-2x4-x5: F(X) = - M(5-2x1-x2-x3-x4-3x5) - M(7-3x1-2x3+x4-6x5) - M(2-x1+x3-2x4-x5)=> max F(X) = (6M)x1+(1M)x2+(2M)x3+(2M)x4+(10M)x5+(-14M)=> max x0 = 6x1 + x2 + 2x3 + 2x4+ 10x5. <6, 7, 8> . x0 = -14+6x1+x2+2x3+2x4+10x5x6 = 5-2x1-x2-x3-x4-3x5x7 = 7-3x1-2x3+x4-6x5x8 = 2-x1+x3-2x4-x5-. , x0. max(6,1,2,2,10,0,0,0) = 10 x0 = -14+6x1+x2+2x3+2x4+10x5x6 = 5-2x1-x2-x3-x4-3x5x7 = 7-3x1-2x3+x4-6x5x8 = 2-x1+x3-2x4-x5x5. D5 .

bi / ai5 : min (5 : 3 , 7 : 6 , 2 : 1 ) = 11/6x7 x5. x5 x7x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7. x0 = -14+6x1+x2+2x3+2x4+10(11/6-1/2x1-1/3x3+1/6x4-1/6x7) x6 = 5-2x1-x2-x3-x4-3(11/6-1/2x1-1/3x3+1/6x4-1/6x7) x8 = 2-x1+x3-2x4-(11/6-1/2x1-1/3x3+1/6x4-1/6x7) , , : x0 = -21/3+x1+x2-11/3x3+32/3x4-12/3x7x6 = 11/2-1/2x1-x2-11/2x4+1/2x7x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7x8 = 5/6-1/2x1+11/3x3-21/6x4+1/6x7x = (6, 5, 8) , : x = (-1, -1, 11/3, -32/3, 0, 0, 12/3,0), x0 = -21/3max(1,1,-11/3,32/3,0,0,-12/3,0)= 32/3x0 = -21/3+x1+x2-11/3x3+32/3x4-12/3x7x6 = 11/2-1/2x1-x2-11/2x4+1/2x7x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7x8 = 5/6-1/2x1+11/3x3-21/6x4+1/6x7x4. D4 . bi / ai4 : min (11/2 : 11/2 , - , 5/6 : 21/6) = 5/13x8 x4. x4 x8x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8. x0=-21/3+x1+x2-11/3x3+32/3(5/13-3/13x1+8/13x3+1/13x7-6/13x8)-12/3x7x6=11/2-1/2x1-x2-11/2(5/13-3/13x1+8/13x3+1/13x7-6/13x8)+1/2x7x5=11/6-1/2x1-1/3x3+1/6(5/13-3/13x1+8/13x3+1/13x7-6/13x8)-1/6x7, , : x0 = -12/13+2/13x1+x2+12/13x3-15/13x7-19/13x8x6 = 12/13-2/13x1-x2-12/13x3+5/13x7+9/13x8x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8x = (6, 5, 4) , : x = (-2/13, -1, -12/13, 0, 0, 0, 15/13, 19/13),x0 = -12/13max(2/13,1,12/13,0,0,0,-15/13,-19/13)= 1 x0 = -12/13+2/13x1+x2+12/13x3-15/13x7-19/13x8x6 = 12/13-2/13x1-x2-12/13x3+5/13x7+9/13x8x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8x2. D2 . bi / ai2 : min (12/13 : 1 , - , - ) = 12/13x6 x2. x2 x6x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8. x0=-12/13+2/13x1+(12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8)+12/13x3-15/13x7-19/13x8x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8, , : x0 = 0-x6-x7-x8x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8x = (2, 5, 4) , : x = (0, 0, 0, 0, 0, 1, 1, 1), x0 = 0 x0 . . x0 = 0-x6-x7-x8x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8

( ) - . . . x2 = 12/13-2/13x1-12/13x3x5 = 13/13-7/13x1-3/13x3x4 = 5/13-3/13x1+8/13x3

: x5 = 13/13-7/13x1-3/13x3x4 = 5/13-3/13x1+8/13x3: F(X) = + 3x3-2(5/13-3/13x1+8/13x3)-(13/13-7/13x1-3/13x3) F(X) = -2+x1+2x3. x0 = -2+x1+2x3x2 = 12/13-2/13x1-12/13x3x5 = 13/13-7/13x1-3/13x3x4 = 5/13-3/13x1+8/13x3max(1,0,2,0,0) = 2 x0 = -2+x1+2x3x2 = 12/13-2/13x1-12/13x3x5 = 13/13-7/13x1-3/13x3x4 = 5/13-3/13x1+8/13x3x3. D3 .

bi / ai3 : min (12/13 : 12/13 , 13/13 : 3/13, - ) = 1 x2 x3. x3 x2x3 = 1-1/6x1-11/12x2. x0 = -2+x1+2(1-1/6x1-11/12x2) x5 = 13/13-7/13x1-3/13(1-1/6x1-11/12x2) x4 = 5/13-3/13x1+8/13(1-1/6x1-11/12x2) , , : x0 = 0+2/3x1-21/6x2x3 = 1-1/6x1-11/12x2x5 = 1-1/2x1+1/4x2x4 = 1-1/3x1-2/3x2x = (3, 5, 4) , : x = (-2/3, 21/6, 0, 0, 0), x0 = 0 max(2/3,-21/6,0,0,0) = 2/3x0 = 0+2/3x1-21/6x2x3 = 1-1/6x1-11/12x2x5 = 1-1/2x1+1/4x2x4 = 1-1/3x1-2/3x2x1. D1 . bi / ai1 : min (1 : 1/6 , 1 : 1/2 , 1 : 1/3 ) = 2 x5 x1. x1 x5x1 = 2+1/2x2-2x5. x0 = 0+2/3(2+1/2x2-2x5)-21/6x2x3 = 1-1/6(2+1/2x2-2x5)-11/12x2x4 = 1-1/3(2+1/2x2-2x5)-2/3x2, , : x0 = 11/3-15/6x2-11/3x5x3 = 2/3-11/6x2+1/3x5x1 = 2+1/2x2-2x5x4 = 1/3-5/6x2+2/3x5x = (3, 1, 4) , : x = (0, 15/6, 0, 0, 11/3), x0 = 11/3x0 . . : x0 = 11/3-15/6x2-11/3x5x3 = 2/3-11/6x2+1/3x5x1 = 2+1/2x2-2x5x4 = 1/3-5/6x2+2/3x5

: x1 = 2 x3 = 2/3x4 = 1/3F(X) = 32/3 + 02 = 11/3

:

  1. - n!/((n-m)!*m!)
  2. , 0, .
  3. , .

. -, M-

math.semestr.ru

Интерактивный подход к решению задач линейного программирования методом больших штрафов

Библиографическое описание:

Папинашвили В. Г. Интерактивный подход к решению задач линейного программирования методом больших штрафов // Молодой ученый. — 2017. — №13. — С. 14-16. — URL https://moluch.ru/archive/147/41205/ (дата обращения: 08.03.2018).



В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида «», но и условия видов «» и «=»). Такую задачу, где необходимо будет вводить искусственные переменные, можно будет решить методом больших штрафов. Данная статья посвящена обучению пользователя этому методу посредством интерактивного пошагового решения.

Ключевые слова: метод больших штрафов, симплекс-метод

Для того чтобы приступить к интерактивному пошаговому решению задач методом больших штрафов, необходимо изучить теорию по данному методу, а также иметь знания и навыки решения ЗЛП симплекс-методом.

Интерактивное решение задачи данным методом было решено реализовывать следующими средствами: JavaScript (объектно-ориентированный (прототипный) язык программирования) и HTML (язык гипертекстовой разметки). Данные средства являются наиболее простыми и понятными в реализации пошагового решения задачи.

Решение любой задачи начинается с её постановки. Математическая постановка выглядит следующим образом:

Целевая функция (далее ЦФ):

Ограничения:

Так как постановка задачи представляется в текстовом виде, а также в виде формул, реализовывать её достаточно только средствами HTML. Кнопку, чтобы приступить к самому решению задачи, для проверки правильности ответа и для перехода к следующему шагу задачи, также можно реализовать средствами HTML. Но, для того, чтобы при нажатии кнопки, программа выдавала пользователю сообщение о верности его ответа, и перемещала на следующий шаг, данное средство уже не поможет. Эта функция будет реализована с помощью языка программирования — JavaScript. На рисунке 1 представлена данная реализация.

Рис. 1. Фрагмент интерактивного решения задачи, реализованный средствами JavaScript и HTML

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

1) Ввод данных вручную (рисунок 2)

2) Выбор одного варианта (рисунок 3)

3) Выбор одного или нескольких вариантов (рисунок 4)

Рис. 2. Ввод данных вручную

Рис. 3. Выбор одного варианта

Рис. 4. Выбор одного или нескольких вариантов

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

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

Таким образом, в данной статье было описано и реализовано интерактивное обучение пользователей «Методу больших штрафов», которое поможет им получить практические навыки в решении задач данным методом и закрепить изученный материал прохождением теста.

Литература:
  1. Таха Х. А. Введение в исследование операций 6-е издание. Пер. с англ. — Москва: Издательский дом «Вильямс», 2005. – 912 с.
  2. Зайченко Ю. П. Исследование операций: Учеб. пособие для студентов вузов. — 2-е изд., перераб. и доп.— Киев: Вища школа. Головное изд-во, 1979. 392 с.
  3. Б. Хеник. HTML и CSS. Путь к совершенству (HTML and CSS: The Good Parts), 2010. — 362 c.
  4. Дэвид Флэнаган — «JavaScript. Подробное руководство (JavaScript. The Definitive Guide)», Издательство: Символ-Плюс, 2008 г., 992 с.

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

moluch.ru


Смотрите также