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

    

 

 

Введение

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

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

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

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

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

На основе поставленной цели были определены задачи:

• изучить симплексный метод решения задач линейного программирования;
• рассмотреть решение симплексным методом в MS Excel;
• разработать свое приложение для решения задачи симплексным методом.

Курсовая работа состоит  из введения, 4 параграфов, заключения, списка литературы и приложения. В первом параграфе приводится постановка задачи линейного программирования, кратко даются теоремы, во втором – приводятся рассмотрение симплексного метода, применение MS Excel при решении, третий параграф посвящен описанию разработанного приложении и четвертом рассматривается пример решения задачи.

 

 

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

1. Основные понятия и определения.

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

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

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

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

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

Различают три основные формы задач линейного программирования в зависимости от наличия ограничений разного типа.

Стандартная задача линейного программирования.

или, в матричной записи,

где , , , — матрица коэффициентов. Вектор с называется вектором коэффициентов линейной формы, b— вектором ограничений. 

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

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

или, в матричной записи,

Основные вычислительные схемы (симплекс-метод и его модификации) решения задач линейного программирования разработаны именно для канонической задачи.

Общая задача линейного  программирования

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

Здесь , . Ясно, что стандартная задача получается как частный случай общей при , ; каноническая — при , .

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

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

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

или, в матричной форме,

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

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

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

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

Еще проще процесс сведения канонической задачи к стандартной  — надо лишь каждое уравнение из системы ограничений заменить двумя  неравенствами:

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

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

3. Теоремы задачи линейного программирования

Пусть исходная ЗЛП имеет  вид:

                                                   (1)

                                                (2)

                                             (3)

                                                        (4)

Преобразуем ее к каноническому виду. Введем m дополнительных (балансовых) неотрицательных переменных . Для того чтобы неравенства (2) преобразовать в равенства, к их левым частям прибавим дополнительные переменные , после чего система неравенства (2) примет вид

  .                                        (5)

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

,  ( ).                                      (6)

Систему уравнений (5) ((6)) с  условием неотрицательности дополнительных переменных называют эквивалентной системе неравенств (2) ((3)).

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

                                                (7)

  ,                                              (8)

   ( ),                                           (9)

  ( ),  .                                         (10)

Задача (7) – (10) имеет каноническую форму. Задачи (1) – (4) и (7) – (10) тесно  связаны между собой.

Теорема 1. Каждому допустимому решению задачи (1) – (4) соответствует вполне определенное допустимое решение ( ) задачи (7) – (10), где , и наоборот, каждому допустимому решению задачи (7) – (10) соответствует допустимое решение задачи (1) – (4).

Перейдем к геометрической интерпретации ЗЛП с n переменными:

                                                          (11)

   ,                                                     (12)

                                                             (13)

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

Множество планов, удовлетворяющих  системе ограничений ЗЛП (12), (13), представляет собой пересечение конечного числа полупространства и потому является выпуклым. Отсюда следует теорема.

Теорема 2. Множество  планов ЗЛП выпукло.

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

Целевую функцию (11) геометрически  можно рассматривать как семейство  параллельных гиперплоскостей  , каждой из которых соответствует определенное значение параметра Z. Вектор , перпендикулярный к гиперплоскостям Z=const, указывает направление наискорейшего возрастания функции Z.

С учетом сказанного, задача (11) – (13) геометрически сводится к  нахождению точки многогранника (многоугольной области), определяемого неравенствами (12), (13), через которую проходит гиперплоскость семейства (11), соответствующая наибольшему значению Z.

Графическим методом можно  решить ЗЛП с n > 2 переменными, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n – m 2.