90296

Формування виробничого плану випуску продукції

Курсовая

Информатика, кибернетика и программирование

В даному курсовому проекті використовується метод лінійного програмування двоїстий симплекс. Лінійне програмування – розв’язує задачі подані лінійними моделями , тобто ті, які мають лінійну цільову функцію (ЦФ) та лінійну область допустимих рішень (ОДР).

Украинкский

2015-06-02

1.36 MB

1 чел.

Міністерство освіти і науки України

Київський національний університет будівництва і архітектури

Кафедра інформаційних технологій

КУРСОВА РОБОТА

з дисципліни 

«Математичні методи дослідження операцій»

на тему:

«Формування виробничого плану випуску продукції»

Виконала студентка групи ПНК-41

Леонченко А.О.

Керівник роботи:

Бабич В. І.

Київ 2010 р.

Зміст

  1.  


Вступ

Дослідження операцій – це наука про моделі і методи оптимального управління, а також про систему прийняття рішень з допомогою оптимального управління.[1,7]

В даному курсовому проекті використовується метод лінійного програмування двоїстий симплекс.

Лінійне програмування – розв’язує задачі подані лінійними моделями , тобто ті, які мають лінійну цільову функцію (ЦФ) та лінійну область допустимих рішень (ОДР).


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

У районі лісового масиву діють лісопильний завод і фабрика, на якій виготовлюють фанеру. Щоб одержати 2,5 м3 комплектів пиломатеріалів, треба витратити l1 м3 ялинових і 1 м3 пихтових лісоматеріалів. Для готування 100 м2 фанери потрібно l2 м3 ялинових і 2 м3 пихтових лісоматеріалів. Лісовий масив містить E м3 ялинових і Р м3 пихтових лісоматеріалів. Протягом планованого періоду необхідно зробити принаймні Q1 м3 пиломатеріалів і Q2 м3 фанери. 1 м3 пиломатеріалів дає D1 грн., а 100 м2 фанери – D2 грн. прибутку

Яка кількість пиломатеріалів і фанери потрібно зробити, щоб прибуток був максимальним?

Номер варіанта

L1

ρ1

l2

ρ2

Е

P

Q1

Q2

D1

D2

3

2,6

7,5

5,1

8,5

90

200

9

1000

20

50

2. Розробка математичної моделі

- пиломатеріали (м3)

- фанера (м2)

                         


3. Вибір та обґрунтування методів рішення задачі.

Дану задачу можна вирішувати наступними методами:

  •  Двоїстий симплекс-метод (програмую)

Є ряд задач лінійного програмування, які можуть бути розв’язані тільки двоїстим симплекс-методом, наприклад деякі задачі мінімізації. Для кожної моделі існує поняття двоїстої задачі, тобто запис задачі іншими змінними для розв’язання потім іншим методом, який потрібний для перевірки правильності симплекс-методу та інших методів ЛП.

Метод базується на постійному поліпшенні умови недопустимості розв’язку. На його основі створена програма double.exe. Якщо в прямому симплекс-методі алгоритм базується на постійному покращенні значенні цільової функції, тобто значення симплекс-таблиці                        , то в ДСМ алгоритм - на постійному вилученні розв’язку, тобто всі базисні змінні в кінці xn є Bx , xn<=0, стануть позитивними.

  •  Симплекс-метод

Даний метод базується на табличних перетвореннях Джордана-Гауса моделі, поданої в канонічному вигляді. Метод симплекс-таблиць або метод переміщення по кутах (по симплексах) має в основі ітераційний розрахунок з максимально можливою кількістю ітерацій:

С=m!/n!(m-n!)

де C - максимально можлива кількість ітерацій (умова перевірки на зацикленість);

n - кількість рівнянь;

m -  кількість змінних у канонічному вигляді.

Симплекс-метод базується на постійних перетвореннях таблиці:                                        


                                                                                                              

1

2

3

...

n

Cx    Bx   A0       A1   ...   Am

               0     1     ...    m

де:  Bx  - базисні змінні;

 Cx  - коефіцієнти цільової функції при базисних змінних;

- симплекс різниця;

A1 ... Am - коефіцієнти в обмеженнях;

A0 - права частина.

Кожна ітерація полягає в заміні (перерахунку) базисної змінної.


4. Алгоритм двоїстого симплекс-методу рішення задачі та опис програми.

1. Зведення ЦФ до максимуму, а обмежень до рівностей (канонічний вигляд).

2. Запис двоїстої задачі

             

3. Побудова незалежних векторів на підставі рядків ДЗ.

   

4. Вибір спряженого базису:

  •  Довільний вибір m рівнянь;
  •  Розв’язання цієї системи m з рівнянь;
  •  Підстановка розв’язку в кожне із залишених обмежень та перевірка: чи задовольняє спряжений базис;
  •  Якщо спряжений базис задовольняє, то формування псевдолану (розрахунок симплекс-таблиці);
  •  Якщо спряжений базис не задовольняє, то треба обрати новий. Якщо на генерації нових сполучень не буде знайдено спряжений базис, то немає розв’язку.

Спряжений базис (А1А4А5А6)

5. Заповнення симплекс-таблиці.

6. Вибір направляючого елементу.

7. Всі інші симплекс-перетворення в ДСМ аналогічні прямому СМ.

                                                      

ні

 так 

                                                                              

 Рис. 1 Алгоритм двоїстого симплекс-методу


5. Ітерації програмного рішення задачі.

(

c) Leonchenko Anna .... PNK-41

Условие считывается из файла <in.txt>

Вывод выполняется в файл <out.txt>

Размерность задачи 4x6:

max(20x1+0.50x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.05x2+1.04x3+0x4+0x5+0x6=86.53

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   86.53       1    0.05    1.04       0       0       0

      0     X4  -59.60       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R  1730.60       0    0.48   20.80       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   37.53       1       0    1.04       0       0    0.05

      0     X4    2.40       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

   0.50     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R  1250.60       0       0   20.80       0       0    0.48

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= 1250.60

X = (37.53  1000  0  2.40  28.59  0  )


Опис процедур програми:

Function value – “,” міняє на “.”;

Procedure prov – Обрізання пробілів на початку та в кінці рядку;

Procedure error -  недопустимий символ;

Function ReadData – зчитування з файлу;

Function Druk – перетворює real в integer, знаходить дробову частину, перетворює число в рядок;

Procedure WriteUmovu- вивід даних зчитаних з вхідного файлу;

Procedure vivod вивід ітерацій;

Procedure RozDelta – розрахунок дельта та запис в симплекс-таблицю;

Function napr_str визначення спрямовуючого рядка;

Function napr_st визначення спрямовуючого стовпчика;

Procedure pererah – перерахунок симплекс-таблиці за формулою прямокутника;

Function simpl -  перевірка.


6. Алгоритм методу симплекс-таблиць рішення задачі.

 

1. Визначення спрямовуючого стовпчика j*

Якщо    відсутнє, то розв’язок  знайдено: базисні змінні дорівнюють, а небазисні – 0

2. Визначення спрямовуючого рядка і*

Якщо і*   відсутнє, тобто в стовпчику знаходиться значення не більше 0, то розв’язок відсутній (ОДР не обмежена зверху), інакше фіксуємо спрямовуючий елемент: (2   1)=1

3. Перерахунок таблиці (власне заміна базисних змінних):

  •  ділення значень спрямовуючого рядка на спрямовуючий елемент:

  •  обнулення спрямовуючого стовпця, крім спрямовуючого елемента:

  •  перерахунок решти значень за формулою прямокутників:

4. Перевірка ітерації:

  •  цільова функція має не зменшуватися;
  •  номер ітерації має не перевищувати їхню максимальну кількість:

  •  базисні змінні мають мати одиничний вектор;
  •  розрахунок   має співпадати як за формулою спрямовуючого стовпчика, так і за формулою «прямокутника».

Розв’язок знайдено, тому що всі     0. Після розрахунку потрібно виконати наступну перевірку:

  •  чи всі М-змінні дорівнюють 0 якщо ні, то розв’язок відсутній або ж вибрано занадто малий коефіцієнт m.
  •  Значення Z має дорівнювати значенню  Ci Xi

   Рис.2 Алгоритм симплекс-методу

Канонічна форма, розмірність 4*8


Ітерації рішення задачі вручну.

Размерность задачи НЛП - 4 х 8

max( 20X1 +0.5X2-200X6-200X8 )

{1}  1.04X1 + 0.051X2 + 1X3   = 90

{2}  3X1 + 0.085X2 + 1X4   = 200

{3}  1X1 + -1X5 + 1X6   = 9

{4}  1X2 + -1X7 + 1X8   = 1000

И  т  е  р  а  ц  и  я________1

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X3  90    1.04  0.051 1     0     0     0     0     0     

0     X4  200   3     0.085 0     1     0     0     0     0     

-200  X6  9     1     0     0     0     -1    1     0     0     

-200  X8  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   -2.0E+05 -220  -200  0     0     200   0     200   0     

=================================================================

               3->1                                            

Вводится в базис переменная Х1     вместо  Х6

И  т  е  р  а  ц  и  я________2

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X3  80.64 0     0.051 1     0     1.04  -1.04 0     0     

0     X4  173   0     0.085 0     1     3     -3    0     0     

20    X1  9     1     0     0     0     -1    1     0     0     

-200  X8  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   -2.0E+05 0     -200  0     0     -20   220   200   0     

=================================================================

                     4->2                                      

Вводится в базис переменная Х2     вместо  Х8

И  т  е  р  а  ц  и  я________3

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X3  29.64 0     0     1     0     1.04  -1.04 0.051 -0.0  

0     X4  88    0     0     0     1     3     -3    0.085 -0.0  

20    X1  9     1     0     0     0     -1    1     0     0     

0.5   X2  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   680   0     0     0     0     -20   220   -0.5  200.5

=================================================================

                                       1->5                    

Вводится в базис переменная Х5     вместо  Х3

И  т  е  р  а  ц  и  я________4

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X5  28.5  0     0     0.962 0     1     -1    0.049 -0.0  

0     X4  2.5   0     0     -2.88 1     0     0     -0.0  0.062

20    X1  37.5  1     0     0.962 0     0     0     0.049 -0.0  

0.5   X2  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   1250  0     0     19.23 0     0     200   0.481 199.5

=================================================================

Р е ш е н и е   н а й д е н о

X = ( 37.5 1000 0 2.5 28.5 0 0 0  )

Z = 1250

 

  1.  
    Висновок та дослідження на чутливість моделі.

Модифікація вхідних значень

Пошукові

xі

Цільова функція

Z

Примітка

1

Лісовий масив складається з Е=100м3

Р=250м3

L1=2,6

L2=5,1

P1=7,5

P2=8,5

E=100

P=250

Q1=9

Q2=1000

D1=20

D2=0,5

1520

Зі збільшенням площі лісового масиву  сумарний прибуток заводу збільшуються.

2

Прибуток приносять:

Пиломатеріали D1=30грн

Фанера D2=2грн

L1=2,6

L2=5,1

P1=7,5

P2=8,5

E=100

P=250

Q1=9

Q2=1000

D1=30

D2=3

3125,90

Сумарний прибуток збільшуються.

3

Якщо використовувати менше ялинових лісоматеріалів 1=2,5м3

L1=2,5

L2=5,1

P1=7,5

P2=8,5

E=100

P=250

Q1=9

Q2=1000

D1=20

D2=0,5

1830,60

Сумарний прибуток  збільшуються, так як матеріал використовується менше.

Рішення інших задач

Приклад№1

Вхідний файл:

4 6

20 0.5 0 0 0 0

1 0.049 1.04 0 0 0 = 100

0 -0.062 -3.12 1 0 0 = -40

0 0.049 1.04 0 1 0 = 77.59

0 -1 0 0 0 1 = -1000

Вихідний файл:

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <in1.txt>

Vivid vukon v file <out1.txt>

Rozmirnist zadachi 4x6:

max(20x1+0.50x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.05x2+1.04x3+0x4+0x5+0x6=100

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-40

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1     100       1    0.05    1.04       0       0       0

      0     X4     -40       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R     2000       0    0.48   20.80       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1      51       1       0    1.04       0       0    0.05

      0     X4      22       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

   0.50     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R     1520       0       0   20.80       0       0    0.48

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z=    1520

X = (51  1000  0  22  28.59  0  )

Приклад№2

Вхідний файл:

4 6

30 2 0 0 0 0

1 0.049 1.04 0 0 0 = 86.53

0 -0.062 -3.12 1 0 0 = -59.6

0 0.049 1.04 0 1 0 = 77.59

0 -1 0 0 0 1 = -1000

Вихідний файл:

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <in2.txt>

Vivid vukon v file <out2.txt>

Rozmirnist zadachi 4x6:

max(30x1+2x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.05x2+1.04x3+0x4+0x5+0x6=86.53

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  30       2       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     30     X1   86.53       1    0.05    1.04       0       0       0

      0     X4  -59.60       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R  2595.90       0   -0.53   31.20       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  30       2       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     30     X1   37.53       1       0    1.04       0       0    0.05

      0     X4    2.40       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

      2     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R  3125.90       0       0   31.20       0       0   -0.53

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= 3125.90

X = (37.53  1000  0  2.40  28.59  0  )

Приклад№3

Вхідний файл:

4 6

20 0.5 0 0 0 0

1 0.02 1.04 0 0 0 = 86.53

0 -0.062 -3.12 1 0 0 = -59.6

0 0.049 1.04 0 1 0 = 77.59

0 -1 0 0 0 1 = -1000

Вихідний файл:

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <in4.txt>

Vivid vukon v file <out4.txt>

Rozmirnist zadachi 4x6:

max(20x1+0.50x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.02x2+1.04x3+0x4+0x5+0x6=86.53

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   86.53       1    0.02    1.04       0       0       0

      0     X4  -59.60       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R  1730.60       0   -0.10   20.80       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   66.53       1       0    1.04       0       0    0.02

      0     X4    2.40       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

   0.50     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R  1830.60       0       0   20.80       0       0   -0.10

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= 1830.60

X = (66.53  1000  0  2.40  28.59  0  )

8.Дослідження розробленої програми для великих розмірностей

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <dat2.txt>

Vivid vukon v file <vvv.txt>

Rozmirnist zadachi 5x11:

max(-17x1-20x2-22x3-25x4-28x5-30x6+0x7+0x8+0x9+0x10+0x11)

{1}  -33x1+0x2-43x3+0x4-60x5+0x6+1x7+0x8+0x9+0x10+0x11=-1050

{2}  0x1-28x2+0x3-40x4+0x5-50x6+0x7+1x8+0x9+0x10+0x11=-600

{3}  1x1+1x2+0x3+0x4+0x5+0x6+0x7+0x8+1x9+0x10+0x11=5

{4}  0x1+0x2+1x3+1x4+0x5+0x6+0x7+0x8+0x9+1x10+0x11=15

{5}  0x1+0x2+0x3+0x4+1x5+1x6+0x7+0x8+0x9+0x10+1x11=15

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

      0     X7   -1050     -33       0     -43       0     -60       0       1       0       0       0       0

      0     X8    -600       0     -28       0     -40       0     -50       0       1       0       0       0

      0     X9       5       1       1       0       0       0       0       0       0       1       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11      15       0       0       0       0       1       1       0       0       0       0       1

------------------------------------------------------------------

R        0      17      20      22      25      28      30       0       0       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1   31.82       1       0    1.30       0    1.82       0   -0.03       0       0       0       0

      0     X8    -600       0     -28       0     -40       0     -50       0       1       0       0       0

      0     X9  -26.82       0       1   -1.30       0   -1.82       0    0.03       0       1       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11      15       0       0       0       0       1       1       0       0       0       0       1

------------------------------------------------------------------

R  -540.91       0      20   -0.15      25   -2.91      30    0.52       0       0       0       0

-------------------------------------------------------------------

Iteracija #   3

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1   31.82       1       0    1.30       0    1.82       0   -0.03       0       0       0       0

    -20     X2   21.43       0       1       0    1.43       0    1.79       0   -0.04       0       0       0

      0     X9  -48.25       0       0   -1.30   -1.43   -1.82   -1.79    0.03    0.04       1       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11      15       0       0       0       0       1       1       0       0       0       0       1

------------------------------------------------------------------

R  -969.48       0       0   -0.15   -3.57   -2.91   -5.71    0.52    0.71       0       0       0

-------------------------------------------------------------------

Iteracija #   4

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1   31.82       1       0    1.30       0    1.82       0   -0.03       0       0       0       0

    -20     X2  -26.82       0       1   -1.30       0   -1.82       0    0.03       0       1       0       0

    -30     X6   27.02       0       0    0.73    0.80    1.02       1   -0.02   -0.02   -0.56       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11  -12.02       0       0   -0.73   -0.80   -0.02       0    0.02    0.02    0.56       0       1

------------------------------------------------------------------

R  -815.09       0       0    4.02    1.00    2.91       0    0.42    0.60   -3.20       0       0

-------------------------------------------------------------------

Iteracija #   5

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1    5.00       1       1       0       0       0       0       0       0       1       0       0

    -22     X3   20.58       0   -0.77       1       0    1.40       0   -0.02       0   -0.77       0       0

    -30     X6   12.00       0    0.56       0    0.80       0       1       0   -0.02       0       0       0

      0     X10   -5.58       0    0.77       0       1   -1.40       0    0.02       0    0.77       1       0

      0     X11    3.00       0   -0.56       0   -0.80       1       0       0    0.02       0       0       1

------------------------------------------------------------------

R  -897.79       0    3.08       0    1.00   -2.70       0    0.51    0.60   -0.12       0       0

-------------------------------------------------------------------

Iteracija #   6

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1    5.00       1       1       0       0       0       0       0       0       1       0       0

    -22     X3      15       0       0       1       1       0       0       0       0       0       1       0

    -30     X6   12.00       0    0.56       0    0.80       0       1       0   -0.02       0       0       0

    -28     X5    4.00       0   -0.55       0   -0.72       1       0   -0.02       0   -0.55   -0.72       0

      0     X11   -1.00       0   -0.01       0   -0.08       0       0    0.02    0.02    0.55    0.72       1

------------------------------------------------------------------

R  -887.00       0    1.60       0   -0.93       0       0    0.47    0.60   -1.60   -1.93       0

-------------------------------------------------------------------

Iteracija #   7

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1  -95.00       1       0       0   -8.33       0       0    1.67    2.00   56.00   71.67   100.00

    -22     X3      15       0       0       1       1       0       0       0       0       0       1       0

    -30     X6  -44.00       0       0       0   -3.87       0       1    0.93    1.10   30.80   40.13   56.00

    -28     X5   59.00       0       0       0    3.87       1       0   -0.93   -1.10  -30.80  -40.13  -55.00

    -20     X2   100.00       0       1       0    8.33       0       0   -1.67   -2.00  -55.00  -71.67  -100.00

------------------------------------------------------------------

R -1047.00       0       0       0  -14.27       0       0    3.13    3.80   86.40  112.73  160.00

-------------------------------------------------------------------

Iteracija #   8

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -25     X4   11.40   -0.12       0       0       1       0       0   -0.20   -0.24   -6.72   -8.60  -12.00

    -22     X3    3.60    0.12       0       1       0       0       0    0.20    0.24    6.72    9.60   12.00

    -30     X6    0.08   -0.46       0       0       0       0       1    0.16    0.17    4.82    6.88    9.60

    -28     X5   14.92    0.46       0       0       0       1       0   -0.16   -0.17   -4.82   -6.88   -8.60

    -20     X2       5       1       1       0       0       0       0       0       0       1       0       0

------------------------------------------------------------------

R  -884.36   -1.71       0       0       0       0       0    0.28    0.38   -9.47   -9.96  -11.20

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= -884.36

X = (0  5  3.60  11.40  14.92  0.08  0  0  0  0  0  )

Найбільша розмірність, яка може бути вирішена даним програмним продуктом складає матрицю розміром 50*50.


Список використаної літератури

1. Бабич В. І.  Конспект лекцій з дисципліни «Математичні методи дослідження операцій»

2. Культин Н. Б.  Программирование в Turbo Pascal 7.0 – Спб.: БХВ – Санкт-Петербург, 1999 – 240 с.

 


Додаток

Лістинг програми

program simplex;

uses crt;

const

 nmax=50;

 mmax=50;

var

 sub, file_input, file_output, iter, zn_max: string;

 it, res,fl: boolean;

 ind, k, n, m, j0, i0, i, j,nom_it: integer;

 c: array [1..mmax] of real;

 a: array [1..nmax,0..mmax] of real;

 b: array [1..nmax] of byte;

 d: array [0..mmax] of real;

 znak: array [1..nmax] of char;

 key: char;

{ x: array [1..mmax] of real; }

function value(var s: string): string;

var

 v: string;

 i: integer;

begin

 v:='';

 repeat

   if s[1]=',' then v:=v+'.' else v:=v+s[1];

   delete(s,1,1);

 until (s[1]=' ') or (s='');

 value:=v;

end;

procedure prov(var s: string);

begin

 if s[1]=' ' then

   repeat

     delete(s,1,1);

   until s[1]<>' ';

 if s[length(s)]=' ' then

   repeat

     delete(s,length(s),1);

   until s[length(s)]<>' ';

end;

procedure error(sub: string);

begin

 write('Недопустимий символ ');

 for i:=1 to length(sub) do

   case sub[i] of

     'A'..'Z','a'..'z': write('Буква  ');

     '0'..'9',',','.':;

   else write('спеціальний символ ');

   end;

 writeln;

end;

function ReadData: boolean;

var

 s: string;

 code, i, j: integer;

begin

 readdata:=true;

 assign(input,file_input);

 reset(input);

 if ioresult<>0 then

 begin

   writeln('Файл'<+file_input+'>не найдено');

   halt;

 end;

 readln(s);

 prov(s);

 sub:=value(s);

 val(sub, n, code);

 if code<>0 then

 begin

   writeln('Помилка: рядок 1-й число 1-ше ');

   readdata:=false;

   error(sub);

 end;

 prov(s);

 sub:=value(s);

 val(sub, m, code);

 if code<>0 then

 begin

   writeln(' Помилка: рядок 1-й число 2-ге ');

   readdata:=false;

   error(sub);

 end;

 if (n>nmax) or (m>mmax) then begin

   writeln('Указана розмірність задачі не підходить обмеженням задачі');

   readdata:=false;

 end;

 readln(s);

 prov(s);

 for j:=1 to m do

 begin

   sub:=value(s);

   val(sub, c[j], code);

   if code<>0 then

   begin

     writeln(Помилка: рядок 2-й' , j, 'число);

     readdata:=false;

     error(sub);

   end;

   prov(s);

 end;

 zn_max:=value(s);

 for i:=1 to n do

 begin

   readln(s);

   prov(s);

   for j:=1 to m do

   begin

     sub:=value(s);

     val(sub,a[i,j],code);

     if code<>0 then

     begin

       writeln('Помилка: рядок',i+2,'-число ',j,');

       readdata:=false;

       error(sub);

     end;

     prov(s);

   end;

   znak[i]:=s[1];

   delete(s,1,1);

   if (znak[1]<>'>') and (znak[1]<>'<') and (znak[1]<>'=') then begin

     writeln('Ошибка: рядок  ',i+2,'- й: не вірно вказаний знак');

     readdata:=false;

   end;

   prov(s);

   sub:=value(s);

   val(sub,a[i,0], code);

   if code<>0 then

   begin

     writeln('Ошибка: рядок ',i+2,'- й',m+1,'оє:');

     readdata:=false;

     error(sub);

   end;

 end;

end;

procedure kanon;

var

 max: real;

begin

 max:=1;

 for i:=1 to m do

   if max<c[i] then max:=c[i];

 max:=10*max;

 if (length(zn_max)=3) and ((zn_max[2]='I') or (zn_max[2]='i')) and ((zn_max[3]='N') or (zn_max[3]='n')) then

   for i:=1 to m do

     c[i]:=-c[i];

 repeat

 for i:=1 to n do

   if a[i,0]<0 then

   begin

     for j:=0 to m do

       a[i,j]:=-a[i,j];

     res:=false;

     case znak[i] of

       '>': znak[i]:='<';

       '<': znak[i]:='>';

     end;

     break;

   end

   else if (a[i,0]=0) and (znak[i]='<') then

   begin

     for j:=1 to m do

       a[i,j]:=-a[i,j];

     znak[i]:='>';

     res:=false;

     break;

   end

   else

   begin

     case znak[i] of

       '>': begin

         inc(m);

         c[m]:=0;

         a[i,m]:=-1;

         for j:=1 to n do

           if i<>j then

             a[j,m]:=0;

       end;

       '<':begin

         inc(m);

         c[m]:=0;

         a[i,m]:=1;

         for j:=1 to n do

           if i<>j then

             a[j,m]:=0;

       end;

       '=':begin

         inc(m);

         c[m]:=0;

         a[i,m]:=1;

         for j:=1 to n do

           if i<>j then

             a[j,m]:=0;

       end;

     end;

     res:=true;

     znak[i]:='^';

   end;

 until (res=true);

end;

function druk(b: real; im: boolean): string;

var

 s, s1: string;

 cel, i, j: integer;

begin

 s:='';

 cel:=trunc(b);

 i:=1;

 if b<0 then

 begin

   inc(i);

   cel:=abs(cel);

 end;

 while cel div 10 >0 do

 begin

   cel:=cel div 10;

   inc(i);

 end;

 if frac(b)<>0 then

 begin

   i:=i+3;

   str(b:4:2,s);

 end

 else  str(trunc(b), s);

 if im then

 begin

   i:=8-i;

   s1:='';

   for j:=1 to i do

     s1:=s1+' ';

   s:=s1+s;

 end;

 druk:=s;

end;

procedure vivod;

var i,j:integer;

begin

writeln('Iteracija #',nom_it:4);

writeln('--------------------------------------------------------------------');

writeln('--------------------------------------------------------------------');

write('Cil. funk            ');

for i:=1 to m do

write(druk(c[i],true));

writeln('');

write('------------------------------------------------------------------');

writeln('');

 write('             Bx ');

 for j:=0 to m do

 write('    A',j,'   ');

 writeln('');

 for i:=1 to n do

 begin

 write(druk(c[b[i]],true));

 write('     X',b[i]);

 write(druk(a[i,0],true));

 for j:=1 to m do

  write(druk(a[i,j],true));

  writeln(' ');

 end;

 writeln('------------------------------------------------------------------');

 write('R ');

 for i:=0 to m do

 write(druk(d[i],true));

 writeln(' ');

 writeln('-------------------------------------------------------------------');

 writeln('');

 nom_it:=nom_it+1;

end;

procedure WriteUmovu;

var

 i, j: integer;

begin

 clrscr;

 writeln('(c) Leonchenko Anna .... PNK-41');

 writeln;

 writeln('File dlja zchityvannja <'+file_input+'>');

 if file_output='con' then

   writeln('Vivid vukon na ekran')

 else writeln('Vivid vukon v file <'+file_output+'>');

 Writeln('Rozmirnist zadachi ', n, 'x', m, ':');

 writeln;

 write('max(');

 for j:=1 to m do

   if (c[j+1]>=0) and (j<>m) then write(druk(c[j],false),'x', j,'+')

     else write(druk(c[j],false),'x',j);

 writeln(')');

 for i:=1 to n do

 begin

   write('{',i,'}  ');

   for j:=1 to m do

   begin

     write(druk(a[i,j],false),'x',j);

     if (a[i,j+1]>=0) and (j<>m) then write('+');

   end;

   writeln('=',druk(a[i,0],false));

 end;

 if file_output='con' then

   repeat

     key:=readkey

   until key=#13;

end;

procedure RozDelta; {rozraxynok delta}

var

 i, j, k: integer;

 pr: boolean;

begin

 for i:=1 to n do     {zapisyemo ne 0 elementu}

   for j:=1 to m do

     if a[i,j]=1 then

     begin

       pr:=false;

       for k:=1 to n do

         if (i<>k) then

           if (a[k,j]=0) then pr:=true

           else begin pr:=false; break; end;

       if pr then

       begin b[i]:=j; break; end;

     end;

 for j:=0 to m do {podchet delta}

 begin

   if j=0 then d[j]:=0 else d[j]:=-c[j];

   for i:=1 to n do

     d[j]:=d[j]+a[i,j]*c[b[i]];

 end;

end;

function napr_str(var i0: integer): boolean; {vuznachennja napr-j stroku}

var

 value1: real;

 i: integer;

begin

 napr_str:=false;

 value1:=0;

 i0:=0;

 for i:=1 to n do

   if (a[i,0]<value1) then

   begin

     value1:=a[i,0];

     i0:=i; {nomer napr-j stroku}

     napr_str:=true;

   end;

end;

function napr_st(i0: integer; var j0: integer): boolean; {viznachennja napr-go stovbchika}

var

 value1: real;

 j: integer;

begin

 napr_st:=false;

 value1:=0;

 j0:=0;

 for j:=1 to m do

   if (a[i0,j]<0) and (abs(d[j]/a[i0,j])>value1) then

   begin

     value1:=abs(d[j]/(a[i0,j]));

     j0:=j; {zapusyemo nomer stovbchika}

     napr_st:=true;

   end;

end;

procedure pererah; {pererahovyemo matrucy}

var

 i, j: integer;

begin

 for j:=0 to m do

 if j<>j0 then

 begin

   for i:=1 to n do

     if i<>i0 then

     a[i,j]:=a[i,j]-(a[i0,j]*a[i,j0]/a[i0,j0]);

   d[j]:=d[j]-(a[i0,j]*d[j0]/a[i0,j0]);

 end;

 for j:=0 to m do

   if j<>j0 then a[i0,j]:=a[i0,j]/a[i0,j0]; {rozrahynok napr. stoku}

 for i:=1 to n do

   if i<>i0 then a[i,j0]:=0; {rozrahynok napr. stovb.}

 d[j0]:=0;

 a[i0,j0]:=1;

 b[i0]:=j0; {zapis nomera stovb.}

end;

function simpl: boolean; {}

begin

 simpl:=true;

 while napr_str(i0) do

   if napr_st(i0,j0) then

    begin

     Pererah;

     vivod;

    end

   else

   begin

     simpl:=false;

     break;

   end;

end;

BEGIN

 {file_input:='in.txt';

 file_output:='out.txt';

 it:=true;  }

 file_input:=paramstr(1);

 file_output:=paramstr(2);

 iter:=paramstr(3);

 readkey;

 if (file_input='') or (file_output='') then

 begin

   writeln('Vvedit pravilno dani');

   writeln('DUOSIMPL.exe inputfile outputfile/con [Y/y]');

   exit;

 end;

 if (iter='Y') or (iter='y') then it:=true;

 if file_output<>'con' then

 begin

   assign(output,file_output);

   rewrite(output);

 end;

 res:=true;

 if not ReadData then halt;

 {Kanon; }

 writeln;

 WriteUmovu;

 writeln;

 RozDelta;

 nom_it:=1;

 vivod;

 if not simpl then {nema rishennja}

 begin

   writeln('Rishen nemaje');

   halt;

 end

 else

 begin

 writeln('Rishennja znajdeno!!! Param-pam-pam');

 writeln('Z=',druk(d[0],true));

 write('X = (');

 for i:=1 to m do

 begin

 fl:=false;

 for j:=1 to m do

 if b[j]=i then begin write(druk(a[j,0],false),'  '); fl:=true; end;

 if fl=false then write('0  ');

 end;

 writeln(')');

 end

END.


 

А также другие работы, которые могут Вас заинтересовать

36244. Системы искусственного интеллекта. Понятия и определения. Архитектура, классификация моделей 38 KB
  В этой информационной модели окружающей среды реальные объекты их свойства и отношения между ними не только отображаются и запоминаются но и как это отмечено в данном определении интеллекта могут мысленно целенаправленно преобразовываться . При этом существенно то что формирование модели внешней среды происходит в процессе обучения на опыте и адаптации к разнообразным обстоятельствам . Под структурным подходом мы подразумеваем попытки построения ИИ путем моделирования структуры человеческого мозга. Основной моделируемой структурной...
36245. Распознавание образов: подходы 36 KB
  Ассоциативность памяти и задача распознавания образов Динамический процесс последовательной смены состояний нейронной сети Хопфилда завершается в некотором стационарном состоянии являющемся локальным минимумом энергетической функции ES. Невозрастание энергии в процессе динамики приводит к выбору такого локального минимума S в бассейн притяжения которого попадает начальное состояние исходный пред'являемый сети образ S0. Поскольку для двух двоичных векторов минимальное число изменений компонент переводящее один вектор в другой является...
36246. Персептрон Розенблатта: структура, алгоритм обучения 52 KB
  Персептрон Розенблатта: структура алгоритм обучения. С сегодняшних позиций однослойный персептрон представляет скорее исторический интерес однако на его примере могут быть изучены основные понятия и простые алгоритмы обучения нейронных сетей.Розенблаттом метод обучения состоит в итерационной подстройке матрицы весов последовательно уменьшающей ошибку в выходных векторах. Здесь темп обучения.
36247. Генети́ческий алгори́тм 57.5 KB
  Некоторым обычно случайным образом создаётся множество генотипов начальной популяции. Таким образом можно выделить следующие этапы генетического алгоритма: Задать целевую функцию приспособленности для особей популяции Создать начальную популяцию Начало цикла Размножение скрещивание Мутирование Вычислить значение целевой функции для всех особей Формирование нового поколения селекция Если выполняются условия останова то конец цикла иначе начало цикла. Создание начальной популяции Перед первым шагом нужно...
36248. Программные агенты: классификация, структура. Многоагентные системы 43.5 KB
  Классификация агентов. Классификация агентов типы агентов Простые Смышленые Интеллектуальные характеристики Автономное выполнение Взаимодействие с другими агентами и пользователями Слежение за окружением Способность использования абстракций Способность использования предметных знаний Возможность адаптивного поведения для достижения цели Обучение из окружения Терпимость к ошибкам Rel time исполнение ER взаимодействие С позиции изучаемой дисциплины нас прежде всего...
36249. Экспертные системы: виды, структура, этапы построения 119 KB
  При разработке ЭС определяются основные ресурсы к которым относятся: источники знаний время разработки вычислительные средства объем финансирования. Этап завершается созданием модели предметной области и определением следующих задач: типов доступных данных; исходные и выходные данные; используемые стратегии и гипотезы; типы используемых отношений; состав знаний используемых для решения задачи; состав знаний используемых для обоснованного решения. В ходе данного этапа производится оценка выбранного способа представление...
36250. Ресурсы. Свойства и классификация ресурсов. Дисциплины распределения ресурсов 79 KB
  Понятие ресурса. Ресурсы различаются по запасу выделяемых единиц ресурса и бывают в этом смысле исчерпываемые и неисчерпываемые. Исчерпываемость ресурса как правило приводит к жизненным конфликтам в среде потребителей Для регулирования конфликтов ресурсы должны распределяться между потребителями по какимто правилам в наибольшей степени их удовлетворяющим. Именно в этом смысле далее и трактуется понятие ресурса.
36251. Процессы. Задачи синхронизации. Задача взаимного исключения, задача Производитель-потребитель, задача Читатели-писатели 51 KB
  На уровень долгосрочного планирования выносят действия редкие в системе, но требующие больших системных затрат. На уровень краткосрочного планирования выносятся частые и более короткие по длительности действия по управлению процессами.
36252. Аппаратная реализация взаимоисключения: команда test and set. Семафоры. Обеспечение взаимоисключения при помощи семафоров 50 KB
  Главным фактором, обеспечивающим успех в этом случае, является наличие одной аппаратной команды, которая осуществляет чтение переменной, запись ее значения в область сохранения и установку нужного конкретного значения этой переменной