Линейное программирование

     Введение

         Линейное программирование —  математическая дисциплина, посвящённая  теории и методам решения    экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных  уравнений и неравенств.

     

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

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

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

     Алгоритмы решения общей задачи линейного  программирования 

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

         Первый полиномиальный алгоритм, метод эллипсоидов, был предложен  в 1979 г. советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 60-х гг. Фиако (Fiacco) и МакКормиком (McCormick).

1.Постановка  задачи 

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

         Производитель элементов центрального  отопления изготавливает радиаторы  четырёх моделей. Ограничения на производство, обусловлены количеством рабочей силы и количеством стальных листов, из которых изготавливаются радиаторы, соответственно равны 500, 2500. Определить максимальную прибыль от продажи радиаторов, используя симплекс-метод. Все необходимые данные приведены в таблице. 

 

 
2.Математическая модель 

         Для того чтобы составить математическую модель, вводятся следующие обозначения:

      - количество радиаторов А

      - количество радиаторов В

      - количество радиаторов С

      - количество радиаторов D

        Ограничения по количеству рабочей  силы:

     0,5 +1,5 +2 +1,5 ≤500

     Ограничения по количеству стальных листов:

     4 +2 +6 +8 ≤2500

     Т.к. прибыль должна быть максимальной, задача будет иметь вид:

     F=5 +5 +12,5 +10 max

     xj≥0      (j= )

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

     

 
3.Обзор и анализ существующих методов решения задачи 

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

     Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

     Последовательность  вычислений симплекс-методом можно  разделить на две основные фазы:

1.нахождение исходной вершины множества допустимых решений,

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

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

     4. Описание выбранного алгоритма 

      Алгоритм:

1. Просматриваем m+1 строку, если среди оценок есть отрицательное, то выбираем минимальную среди отрицательных оценок.

Столбец соответствующий этому условию называется разрешающим столбцом.

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

1. разрешающую строку делим на разрешающий элемент и записываем в новую таблицу на это же место;

2. все остальные элементы пересчитываются по методу Джордано-Гаусса (метод прямоугольников)

 

5. В новой  симплексной таблице заполняется m+1 строка, если все оценки не отрицательны, то полученный опорный план оптимальный, если среди оценок есть хотя бы одна отрицательная оценка, то переходим к пункту 1 алгоритма.

  Примечание: Если задача линейного программирования решается на min, то изменяется пункт 1: среди оценок выбирается max среди положительных оценок , и далее переходим к пункту 2 алгоритма

 

5.Средства решения задачи 

1. Технические средства решения задачи

 

     Оценка: 5.0 Индекс производительности Windows

     Процессор: AMD Athlon™ 64 X2 Dual Core Processor 5200+ 2.70 GHz

     Установленная память(ОЗУ): 2.00 ГБ

     Тип системы: 32-х разрядная операционная система  

2. Инструментальные  средства разработки

 

  Borland Delphi

  Говоря  о том или ином средстве разработки приложений, всегда хочется понять, какие тенденции приводят к его появлению. Borland Delphi не является исключением из правил. Итак, что же мы имели к середине 90-х? 
Одно направление - объектно-ориентированный подход, хорошо структурирующий задачу, как таковую, так и ее решение в виде прикладной системы.  
Другое направление, возникшее во многом благодаря объектной ориентации, - визуальные средства быстрой разработки приложений (RAD - Rapid Application Development), основанные на компонентной архитектуре. 
Третья тенденция - использование компиляции, а не интерпретации. Это объясняется тем, что скоростные характеристики компилируемых приложений в десятки раз лучше, чем у систем, использующих интерпретатор. При этом повышается легкость отчуждаемости готовых систем, так как отпадает необходимость "таскать за собой" сам интерпретатор (run-time), выполненный обычно в виде динамической библиотеки и занимающий в лучшем случае несколько сотен килобайт (а большинстве случаев два-три мегабайта). Отсюда и меньшая ресурсоемкость систем. 
Четвертая тенденция - возможность работы с базами данных универсальными (единообразными) методами. Если мы попытаемся оценить процент систем, которые так или иначе требуют обработки структурированной информации (как для внутрикорпоративного использования, так и для коммерческого или иного распространения), то окажется, что цифра 60- 70% может представлять лишь нижнюю границу. Важным свойством средств обеспечения доступа к базам данных является их масштабируемость, как возможность не только количественного, но и качественного роста системы. Например, обеспечение перехода от локальных, в том числе, файл-серверных данных к архитектуре клиент-сервер или тем более к многоуровневой N-tier схеме. Delphi создавался как продукт, в полной мере реализующий описанные тенденции, с архитектурой, открытой для расширения спектра поддерживаемых стандартов и подходов.

 

6. Информационное обеспечение задачи

 

1. Входная информация

 

Входная информация в приложении – это ввод количества базовых переменных, количества переменных, степени точности, задача (на max, на min):