Симплексный метод решения ЗЛП

Базисными переменными  при этом будутx_l,x_k+1,x_k+2,…,x_r-1, x_r-1,…,x_r.

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

Пример 2. Пусть имеется задача линейного программирования с ограничениями-неравенствами:

-5x₁-x₂+2x₃≤2;

-x₁+x₃+x₄≤5; (2.5)

-3x₁+5x₄≤7.

 

Требуется минимизировать линейную функцию

 

Z=5x₁-2x₃

Приводя неравенства  к стандартному виду (≥0) и вводя добавочные переменныеy₁,y₂,y₃переходим к условиям-равенствам:

y₁=5x₁+x₂-2x₃+2

y₂=x₁-x₃-x₄+5 (2.5)

y₃=3x₁-5x₄+7

 

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут  быть выбраны в качестве свободных.

Пусть в качестве свободных переменных выступаютx₁,x₂,x₃,x₄. Положим их равными нулю и получим опорное решение:

 

x₁=x₂=x₃=x₄=0;

y₁=2, y₂=5, y₃=7.

 

При этих значениях  переменных Z= 0.

Это решение  не оптимально, поскольку в линейной функции Z коэффициент приx₃отрицателен. Значит, увеличиваяx₃можно уменьшить Z.

Попробуем увеличиватьx₃.Из выражений (2.5) видно, что вy₁и y₂переменнаяx₃входит с отрицательным коэффициентом, значит, при увеличенииx₃соответствующие переменные могут стать отрицательными.

Определим, какая из этих переменных (y₁илиy₂)раньше обратится в нуль при увеличенииx₃Очевидно, что этоy₁она станет равной нулю приx₃=1, а величинаy₂— только приx₃= 5.

Выбирается  переменная у, и вводится в число  свободных вместоx₃Чтобы разрешить систему (2.5) относительноx₃, y₂, y₃поступим следующим образом. Разрешим первое уравнение (2.5) относительно новой базисной переменнойx₃:

 

x₃=5/2*x₁+1/2*x₂-1/2*y₁+1

Это выражение  подставляется вместоx₃во второе уравнение:

 

x₃=5/2*x₁+1/2*x₂-1/2y₁+1;

y₂=-3/2*x₁-1/2*x₂+1/2*y₁-x₄+4; (2.6)

y₃=3x₁-5x₄+7.

 

Что касается третьего уравнения, то оно, как не содержащееx₃не изменится. Система (2.2) приведена к виду со свободными переменнымиx₁, x₂, y₁, x₄и базиснымиx₃, y₂, y₃.

Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее  значение Z= 0.

Это решение  все еще не оптимально, так как  коэффициент приx₂в выражении (2.7) отрицателен, и переменнаяx₂может быть увеличена. Это увеличение, как это видно из системы (2.6), может сделать отрицательнойy₂(в первое уравнениеx₂входит с положительным коэффициентом, а в третьем — отсутствует).

Поменяем  местами переменныеx₂ и y₂— первую исключим

из числа  свободных, а вторую — включим. Для  этого разрешим второе уравнение (2.6) относительноx₂и подставимx₂в первое уравнение. Получим следующий вид системы (2.5):

 

x₃=x₁-y₂-x₄+5

y₂=-3x₁-2y₂+y₁-2x₄+8  (2.7)

y₃=3x₁-5x₄+7

 

Выразим Z через  новые свободные переменные:

Z=3x₁+2y₂-y₁+2x₄-8+y₁-2=3x₁+2y₂+2x₄-10 (2.8)

Полагаяx₁=y₁=y₂=x₄=0 , получим Z = -10.

Это решение  является оптимальным, так как коэффициенты при всех свободных переменных в выражении (2.8) неотрицательны. Итак, оптимальное решение ОЗ найдено (2.9):

x₁^*=0, x₂^*=8, x₃^*=5, x₄^*=0, y₁^*=0, y₂^*=0, y₃^*=7. (2.9)

При таких  значениях переменных линейная функция Z принимает минимальное значение (2.10):

 

Z_min=-10 (2.10)

 

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

 

2.4 Двойственная  задача

 

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

Задача ЛП в канонической форме имеет вид:  
максимизировать L(x) = сумма от j=1 до n (сjчj) 
при условиях: 
сумма от j=1 до n (аjXj)=bv, (v=1,2,....m) 
или 
сумма от j=1 до n (АjXj)=b, xj>=0,  j=1,2,...n

Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:  
Прямая задача Двойственная задача

 
maxZ=x₁-3x₃-3x₄-MR₁-MR₂

y₁: x₁+2x₃-2x₄+x₅=4

y₂: 3x₁-4x₃+4x₄+R₁=11

y₃: x₁+x₃-x₄-x₆+R₂=0

minW=4y₁+12y₂

x₁: y₁+3y₂+y₃≥1

x₃: 2y₁-4y₂+y₃≥-3

-2y₁+4y₂-y₃≤3(1)

X₄: -2y₁+4y₂-y₃≥3  (2)

X₅: y₁≥0

X₆: -y₃≥0 => y₃≤0

R₁: y₂≥-M

R₂: y₃≥-M 
Итак, получено: y₁≥0,y₂≤≥0 ,y₃≤0. 

 
2. Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки:y₂=y₄-y₅; y₃=-ỹ_3; ỹ₃,y₄,y₅≥0 
Для удобства решения свернём ограничения (1) и (2) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные. 

 

minW=4y₁+12y₄-12y₅+MR₁+MR₂

y₁+3y₄-3y₅-ỹ₃-y₆+R₁=1  (3)

-2y₁+4y₄-4y₅+ỹ₃+R₂=3  (4)

 
3. Решим ДЗ симплекс методом:  
Из (3) выразим: R₁=1-y₁-3y₄+3y₅+ỹ₃+y₆ 
Из (4) выразим:R₂=3+2y₁-4y₄+4y₅-ỹ₃

W+y₁(-4-M)+y₄(-12+7M)+y₅(12-7M)-My₆=4M

 

Создаём симплекс-таблицы:

 

Таблица 2.2 – симплекс-таблица №1 

	W	y1	y4	y5	ỹ3	y6	R1	R2	ПЧ
W	1	-4-M	7M-12	12-7M	0	-M	0	0	4M
R1	0	1	3	-3	-1	-1	1	0	1
R2	0	-2	4	-4	1	0	0	1	3

 

 

B^-1(0)= B(0)=

 

Таблица 2.3 –  симплекс-таблица №2 

	W	y1	y4	y5	ỹ3	y6	R1	R2	ПЧ
W	1	-10/3M	0	0	7/3M-4	4/3M-4	-7/3M+4	0	5/3M+4
y4	0	1/3	1	-1	-1/3	-1/3	1/3	0	1/3
R2	0	-10/3	0	0	7/3	4/3	-4/3	1	5/3

 

B^-1(1)=   B(1)=  

Таблица 2.4 – симплекс-таблица №3

	W	y1	y4	ỹ5	ỹ3	y6	R1	R2	ПЧ
W	1	-40/7	0	0	0	-12/7	-7/3M+4	-M+12/7	48/7
y4	0	-1/7	1	-1	0	-1/7	1/3	1/7	4/7
ỹ3	0	-10/7	0	0	1	4/7	-4/3	-3/7	5/7

 

Симплекс-таблица №3 – оптимальная, т. к. коэффициенты приНБП≥0 
minW=48/7, maxZ=minW=48/7,

y₁^*=0, y₂^*=y₄^*-y₅^*=4/7, y₃^*=-5/7

Двухфазовый симплекс метод, иначе называют методом искусственного базиса:

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

Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация. Из изложенного выше не прозвучало отчетливо почему если ограничения отличается от <= не всякий 0-вектор будет допустимым решением. В самом деле пусть i - уравнение имеет вид Ai1X1+...AinXn>=Bi но просто можно изменить знаки записав -Ai1X1- ... AinXn<=-Bi и тем самым привести все неравенства к канонической форме. Это было бы нельзя сделать если бы на вектор B было наложено условие неотрицательностиBi>=0 Но в формулировке выше ограничения вектор B отсутствуют. (это очевидная неточность для теоретической статьи в энциклопедии, где все предпосылки должны формулироваться полно) Если бы все было так просто и легко, непонятно зачем изобретали двухфазный метод... Кроме того по этой же причине классический симплекс метод не годится для решения задачи Min F (точнее не годится в случае положительности всех коэфф целевой функции, т.к. тогда метод не сделает ни одной итерации).

 

ІІІ  КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА ПРИ РЕШЕНИИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

 

3.1 описание программного продукта

 

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

 •  порождение начального базисного  допустимого решения;

 •  поиск оптимального плана и  экстремума нецелочисленной задачи  линейного программирования;

 •  поиск оптимального плана и  экстремума полностью целочисленной  задачи линейного программирования;

 •  поиск оптимального плана и  экстремума частично целочисленной  задачи линейного программирования;

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

 Рассмотрим  особенность функционирования программного  комплекса. Для организации диалога  с пользователем применяется  стандартный графический интерфейс  Windows, построенный на основе библиотеки  визуальных компонентов VCL (VisualComponentLibrary), поставляемой вместе с пакетом  Delphi. При разработке программы  использовалась MDI-технология (MultipleDocumentInterface – многодокументный пользовательский  интерфейс), что позволяет пользователю  работать сразу с несколькими  задачами линейного программирования. В программе реализована активная  форма диалога, позволяющая выбирать  режимы: расчет, просмотр и редактирование  информации, получение справки и т.д.