Реализация метода Искусственного Базиса

Содержание

 

Введение

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

1.1 Задачи линейного программирования и свойства ее решений     

1.2 Форма задачи линейного программирования и свойства ее решений

1.3 Переход к канонической форме

1.4 Табличный симплекс-метод

1.5 Метод искусственного базиса

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

2.1 Содержательная постановка  задачи

2.2 Математическая модель задачи

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

2.4 Решение задачи с  помощью Excel

Заключение

Список литературы

  

          Введение

Линейное программирование - это наука о методах исследования и

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

Для решения задач  линейного программирования потребовалось  создание специальных методов. В  данной курсовой работе будет рассмотрен метод «искусственного» базиса (симплекс метод) решения задач линейного программирования. Метод «искусственного» базиса  используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств.

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

 

 

где М – достаточно большое положительное  число. Составленная таким образом  задача называется М–задачей линейного  программирования.

Таким образом, целью данной курсовой работы является: освоить навыки использования метода «искусственного» базиса  для решения задач линейного программирования.

 Для этого были  поставлены следующие задачи:

1. Изучить теоретические сведения, необходимые для решения задач линейного программирования методом «искусственного» базиса.
2. Разобрать алгоритм решения ЗЛП методом «искусственного» базиса.
3. Решить поставленную задачу, используя рассмотренный метод решения задач линейного программирования.

 

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

 

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

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

 

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

Общая схема формализации задач управления и планирования может быть описана следующим образом:

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

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

качества при условии, что переменным ограничениям, составляет предмет 

 

 

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

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

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

Общая задача линейного программирования формулируется таким образом:

требуется найти максимум (или минимум) линейной функции n переменных  x₁, x₂,…,x_n:

  (0.1)

При ограничениях, наложенных на переменные x₁, x₂,…,x_n  вида

                (0.2)

 

      (0.3)

                            (0.4)

Линейную функцию (0.1) – критерий качества выбранных данных переменных – принято называть линейной формой   задачи, а множество наборов (x₁, x₂,…,x _n), удовлетворяющих условиям (0.2)-(0.4), - областью определения задачи линейного программирования или областью определения линейной формы. На первый взгляд может показаться, что сформулированная задача (0.1)-(0.4) весьма проста и легко решается обычными методами классического анализа. Однако это не так. Известные методы решения задач на условный экстремум с помощью, так называемых множителей Лагранжа здесь неприменимы. Линейность функции L(x₁,….,x _n) вносит в экстремальную задачу определенную специфику. Дело в том, что линейная функция, заданная в ограниченной области, достигает своего максимума и минимума на границе области в точках, в которых соответствующие частные производные, вообще говоря, не обращаются в нуль. Это значит, что классические методы дифференциального исчисления, разработанные для отыскания экстремальных точек внутри области определения функции, здесь не могут быть использованы.

При анализе системы  условий (0.2) – (0.4) могут представиться три случая:

 а) Условия (0.2) – (0.4) противоречивы. Другими словами, не существует набора чисел x₁,….,x _n, удовлетворяющие всем условиям задачи.

б) Условия (0.2) – (0.4) непротиворечивы, а область, определяемая ими, неограниченна. Другими словами, существуют наборы чисел x₁,….,x _n, удовлетворяющие системе (0.2) – (0.4) и содержащие отдельные переменные

 

со сколь угодно большими значениями.

в) Система условий (0.2) – (0.4) совместна и область, определяемая ею, ограничена.

Практические задачи обычно приводят к последнему случаю. Дальше будет показано, что в этом случае область, заданная системой (0.2)-(0.4), представляет собой выпуклый многогранник в n-мерном пространстве и экстремум линейной формы L достигается в его вершинах. Однако, уже при относительно небольших n, r и t (случаи, к которым сводятся сравнительно простые практические задачи), количество вершин многогранника исчисляется многими миллиардами. Это значит, что неупорядоченный перебор вершин с целью выявления точки, в которой линейная форма достигает своего наибольшего или наименьшего значения, по-видимому, практически невыполнимая работа даже для самых быстродействующих современных вычислительных машин. Как мы увидим дальше, различные методы решения задач линейного программирования представляют собой те или иные рекомендации по упорядочению перебора вершин многогранника, определяемого условием задачи.

Введем понятие разрешимости задачи, важное для последующего изложения.

Задача линейного программирования называется разрешимой, если существует набор чисел (x₁, x₂,…,x _n,) (x_i<∞), удовлетворяющий всем ограничениям (0.2) – (0.4) и обращающий линейную форму в максимум или минимум (в зависимости от постановки задачи).

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

 

 

области ее определения.

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

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

 

1. Задачи линейного программирования и свойства ее решений

 

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

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

Особенностью задач  линейного программирования является то, что

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

допустимых значений. Отсюда — необходимость разработки новых методов.

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

Общей задачей линейного  программирования называют задачу:

 

 

 

 

                           (1)

при ограничениях

            (2)

            (3)

            (4)

            (5)

- произвольные   (6)

где - заданные действительные числа; (1) – целевая функция;

(1) - (6) – ограничения; - план задачи.

 

Пусть Задача ЛП представлена в следующей записи:

                                         (7)

          (8)

           (9)

 

Чтобы задача (7) – (8) имела  решение, системе её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при

оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов содержит базис — максимальную линейно независимую

 

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

несколько, но не более  . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будут

свободными, их обозначают СП. Не ограничивая общности, будем  считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные  значения, то полученное частное решение  системы (8) называют опорным решением (планом).

Теорема.

Если система векторов содержит m линейно независимых векторов , то допустимый план       

является крайней точкой многогранника планов.

Теорема.

Если ЗЛП имеет решение, то целевая функция достигает экстремального

значения, хотя бы в одной из крайних точек многогранника решений.

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

 

 

 

 

1.2 Форма задачи линейного  программирования и свойства  ее решений.

В зависимости  от вида ограничений различают следующие  формы задач:

• Каноническая
• Симметричная
• Общая

 

Задача в  канонической форме – задача ЛП, в которой все ограничения есть равенства (p = q = 0) и все переменные неотрицательные (r = n).

Общий метод решения  задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

( ) = ( * ) →

=

=   – вектор коэффициентов критерия

= -  вектор переменных

 

 

= – матрица условий (технологических коэффициентов)

= ( )

=  – вектор условий

=    – вектор ограничений

 

( ) = ( * )

+ + …+ =

,

 

Для неё разработан метод  решения, который называется симплексным.

Задача в  симметричной форме – задача ЛП, в которой все ограничения есть неравенства (p = q = m) и все переменные неотрицательные (r = n).

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

 

 

 

Симметричная форма допускает  графическое решение (иллюстрацию).

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

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

 

Сведение задачи минимизации  к задаче максимизации:

Преобразование сводится к смене  знака критерия (Рисунок 1).

( ) ~ ( ( ))

 

( ) = ( ( ))

 

Рисунок 1

 

Переход от ограничений-неравенств к уравнению:

 

+ =

Переменные  - дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.

 

 

 

 

- =

 

Переход от переменных произвольного  знака к неотрицательным переменным:

= -

Переход от переменных, ограниченных снизу, к неотрицательным:

= +

Переход от уравнений  к неравенствам:

Если имеется уравнение:

то оно заменяется на два неравенства:

 

Пусть есть несколько  ограничений:

 

А также:

Пусть ранг (количество линейно-независимых  уравнений) системы ограничений  равен  , тогда переменных можно выразить через остальные:

 

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

Задавая произвольные значения свободным переменным, получаем частные решения, но не все они удовлетворяют условиям неотрицательности:

Тогда для свободных переменных получаем ограничения в виде неравенств:

 

 

Если ( ) = 2, то задача допускает иллюстрацию в пространстве двух переменных.

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

 

Примеры решения задач

Каноническая форма

 

 

 

 

Симметричная форма

 

1.3 Переход к канонической форме

В каждой задаче ЛП ищутся значения переменных при условии, чтобы:

• эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
• при этих значениях целевая функция обращалась бы в минимум или максимум.

 

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

Определение.

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

Утверждение. 

Любая общая задача ЛП может быть приведена к канонической форме.  
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных. Система ограничений этой задачи состоит из четырех неравенств. Введя дополнительные переменные y₁≥  0, y₂ ≥  0, y₃ ≥  0, y₄ ≥  0, можно перейти к системе ограничений:

 

 

Эти дополнительные переменные y _i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).  
Например, если бы машины первого вида работали все 18 ч, то x + y = 18,

следовательно, y₁ = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y<18. В этом случаеy₁ приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из пункта 3.3.2, x =  12, y  =  6, мы можем из системы ограничений (3.9) сделать вывод, что y₁  =  y₂  =  y₃  =  0, а y₄  =  12 – 6  =  6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой,            сдать в аренду на это время и т.д.  
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о  смеси. Система ограничений имеет  вид:

Неравенства были обращены в сторону «больше», поэтому вводя  дополнительные переменные y₁, y₂, y₃ ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:

Переменные y_i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y₁ будет означать количество излишнего вещества А в смеси, y₂ –количество излишков вещества В в смеси, y₃ – излишки С в смеси.  
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения maxF = –min (–F ). Посмотрите на рисунок 3.9: если в какой-то точке x= x₀ функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x₀ достигнет минимума, причем F_max = – (–F_min) при x =  x₀.

Вывод. Для представления задачи ЛП в канонической форме необходимо:

• неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
• если целевая функция F →max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).

 

Рисунок 2

1.4 Табличный симплекс-метод

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

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n + x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n +x_n+2 =b₂

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

Исходная таблица для  задачи имеет следующий вид(Таблица 1):

                                                                                                     Таблица 1

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

x₁, x₂, x_n - исходные переменные, x_n+1, x_n+2, x_n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а

исходные переменные как небазисные(дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку).

При каждой итерации элементы симплекс-таблицы  пересчитывают по определенным правилам.

Алгоритм  симплекс-метода.

Приводим задачу ЛП  к каноническому виду

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁