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.


 

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

55258. Найважливіші принципи розміщення продуктивних сил, їх значення для ефективного розміщення підприємств і галузей 24.31 KB
  Принцип розміщення підприємств згідно з раціональними формами суспільної організації виробництва. До таких форм належать концентрація, спеціалізація, кооперування й комбінування.
55260. Природно-ресурсний потенціал, його структура. Забезпеченість України природними ресурсами 25.81 KB
  Природно-ресурсний потенціал території – цілісна система складноорганізованих обєктів, цілісність якого визначається закономірним сполученням взаємозумовлених природних і соціально-економічних звязків і залежностей, що поєднують територіально всі природні ресурси
55261. Презентация фрагментов работы учащихся 7-го класса по созданию учебного проекта «Построение средневекового города в Киевской Руси и Британии» (в рамках «global simulation») 58 KB
  Смещается акцент с фронтальной на групповую парную и самостоятельную работу результат выводится на продуктивный уровень обеспечивается развивающий потенциал уроков наряду с познавательной активностью и в довершении способствует формированию навыков командной работы. Тема: Презентация фрагментов работы учащихся 7го класса по созданию учебного проекта Построение средневекового города в Киевской Руси и Британии в рамках globl simultion Тип урока: интегрированный с использованием билингвальных технологий. Цели урока: представить...
55263. Основні фактори розміщення продуктивних сил, їх вплив на розміщення виробництва 25.69 KB
  Фактори розміщення це реалізація закономірностей і принципів при врахуванні конкретних умов, що впливають на вибір місць розташування промислових підприємств і формування територіально-виробничих комплексів.
55264. Поняття компютерної презентації. Основне призначення системи підготовки презентації 68.5 KB
  Мета уроку: навчальна: отримати уявлення про мультимедіа, познайомитися з програмою для створення мультимедійних презентацій; навчитися технології створення і демонстрації електронних презентацій; розвиваюча: розвиток мислення, пізнавальних інтересів, навиків роботи на компютері, роботи з мультимедійними програмними засобами...
55265. Чисельність населення України, особливості його динаміки. Природний рух населення. Демографічна ситуація в Україні, основні шляхи її розв’язання 25.61 KB
  Демографічні передумови є найважливішою складовою розміщення продуктивних сил. Населення країни фактор її комплексного економічного та соціального розвитку. Населення це трудові ресурси і споживач, яке впливає на формування міжрайонних функцій виробництва, потужність і структуру потоку продукції, що вивозиться за межі певної території, розвиток місцевого виробництва.
55266. Комп’ютерна презентація 107.5 KB
  Мета: 1) ввести поняття “презентація”, навчити учнів проектувати презентації, ознайомити з програмою Power Point та її можливостями. З’ясувати призначення комп’ютерної презентації. 2) розвивати алгоритмічне та логічне мислення, вміння порівнювати, виділяти головне, роботи узагальнення і висновки. Розвивати пізнавальну, комунікативну та інформаційну компетентності.