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

Содержание

 

Введение

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 переменных будут