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

Таблица 1. –Пример симплекс-таблицы 

 

 

 

 

 

 

 

 

 

 

 

 

2.ВЫЧИСЛЕНИЕВЕРОЯТНИСТИНАЛИЧИЯ РЕШЕНИЯ

2.1 Блок схема будущей программы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2. Обоснование выбора языка программирования

 

Для практической реализации я выбрал программную  среду С++ builder, так как в ней довольно не сложно реализовать нашу задачу, он гибок в использовании и в дальнейшем, если будет интерес, возможно будет реализовать графический интерфейс.

Borland  C++  Builder  6 – очередная версия системы объектно – ориентированного  программирования  для 32-разрядных операционных  систем  Microsoft Windows. Интегрированная среда системы (Integrated  Development  Environment, IDE)  обеспечивает  продуктивность  многократного использования визуальных  компонентов в сочетании с усовершенствованными  инструментами и разномасштабными  средствами  доступа к базам данных.  Основное  предназначение  IDE – радикально  ускорит производительный  цикл  разработки  сложнейших  программных проектов  для различных областей  применения.

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

Среди  множества  нововведений  следует  особо  отметить  эффективность  средства  для  поддержки  web – служб и разработки  переносимых проектов.  Технологии  DataSnap,  WebServices  и WebSnap дают  возможность быстро  и легко создать и интегрировать сетевые приложения  (как персональные,  так и коллективные).  Клиентские  и серверный  модули  распределенного приложения 

обмениваются  XML – илиWSDL – документами в рамках  транспортных  протоколов  TCP/IP,  HTTP, SOAP. Библиотека  компонентов CLX  обеспечивает  переносимость исполняемого  кода  между платформами Windows  и Linux.  CLX – приложения  совместимы  на  уровне  языка С++  с программными  продуктами,  которые корпорация  Borland  планирует выпускать для операционной  системы Linux.

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

 

Для  установки  системы  необходим  персональный  компьютер  в  следующей  конфигурации:

• Процессор  Intel  Pentium  с тактовой  частотой  не  ниже  166  МГц;
• Операционная  система  Microsoft  Windows  98/  Millennium  (Me)/  NT/  2000/  XP;
• Оперативная  память  не  менее  128 Мбайт, рекомендуется  256 Мбайт;
• До  750  Мбайт  свободного  пространства  на  жестком  доске,  в  зависимости  от  выбранных  параметров  установки;
• Дисковод  для  компакт – дисков;
• Видеоадаптер  с  разрешением  не  хуже,  чем  в  стандарте  SVGA;
• Сетевой  адаптер;
• Мышь  или  другой  координатный  манипулятор.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3 Реализация программы на c++ builder 2006

 

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

Далее мы определяем для условий какой  знак будет(больше или меньше).

Создаем цикл в котором мы будем  производить  количество тестов( k=500 ).

В цикле  заполняем нашу будущую симплекс таблицу случайными числами от (60;-60).

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

Если  это условие выполняется то мы плюсуем переменную z.

По окончанию  всех тестов (k), мы выводим ответ в процентах (z*100/k) . Этот процент и будет нашей вероятностью существования решения задачи линейного программирования.

Листинг программы с комментариями предоставлен  в Приложении 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.4 Проверка работы программы

 

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

Все это  видно на рисунке 1.

 

Рисунок 1 – скриншоты работы программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

В конце  выдается процент вероятности существования  решения при заданных нами условиями.

 

 

 

 

 

 

 

 

 

Рисунок 2 – скриншот работы программы.

 

 

На рис. 2 , мы видим созданную симплекс таблицу.

Первые 3 строки это условия, последняя строка это целевая функция.

Первый  столбец это свободные члены  наших условий и целевой функции.

Последняя надпись это есть наша вероятность  существования решения задачи линейного  программирования в процентах.

 

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

Возьмем условия и целевую функцию  из нашего скриншота программы.

F = -35x₁+9x₂ → min, при системе ограничений (11):

                                    2x₁+x₂ <= 21

                                     57x₁+52x₂=>14                                                                               (11)

                                     55x₁+ 59x₂=>42

 

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

 

 

 

   График 1. – 1 пример

 

По графику  мы видим, что задача не имеет допустимых решений. ОДР представляет собой пустое множество.

 

Для проверки условия когда у нас все же есть решение, мы опять же возьмем симплекс таблицу из нашего 2ого скриншота программы.

 

F = -35x₁+9x₂ → min, при системе ограничений (12):

 

                                    38x₁+35x₂ <= 57

                                    26x₁-3x₂ => 20                                                                                  (12)

                                    18x₁+57x₂ => 22

 

 

 

 

 

График 2.- 2 пример.

 

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

 

 

 

 

 

 

 

 

 

2.5 Поиск зависимости от количества условий и переменных

 

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

Результаты  этих тестов отображаются в таблицах.

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

Во второй строке результаты, процент вероятности  существование решения ЗЛП.

 

Таблица 2.1

2х1	2х2	2х3	2х4	2х5
82.2 %	75.2 %	68.2 %	66 %	65.8 %

 

Таблица 2.2

3х1	3х2	3х3	3х4	3х5
78.6 %	64.4 %	57.6 %	54.6 %	52.6 %

 

Таблица 2.3

4х1	4х2	4х3	4х4	4х5
69.9 %	60.4 %	50.2 %	45 %	40.2 %

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1.

Листинг программы с комментариями

 

#include <iostream.h>

#include <math.h>

#include <windows.h>

#include <conio.h>

#include <stdlib.h>

 

char* Rus(const char* text);

char bufRus[256];

 

char* Rus(const char* text)

{

      CharToOem(text, bufRus);

      return bufRus;

}

 

main()

{

start: double A[100][100];

int i, j, q, s, N, M, I, J, x, yslovie, target,k=50,o=0,r=0,l,h;   // k - колличество раз прогона цикла

float t=0,z=0;

 

 

cout<<Rus("Введите количество переменных: ");

cin>>N;

cout<<Rus("Теперь введите количество условий: ");

cin>>M;

J=N+M+2; // основные переменные + добав. переменн. + свободный член + оценочные соотношения

I=M+1; // добаляем еще одну строку для целевой функции

 

 

 

 

         x=N;//переменная чтобы выставлять коэффиценты (по диагонали) 1 или -1 для добавочных переменных

for (i=0; i<I-1; i++)

{

x++;

cout<<i+1<<Rus("-е условие больше или меньше? (1/0) ");

cin>>yslovie;

//если  знак "больше", то кооф. доб. переменной поменять знак на добавочной переменной

for (j=x;j<=x; j++)

{

if (yslovie==1)

A[i][j]=-1;

else

A[i][j]=1;

}

}

 

 

 

  for (t = 1; t <= k ; t++)        // Цикл

 

  {

 

 

 

for (i=0; i<I; i++)                                // генерация случайных чисел для свободных членов

 {A[i][0]=random(90)-30;

 

  }

 

 

 

        for (i=0; i<I; i++)                                  // генерация случайных чисел для коэфициентов

{for (j=1;j<=N;j++)

   A[i][j]=random(90)-30;

}

 

for (j=1; j<=N;j++)

A[I-1][j]=-1*A[I-1][j];//меняем знак для целевой функции

 

 

 

//проверка  на возможность решения    при выборе минимума

 

l=0;                              // счетчик

for (i=0; i<I-1; i++)

{if (A[i][0]<0) {l=1; break;}}

if (l==0) {z=z+1; cout<<Rus("Решение есть"); goto end;}  // если   столбец положительный

 

 

r=0;

h=0;

for (i=0; i<I; i++)

{

   if (A[i][0]<0) {o=i; h=h+1;

 

   for (j=1;j<=N;j++)

   if (A[o][j]<0) {(r=r+1);break;}

                           }

 

                         }

  if (r==h) cout<<Rus("Решение есть"); else {cout<<Rus("Нет решениея");