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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне агентство з освіти РФ

Федеральне державне освітній заклад

Середньої професійної освіти

Барнаульський будівельний коледж

Курсова робота.

З дисципліни: «Математичні методи»

На тему: «Рішення задач лінійного програмування симплекс методом»

Виконав: Нунгесер М.В.

Спеціальність: ПОВТ

Група: 0881

Викладач: Клепікова М.М.

Барнаул 2010



Зміст:

Введення

Лінійне програмування

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

Постановка завдання

Розробка алгоритму

Рішення завдання

Програмна реалізація на мові Delphi

Додаток

Висновок

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

Введення

В останні роки в прикладній математиці велика увага приділяється новому класу задач оптимізації, які полягають у знаходженні в заданій області точок найбільшого або найменшого значення певної функції, що залежить від великого числа змінних. Це так звані завдання математичного програмування, що виникають у найрізноманітніших галузях людської діяльності і перш за все в економічних дослідженнях, в практиці планування і організації виробництва. Вивчення цього кола завдань і методів їх вирішення призвело до створення нової наукової дисципліни, що отримала пізніше назву лінійного програмування. В кінці 40-х років американським математиком Дж. Данцигом був розроблений ефективний метод вирішення даного класу завдань - симплекс-метод. До завдань, що вирішуються цим методом у межах математичного програмування належать такі типові економічні завдання як «Визначення найкращого складу суміші», «Завдання про оптимальний плані випуску продукції», «Оптимізація міжгалузевих потоків», «Завдання про вибір виробничої програми», «Транспортна задача» , «Завдання розміщення», «Модель Неймана розширюється економіки» та інші. Вирішення таких завдань дає великі вигоди як народному господарству в цілому, так і окремих його галузях.

Рішення задач математичного програмування за допомогою симплекс-методу традиційними способами вимагає витрат великої кількості часу. У зв'язку з бурхливим розвитком комп'ютерної техніки в останні десятиліття природно було очікувати, що обчислювальна потужність сучасних ЕОМ буде застосована для вирішення зазначеного кола завдань.



Лінійне програмування

Лінійне програмування - математична дисципліна, присвячена теорії та методів розв'язання задач про екстремуму лінійних функцій на множинах n-мірного векторного простору, що задаються системами лінійних рівнянь і нерівностей.

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

Багато властивостей задач лінійного програмування можна інтерпретувати також як властивості многогранників і таким чином геометрично формулювати і доводити їх.

Математичне формулювання задачі лінійного програмування

Потрібно визначити максимум лінійної цільової функції (лінійної форми)

за умов


Іноді на x i також накладається деякий набір обмежень у вигляді рівностей, але від них можна позбутися, послідовно висловлюючи одну змінну через інші і підставляючи її в усіх інших равенствах і нерівностях (а також у функції f).

Таке завдання називають «основний» або «стандартної» в лінійному програмуванні. Найбільш відомим і широко застосовуваним на практиці для вирішення загальної задачі лінійного програмування (ЛП) є симплекс метод.

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

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

Застосування симплекс-методу для задачі лінійного програмування передбачає попереднє приведення її формальної постановки до канонічної форми з n невід'ємними змінними: (X 1, ..., X n), де потрібно мінімізація лінійної цільової функції при m лінійних обмеженнях типу рівностей. Серед змінних завдання вибирається початковий базис з m змінних, для визначеності (X 1, ..., X m), які повинні мати невід'ємні значення, коли решта (nm) вільні змінні рівні 0. Цільова функція та обмеження рівності перетворяться до діагональної формі щодо базисних змінних, змінних, де кожна базисна змінна входить лише в одне рівняння з коефіцієнтом 1.

Дана формальна модель задачі лінійного програмування зазвичай задається у формі, так званої симплекс-таблиці, зручної для виконання операцій симплекс-методу:

Симплекс-таблиця


1

X 1

X 2

...

X m

X m +1

...

X n

X 0

A 0,0

0

0

...

0

A 0, m +1

...

A 0, n

X 1

A 1,0

1

0

...

0

A 1, m +1

...

A 1, n

X 2

A 2,0

0

1

...

0

A 2, m +1

...

A 2, n

...

...

...

...

...

...

...

...

...

X m

A m, 0

0

0

...

1

A m, m +1

...

A m, n

Верхній рядок симплекс-таблиці представляє цільову функцію завдання. Кожен рядок симплекс-таблиці, крім першої, відповідає певному обмеженню-рівності завдання. Вільні члени обмежень складають крайній лівий стовпець таблиці. Зліва від таблиці записані поточні базисні змінні (X 1, ..., X m). Зверху від таблиці наведено набір всіх змінних задачі, де X m +1, ..., X n - вільні змінні завдання.

На початковому кроці алгоритму симплекс-методу має бути вибрано базисне допустиме рішення (X 1, ..., X m)> = 0 при X j = 0 (j = m +1, ..., n), отже, всі вільні члени обмежень A i, 0> = 0 (i = 1, ..., m). Коли ця умова виконана, симплекс-таблиця називається прямо-допустимої, тому що в цьому випадку базисні змінні, рівні A i, 0, визначають дозволене рішення прямої задачі лінійного програмування. Якщо всі коефіцієнти цільової функції A 0, j> = 0 (j = 1, ..., m), то симплекс-таблиця називається двояко-допустимої, оскільки відповідне рішення є допустимим для двоїстої задачі лінійного програмування.

Якщо симплекс-таблиця є одночасно прямо і двояко допустимої, тобто одночасно всі A i, 0> = 0 і A 0, j> = 0, то рішення оптимально.

Дійсно, оскільки допустимими є лише невід'ємні значення керованих параметрів, то зміна цільової функції за рахунок варіації вільних змінних, через які вона виражена, можливо тільки в бік збільшення, тобто, буде погіршуватися. Якщо серед її коефіцієнтів є A 0, j <0, то значення цільової функції ще можна зменшити (т.e. поліпшити), збільшуючи значення будь-якої вільної змінної X j з негативним коефіцієнтом A 0, j при побічну зменшенні базисних змінних, щоб залишалися справедливі обмеження завдання. Теоретично можна використовувати будь-яку вільну змінну X j з A 0, j <0, але на практиці зазвичай діють у відповідності зі стратегією найшвидшого спуску, вибираючи мінімальний елемент A 0, p <0 з усіх негативних A 0, j <& nbsp0:

A 0, p = min A 0, j <0.

j

Стовпець p симплекс-таблиці, що відповідає обраному коефіцієнту A 0, p <0, називається провідним стовпцем. Вільна мінлива ведучого шпальти повинна бути введена в базис замість однієї з поточних базисних змінних. Очевидно, з базису слід виключити таку змінну X q, яка раніше інших звертається в нуль при збільшенні змінної X p ведучого шпальти.

Її індекс легко визначити, якщо серед позитивних елементів ведучого шпальти p знайти елемент, здатний мінімізувати відношення (A i, 0 / A i, p):

A q, 0 A i, 0

------ = Min ------, i = 1 ,..., m.

A q, p i A i, p



Елемент A q, p називається провідним елементом, c Троках q симплекс-таблиці, що містить ведучий елемент, називається, відповідно, провідною рядком. Змінна провідною рядки X q замінюється в базисі змінної ведучого шпальти X p і стає вільною змінної з значенням 0, у той час як нова базисна змінна X p досягне максимально можливого значення, рівного: max X p = (A q, 0 / A q, p).

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

  • множення рівняння E 1 (X) = 0 на константу K 1 і заміна рівняння E 1 (X) = 0 рівнянням K 1 * E 1 (X) = 0;

  • складання рівнянь E 1 (X) = 0 і E 2 (X) = 0 c наступною заміною рівняння E 2 (X) = 0 рівнянням E 1 (X) + E 2 (X) = 0.

Винятки Гауса дозволяють привести систему рівнянь до діагональної формі щодо бажаного безлічі змінних. У даному випадку виключення Гауса застосовується так, щоб всі елементи симплекс-таблиці у провідному стовпці, крім ведучого елемента A q, p, стали нульовими, а ведучий елемент став рівним одиниці:

A i, p = 0, якщо i не дорівнює q

і

A i, p = 1, якщо i = q.

Зазначені кроки симплекс-методу повторюються, поки не буде отримана симплекс-таблиця, яка одночасно є прямо і двояко допустимої. Якщо покладе в такій симплекс-таблиці поточні базисні змінні рівними A i, 0, а вільні - нулю, то буде отримано оптимальне рішення.

Практика застосування симплекс методу показала, що кількість ітерацій, необхідних для вирішення задачі лінійного програмування зазвичай коливається від 2m до 3m, хоча для деяких спеціально побудованих завдань обчислення за правилами симплекс методу перетворюються на прямий перебір базисних допустимих рішень. Проте, важкі для симплекс методу завдання на практиці зустрічаються украй рідко, що пояснює широке розповсюдження і більшу популярність даного методу лінійного програмування в порівнянні з іншими підходами.

Постановка завдання

На звірофермі можуть вирощуватися норки, видри і нутрії. Для забезпечення нормальних умов їх вирощування використовується 3 види кормів. Кількість корму кожного виду, яке повинні отримувати звіри в середньому наведено в таблиці:


Кількість одиниць корму, яке щодня повинні отримувати


Вид корму

Норка

Видра

Нутрія

Загальна кількість корму

I

4

2

5

190

II

5

3

4

320

III

7

9

5

454

Прибуток від реалізації однієї шкурки, руб.

150

320

350



У таблиці вказана загальна кількість корму кожного виду, яке може бути використане звіроферми, і прибуток від реалізації однієї шкурки звірка.

Визначити, скільки звірків кожного виду слід вирощувати на звірофермі, щоб прибуток від реалізації шкурок була максимальною.

Алгоритм розв'язання задач симплекс - методом

  1. Поставлена ​​описова завдання переводиться в математичну форму (цільова функція та обмеження).

  2. Отримане математичний опис призводять до канонічної форми.

  3. Канонічну форму призводять до матричному увазі.

  4. Шукають перший допустиме рішення. Для цього матриця повинна бути правильною. Матриця в ЗЛП називається правильною, якщо вона містить мінімум m правильних (базисних) стовпців, де m - число рядків в матриці. Стовпець у канонічній ЗЛП називається правильним (базисним), якщо всі його елементи дорівнюють нулю, крім єдиного рівного одиниці.

  5. Якщо матриця не є правильною, то її потрібно зробити такої з допомогою штучного базису. Для цього в матрицю потрібно дописати стільки базисних стовпців, щоб їх загальна кількість разом з уже наявними базисними стовпцями становило m. Після цього переходять до пункту 6. Якщо штучний стовпець виходить з базису, то його видаляють з матриці. Якщо вилучені всі штучні стовпці, то отримано перше допустиме рішення. Якщо штучні елементи не вдається вивести з базису, то система не має рішень.

  6. Будують послідовність матриць. Потрібно визначити провідний стовпець, провідну рядок і ведучий елемент. Елемент, відповідний провідною рядку, видаляється з базису, а на його місце ставлять елемент, відповідний ведучому стовпцю. Складають рівняння перерахунку матриці, виконують перерахунок, а потім перевіряють його результати на оптимальність. Якщо рішення не оптимально, то заново обмежують провідний елемент, провідну рядок і ведучий стовпець.

Ознакою оптимальності рішення є наявність у векторі рішень тільки негативних або нульових коефіцієнтів при всіх обмеженнях.

Відповідь записується таким чином:

- Кожному негативного коефіцієнту у векторі рішення ставиться у відповідність нульовий коефіцієнт для відповідної змінної у відповіді.

- Для кожного нульового коефіцієнта у векторі рішення ставиться у відповідність значення вільного члена з рядка, що містить одиницю в стовпці даної змінної.

- Фіктивні змінні у відповіді не враховуються.

Провідним може бути призначений будь-який стовпець, що задовольняє одній з умов:

1) Перший стовпець, що містить позитивний елемент у векторі рішень.

2) Стовпець, що містить найбільший позитивний елемент у рядку рішення.

3) Якщо стовпець задовольняє умові max (C j min b j / a ij) при вирішенні на max, і m in (C j min b j / a ij) при вирішенні завдань на min.

C j - коефіцієнт цільової функції в стовпці j, a ij - коефіцієнт у стовпці j і рядку i.

Рішення завдання

Визначимо максимальне значення цільової функції F (X) = 3500 x 1 +3200 x два +1500 x 3 при наступних умовах обмежень.

4 x 1 + 2 x 2 + 5 x 3 <= 190

5 x 1 + 3 x 2 + 4 x 3 <= 320

7 x 1 + 9 x 2 + 5 x 3 <= 454

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

4 x 1 + 2 x 2 + 5 x 3 + 1 x 4 + 0 x 5 + 0 x 6 = 190

5 x 1 + 3 x 2 + 4 x 3 + 0 x 4 + 1 x 5 + 0 x 6 = 320

7 x 1 + 9 x 2 + 5 x 3 + 0 x 4 + 0 x 5 + 1 x 6 = 454

Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:

Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.

Вирішимо систему рівнянь відносно базисних змінних:

x 4, x 5, x 6

Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план: X 1 = (0,0,0,190,320,454)

Оскільки завдання вирішується на максимум, то провідний стовпець вибирають по максимальному негативному числу і індексному рядку. Усі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.

Переходимо до основного алгоритму симплекс-методу.



X 1

X 2

X 3

X 4

X 5

X 6

св. чл.

4

2

5

1

0

0

190

5

3

4

0

1

0

320

7

9

5

0

0

1

454

- 3500

- 3200

- 1500

0

0

0

0

Ітерація № 0

Поточний опорний план неоптімален, так що в індексному рядку знаходяться негативні коефіцієнти

В якості ведучого виберемо стовпець, відповідний змінної x 1, так як найбільший коефіцієнт за модулем.

Обчислимо значення D i по рядках як частка від ділення

і з них виберемо найменше:

Отже, 1-ий рядок є провідною

Дозволяє елемент дорівнює 4 і знаходиться на перетині ведучого шпальти і головною рядки

Формуємо наступну частину симплексного таблиці.

Замість змінної x в план 1 увійде мінлива x 1

Рядок, відповідна змінної x 1 в плані 1, отримана в результаті поділу всіх елементів рядка x 4 плану 0 на дозволяє елемент РЕ = 4

На місці дозволяє елемента в плані 1 отримуємо 1.

В інших клітинах стовпця x 1 плану 1 записуємо нулі.

Таким чином, у новому плані 1 заповнені рядок x 1 і стовпець x 1.

Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозволяє елемент РЕ.

НЕ = СЕ - (А * В) / РЕ

СТЕ - елемент старого плану, РЕ - дозволяє елемент (4), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.

Уявімо розрахунок кожного елемента у вигляді таблиці:

X 1

X 2

X 3

X 4

X 5

X 6

св. чл.

1

1 / 2

5 / 4

1 / 4

0

0

190 / 4

5

3

4

0

1

0

320

7

9

5

0

0

1

454

3500

3200

1500

0

0

0


X 1

X 2

X 3

X 4

X 5

X 6

св. чл.

1

1 / 2

5 / 4

1 / 4

0

0

190 / 4

0

1 / 2

-9 / 4

-5 / 4

1

0

165 / 2

0

11 / 2

-15 / 4

-7 / 4

0

1

243 / 2

0

-1450

2875

875

0

0


Ітерація № 1

Поточний опорний план неоптімален, так що в індексному рядку знаходяться негативні коефіцієнти

В якості ведучого виберемо стовпець, відповідний змінної x 2, так як найбільший коефіцієнт за модулем.

Обчислимо значення D i по рядках як частка від ділення і з них виберемо найменше:

Отже, 3-ий рядок є провідною

Дозволяє елемент дорівнює 5.5 і знаходиться на перетині ведучого шпальти і головною рядки

Формуємо наступну частину симплексного таблиці.

Замість змінної x в план 2 увійде мінлива x 2

Рядок, відповідна змінної x 2 в плані 2, отримана в результаті поділу всіх елементів рядка x 6 плану 1 на дозволяючий елемент РЕ = 5.5

На місці дозволяє елемента в плані 2 отримуємо 1.

В інших клітинах стовпця x 2 плану 2 записуємо нулі.

Таким чином, у новому плані 2 заповнені рядок x 2 і стовпець x 2.

Всі інші елементи нового плану 2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозволяє елемент РЕ.

НЕ = СЕ - (А * В) / РЕ

СТЕ - елемент старого плану, РЕ - дозволяє елемент (5.5), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.

Уявімо розрахунок кожного елемента у вигляді таблиці:

Кінець ітерацій: знайдений оптимальний план



Остаточний варіант симплекс-таблиці:

X 1

X 2

X 3

X 4

X 5

X 6

св. чл.

1

0

159/100

41/100

0

-9/100

729/20

0

0

-191/100

-109/100

1

-9/100

1429/20

0

1

-15/22

-7/22

0

9 / 50

243/11

0

0

1886.36

413.64

0

263.64


Оптимальний план можна записати так:

x 1 = 729/20 = 36.45

x 5 = 1429/20 = 71.45

x 2 = 243/11 = 22.09

F (X) = 3500 * 36.45 + 3200 * 22.09 = 198281.82

Програмна реалізація

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class (TForm)

Label1: TLabel;

Label2: TLabel;

Edit2: TEdit;

Exit: TButton;

Button_Next: TButton;

Edit1: TEdit;

Button_Prev: TButton;

ScrollBox1: TScrollBox;

Conditions: TGroupBox;

Label3: TLabel;

Extrem: TComboBox;

Memo1: TMemo;

procedure ExitClick (Sender: TObject);

procedure Button_NextClick (Sender: TObject);

procedure Button_PrevClick (Sender: TObject);

procedure FormCreate (Sender: TObject);

private

{Private declarations}

public

{Public declarations}

end;

const

mm = 100; nn = 100;

var

Form1: TForm1;

table_changed, done, solve, is_ok, kanon, need_basis, need_i_basis, is_basis, written: boolean;

m, n, y, i_basis, i0, j0, step, iter: integer; {m - елементів, n - обмежень}

pole: array [1 .. nn, 1 .. mm] of TEdit; {поля для введення}

podpis: array [0 .. nn, 0 .. mm] of TLabel; {підпису полів}

znak: array [1 .. nn] of TComboBox; {знаки порівняння обмежень}

matrix: array [1 .. nn, 1 .. mm] of double; {масив для розрахунків}

all_basis: array [1 .. nn] of integer; {номери базисних змінних}

f: text; {файлова змінна для звіту}

tochnost: double;

implementation

{$ R *. dfm}

procedure Init;

{Ініціалізація: введення розмірів системи}

Begin

form1.Button_Prev.Enabled: = false;

form1.Edit1.Enabled: = true;

form1.Edit2.Enabled: = true;

form1.Extrem.Enabled: = true;

form1.ScrollBox1.DestroyComponents; {розчищаємо місце під табличку}

table_changed: = true;

tochnost: = 0.000000001;

assign (f, 'report.htm');

end;

procedure Step1;

{Крок перший: створення таблички і введення значень}

var

i, j: integer;

nadpis: string;

begin

form1.Memo1.ReadOnly: = false;

form1.Memo1.Lines.Clear;

form1.Memo1.ReadOnly: = true;

form1.Extrem.Enabled: = true;

if table _ changed = true then {якщо змінювали кількість ел-тів або обмежень,}

begin {то створюємо нову табличку}

table_changed: = false;

m: = strtoint (form1.Edit1.Text); {зчитуємо кількість змінних}

n: = strtoi

nt (form1.Edit2.Text); {і обмежень}

form1.Edit1.Enabled: = false; {блокуємо поля для їх введення}

form1.Edit2.Enabled: = false;

i: = 0; {використовуємо нульову рядок масиву підписів для заголовків}

for j: = 1 to 3 do {підписуємо що is що}

begin

podpis [i, j]: = TLabel.Create (Form1.ScrollBox1);

podpis [i, j]. parent: = form1.ScrollBox1;

podpis [i, j]. Left: = 5;

podpis [i, j]. Top: = 32 * (j-1); {відстань між написами}

case j of

1: nadpis: = 'Цільова функція: ';

2: nadpis: = 'F (x) =';

3: nadpis: = 'Система обмежень:';

end;

podpis [i, j]. Caption: = nadpis;

end;

i: = n +1; {використовуємо останній рядок масиву полів для цільової ф-ції}

for j: = 1 to m +1 do

begin

pole [i, j]: = TEdit.Create (Form1.ScrollBox1);

pole [i, j]. parent: = form1.ScrollBox1;

pole [i, j]. Height: = 20;

pole [i, j]. Width: = 40;

pole [i, j]. Left: = 80 * (j-1) +30;

pole [i, j]. Top: = 30;

pole [i, j]. Text: = '0 ';

if j <= m then

begin

podpis [i, j]: = TLabel.Create (Form1.ScrollBox1);

podpis [i, j]. parent: = form1.ScrollBox1;

podpis [i, j]. Height: = 20;

podpis [i, j]. Width: = 20;

podpis [i, j]. Left: = pole [i, j]. Left + pole [i, j]. Width +2;

podpis [i, j]. Top: = pole [i, j]. Top +2;

podpis [i, j]. Caption: = 'X [' + inttostr (j )+']';

if j <> m +1 then podpis [i, j]. Caption: = podpis [i, j]. Caption + '+';

{Якщо поле не останнє, то дописуємо плюсик}

end;

end;

for i: = 1 to n do {поля для введення обмежень}

for j: = 1 to m +1 do

begin

pole [i, j]: = TEdit.Create (Form1.ScrollBox1);

pole [i, j]. parent: = form1.ScrollBox1;

pole [i, j]. Height: = 20;

pole [i, j]. Width: = 40;

pole [i, j]. Left: = 80 * (j-1) +5; {відстань між сусідніми + відступ від краю}

pole [i, j]. Top: = 40 * (i-1) +100;

pole [i, j]. Text: = '0 ';

if j <= m then

begin

podpis [i, j]: = TLabel.Create (Form1.ScrollBox1);

podpis [i, j]. parent: = form1.ScrollBox1;

podpis [i, j]. Height: = 20;

podpis [i, j]. Width: = 20;

podpis [i, j]. Left: = pole [i, j]. Left + pole [i, j]. Width +2;

podpis [i, j]. Top: = pole [i, j]. Top +2;

podpis [i, j]. Caption: = 'X [' + inttostr (j )+']';

if j <> m then podpis [i, j]. Caption: = podpis [i, j]. Caption + '+'

{Якщо поле не останнє, то дописуємо плюсик; інакше пишемо знак}

else begin

znak [i]: = TComboBox.Create (Form1.ScrollBox1);

znak [i]. parent: = form1.ScrollBox1;

znak [i]. Height: = 20;

znak [i]. Width: = 40;

znak [i]. Left: = podpis [i, j]. Left + podpis [i, j]. Width +25;

znak [i]. Top: = pole [i, j]. Top;

znak [i]. Items.Insert (0, '>');

znak [i]. Items.Insert (1 ,'>=');

znak [i]. Items.Insert (2, '=');

znak [i]. Items.Insert (3 ,'<=');

znak [i]. Items.Insert (4, '<');

znak [i]. ItemIndex: = 1;

end;

end else pole [i, j]. Left: = pole [i, j]. Left +70; / / поля для правою частини

/ / Обмежень

end;

end else {якщо табличку створювати не треба, то розблокуємо поля}

begin

for i: = 1 to n +1 do

for j: = 1 to m +1 do

begin

pole [i, j]. Enabled: = true;

if i <= n then znak [i]. Enabled: = true;

end;

end;

end;

{/////////////////}

procedure write_system (strok, stolb: integer);

{Записує масив у вигляді рівнянь}

var

i, j: integer;

begin

write (f, '<P> F (x) =');

for j: = 1 to stolb do

begin

write (f, matrix [strok, j]: 0:3);

if j <stolb then

begin

write (f, 'x <sub>', j, '</ sub>');

if (kanon = true) and (j = stolb-1) then write (f, '=') else

if (matrix [strok, j +1]> = 0) then write (f, '+') else write (f, '');

end;

end;

writeln (f, '</ P>');

writeln (f, '<P> При обмеженнях: </ P> <P>');

for i: = 1 to strok-1 do

begin

for j: = 1 to stolb do

BEGIN

write (f, matrix [i, j]: 0:3);

if j <stolb then write (f, 'x <sub>', j, '</ sub>');

if j = stolb-1 then

if kanon = false then write (f, '', znak [i]. text, '')

else write (f, '=');

if (matrix [i, j +1]> = 0) and (j <stolb-1) then write (f ,'+');

end;

writeln (f, '<br>');

end;

writeln (f, '</ P>');

end;

{/////////////////}

procedure zapisat (strok, stolb: integer; v_strok, v_stolb: integer);

{Записує масив у вигляді таблички}

var

i, j: integer;

begin

writeln (f, '<TABLE BORDER BORDERCOLOR=black CELLSPACING=0 CELLPADDING=5>');

for i: = 0 to strok do

begin

writeln (f, '<TR>');

for j: = 1 to stolb +1 do

begin

write (f, '<TD');

if i = 0 then

begin

if (i_basis <> 0) and (j> m + y-i_basis) and (j <= m + y) then

write (f, 'BGCOLOR = yellow')

else

write (f, 'BGCOLOR = green');

end

else

if (i = v_strok) or (j = v_stolb) then write (f, 'BGCOLOR = silver') else

if (i = strok) or (j = stolb) then

if (j <> stolb +1) then write (f, 'BGCOLOR = olive');

write (f, 'align =');

if (i = 0) and (j <stolb) then write(f,'center> X <sub> ', j,' <sub> ') else

if (i = 0) and (j = stolb) then write (f, 'center> св. чл.') else

if (i = 0) and (j = stolb +1) then write (f, 'center> базис') else

if (j = stolb +1) then

if i <> n +1 then write (f, 'center> X <sub>', all_basis [i ],'</ sub> ') else

write (f, 'center>')

else

write (f, 'right>', matrix [i, j]: 1:3);

writeln (f, '</ TD>');

end;

writeln (f, '</ TR>');

end;

writeln (f, '</ TABLE>');

end;

{/////////////////}

procedure findved;

{Шукає провідний елемент}

var

i, j, k: integer;

temp: double;

begin

done: = false;

solve: = false;

is_ok: = true;

temp: = 100000;

i0: = 0;

j0: = 0;

i: = n +1;

for j: = 1 to m + y do

if (i0 = 0) or (j0 = 0) then

if matrix [i, j]> 0 then

begin

j0: = j;

for k: = 1 to n do

if (matrix [k, j]> 0) then

if (matrix [k, m + y +1] / matrix [k, j] <temp) then

begin

temp: = matrix [k, m + y +1] / matrix [k, j];

i0: = k;

end;

end;

if (j0 = 0) and (i0 = 0) then

for j: = 1 to m do

if matrix [n +1, j] = 0 then

for i: = 1 to n do

if (matrix [i, j] <> 0) and (matrix [i, j] <> 1) then

begin

is_ok: = false;

j0: = j;

end;

if is_ok = false then

begin

temp: = 100000;

for k: = 1 to n do

if (matrix [k, j0]> 0) then

if (matrix [k, m + y +1] / matrix [k, j0] <temp) then

begin

temp: = matrix [k, m + y +1] / matrix [k, j0];

i0: = k;

end;

end;

if (j0 = 0) and (i0 = 0) then

begin

writeln (f, '<P> Кінець обчислень </ P> ');

done: = true;

solve: = true;

end

else if (j0 <> 0) and (i0 = 0) then

begin

writeln (f, '<P> Не вдається вирішити систему </ P>');

done: = true;

solve: = false;

end

else

if iter <> 0 then

begin

writeln (f, '<P> <b> Ітерація', iter, '</ b> </ P>');

writeln (f, '<P> Знайдемо провідний елемент: </ P>');

zapisat (n +1, m + y +1, i0, j0);

writeln (f, '<P> Ведучий стовпчик:', j0, '<br> Провідна рядок:', i0, '</ P>');

write (f, '<P> У стрічці', i0, ': базис');

writeln (f, 'X <sub>', all_basis [i0 ],'</ sub> замінюємо на X <sub> ', j0,' </ sub> </ P> ');

all_basis [i0]: = j0;

end;

end;

{/////////////////}

procedure okr;

{Округлює дрібні похибки}

var

i, j: integer;

begin

for i: = 1 to n +1 do

for j: = 1 to m + y +1 do

if abs (matrix [i, j]-round (matrix [i, j])) <tochnost then

matrix [i, j]: = round (matrix [i, j]);

end;

{/////////////////}

procedure preobr;

{Перетворює масив щодо ведучого елемента}

var

i, j, k, l, t: integer;

temp: double;

begin

if done = false then

begin

write (f, '<P> Перерахунок: </ P>');

temp: = matrix [i0, j0];

for j: = 1 to m + y +1 do matrix [i0, j]: = matrix [i0, j] / temp;

for i: = 1 to n +1 do

begin

temp: = matrix [i, j0];

for j: = 1 to m + y +1 do

if (i <> i0) then

matrix [i, j]: = matrix [i, j]-matrix [i0, j] * temp;

end;

okr;

zapisat (n +1, m + y +1, -1, -1);

{///////////////////////// Прибираємо штучний базис ///////////////////// }

if i _ basis> 0 then {якщо він є}

begin

t: = 0;

for j: = m + y - i _ basis +1 to m + y do {від першого ісскусственного елемеента до кінця}

begin

need _ i _ basis: = false; {припускаємо, що елемент не потрібен (*)}

for i: = 1 to n do {переглядаємо стовпець}

if all _ basis [i] = j then {і якщо елемент у базисі}

need _ i _ basis: = true; {тоді він все-таки потрібен}

if need_i_basis = false then t: = j;

{Якщо наші припущення (*) підтвердилися, то запам'ятаємо цей елемент}

end;

if t <> 0 then

begin

for k: = 1 to n +1 do {у всіх рядках}

begin

for l: = t to m + y do {від поточного стовпця до останнього}

matrix [k, l]: = matrix [k, l +1]; {замінюємо елемент на сусідній}

matrix [k, m + y +1]: = 0; {а останній прибираємо}

end;

{Стовпець знищений! треба це запам'ятати}

y: = y-1;

i_basis: = i_basis-1;

if i _ basis> 0 then {якщо залишилися ще штучні змінні,}

for l: = m + y - i _ basis +1 to m + y do {то від першої з них до останньої}

for i: = 1 to n do {переглядаємо рядка у стовпці}

if matrix [i, l] = 1 then all_basis [i]: = l; {туди, де 1, заносимо в базис}

writeln (f, '<P> Штучна мінлива виключена з базису <br>');

writeln (f, 'і може бути вилучена з таблиці.');

writeln (f, '</ P>');

zapisat (n +1, m + y +1, -1, -1);

end;

end;

{/////////////// Закінчили прибирати штучний базис ////////////////////}

end;

end;

{/////////////////}

procedure otvet;

{Виводить відповідь}

var

i, j: integer;

begin

writeln (f, '<P> <b> ВІДПОВІДЬ: </ b> </ P>');

form1.Memo1.ReadOnly: = false;

form1.Memo1.Lines.Clear;

form1.Memo1.Lines.Add ('ВІДПОВІДЬ:');

form1.Memo1.Lines.Add ('');

if (solve = true) and (i_basis = 0) then

write (f, 'F (');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'F (';

if form1.Extrem.ItemIndex = 0 then

begin

write (f, 'max) =' ,0-matrix [n +1, m + y +1]: 0:3);

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'max) =';

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + floattostr (0-matrix [n +1, m + y +1]);

end

else

begin

write (f, 'min) =', matrix [n +1, m + y +1]: 0:3);

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'min) =';

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + floattostr (matrix [n +1, m + y +1]);

end;

writeln (f, '<br> при значеннях: <br>');

form1.Memo1.Lines.Add ('');

form1.Memo1.Lines.Add ('');

form 1. Memo 1. Lines. Add ('при значеннях:');

form1.Memo1.Lines.Add ('');

for j: = 1 to m do

begin

writeln (f, 'x <sub>', j, '</ sub> =');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'X [';

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + inttostr (j);

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + '] =';

written: = false;

for i: = 1 to n do

if all_basis [i] = j then

begin

writeln (f, matrix [i, m + y +1]: 0:3, '<br>');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + floattostr (matrix [i, m + y +1]);

form1.Memo1.Lines.Add ('');

form1.Memo1.Lines.Add ('');

written: = true;

end;

if written = false then

begin

writeln (f, '0 .000 <br> ');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 0 ";

form1.Memo1.Lines.Add ('');

form1.Memo1.Lines.Add ('');

end;

end;

end else

begin

writeln (f, '<P> Рішення НЕ знайдено. (</ P> ');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'Рішення НЕ знайдено. ';

end;

form1.Memo1.ReadOnly: = true;

end;

{/////////////////}

procedure Step2;

{Крок другий: вирішення завдання і формування звіту}

var

i, j: integer;

k: integer;

begin

for i: = 1 to n +1 do

for j: = 1 to m +1 do

begin

matrix [i, j]: = strtofloat (pole [i, j]. Text); {Вводимо значення в масив}

pole [i, j]. Enabled: = false; {Блокуємо поля}

if i <= n then znak [i]. Enabled: = false; {блокуємо знаки}

end;

form1.Extrem.Enabled: = false;

{///////////////////////////////////////////////// ///////////////////////////}

{Маємо матрицю [n +1, m +1]}

rewrite (f);

writeln (f, '<HTML>');

writeln (f, '<HEAD>');

writeln (f, '<TITLE> Звіт </ TITLE>');

writeln (f, '</ HEAD>');

writeln (f, '<BODY>');

writeln (f, '<H1> Звіт </ H1>');

write (f, '<P> <b> Необхідно');

if form1.Extrem.ItemIndex = 0 then write (f, 'макс') else write (f, 'хв');

writeln (f, 'імізіровать цільову функцію: </ b> </ P>');

kanon: = false; {ще не в канонічній формі}

write_system (n +1, m +1); {Виведемо її до звіту}

{Приведемо її до канонічного вигляду}

writeln (f, '<P> <b> Наведемо до канонічного вигляду: </ b> </ P>');

y: = 0; {кількість додаткових змінних}

need_basis: = false;

for i: = 1 to n do

if znak [i]. ItemIndex <> 2 then {якщо обмеження не є рівністю}

begin

y: = y +1; {вводимо додаткову змінну, для цього:}

for k: = 1 to n +1 do begin {у всіх обмеженнях і в ЦФ}

{Перед правою частиною додаємо стовпець}

matrix [k, m + y +1]: = matrix [k, m + y];

matrix [k, m + y]: = 0; {складається з нулів}

end;

{А в поточному обмеження, якщо знак був> або> =}

if (znak [i]. ItemIndex = 0) or (znak [i]. ItemIndex = 1) then

begin

matrix [i, m + y]: =- 1; {записуємо -1}

need_basis: = true;

end

else {інакше, тобто у разі <або <=}

matrix [i, m + y]: = 1; {записуємо 1}

end

else need_basis: = true;

{ЦФ прирівнюється до нуля, а вільний член переноситься в праву частину:}

matrix [n +1, m + y +1]: = 0-matrix [n +1, m + y +1];

{Праві частини обмежень повинні бути ненегативні, перевіримо це:}

for i: = 1 to n do {для всіх обмежень}

if matrix [i, m + y +1] <0 then {якщо права частина негативна,}

{То забираємо всю рядок від нуля}

for j: = 1 to m + y +1 do matrix [i, j]: = (0-matrix [i, j]);

kanon: = true; {система приведена до канонічного вигляду}

{Виведемо її до звіту}

write_system (n +1, m + y +1);

{Якщо ф-ція на мінімум, то потрібно поміняти знаки в останньому рядку}

if form1.Extrem.ItemIndex = 1 then

for j: = 1 to m + y +1 do matrix [n +1, j]: = 0-matrix [n +1, j];

{///////////////////////////////////////////////// ///////////////////////////}

{////////////////////////// Тут треба ввести базис /////////////////// ////////}

i_basis: = 0;

for i: = 1 to n do {то у всіх обмеженнях}

begin

is_basis: = false;

for j: = 1 to m + y do

if (matrix [i, j] = 1) then

if (is_basis = false) then

begin

all_basis [i]: = j;

is_basis: = true;

for k: = 1 to n do

if k <> i then

if (matrix [k, j] <> 0) then

if (is_basis = true) then

begin

is_basis: = false;

all_basis [i]: = 0;

end;

end;

if is_basis = false then

begin

i_basis: = i_basis +1;

y: = y +1;

for k: = 1 to n +1 do

begin {у всіх обмеженнях і в ЦФ}

{Перед правою частиною додаємо стовпець}

matrix [k, m + y +1]: = matrix [k, m + y];

matrix [k, m + y]: = 0; {складається з нулів}

end;

matrix [i, m + y]: = 1;

all_basis [i]: = m + y;

end;

end;

{//////////////// Закінчили введення штучного базису //////////////////////}

{///////////////////////////////////////////////// ///////////////////////////}

{///////////////////////////////////////////////// ///////////////////////////}

{//////////////// Тепер треба від нього позбавитися //////////////////////////// }

if i _ basis> 0 then

begin

write (f, '<H 2> Необхідно ввести штучний базис </ H 2>');

zapisat (n +1, m + y +1, -1, -1);

writeln (f, '<P> Штучний базис введений. <br>');

writeln (f, 'Позбувшись від нього, отримаємо перше допустиме рішення </ P>');

iter: = 0;

repeat

inc (iter);

findved;

preobr;

until (i_basis = 0) or (iter = 20) or (done = true);

if i_basis = 0 then

begin

writeln (f, '<P> Штучний базис виведений повністю. <br>');

writeln (f, 'Отримано першу допустиме рішення! </ P>');

end

else

begin

writeln (f, '<P> Не вдалося вивести штучний базис. <br>');

writeln (f, 'Рішення не знайдено. </ P>');

end;

end;

{//////////////////////// Спроби позбавлення закінчені ////////////////////// / /}

{///////////////////////////////////////////////// ///////////////////////////}

{/////////////////////////////// SIMPLEX START //////////////// /////////////}

if i_basis = 0 then

begin

iter: = 0;

findved;

if done = false then

begin

writeln (f, '<H2> Застосовуємо симплекс метод </ H2>');

repeat

inc (iter);

findved;

preobr;

until (done = true) or (iter = 20);

end;

end;

otvet;

{/////////////////////////////// SIMPLEX END //////////////// ///////////////}

writeln (f, '</ BODY>');

writeln (f, '</ HTML>');

CloseFile (f);

{///////////////////////////////////////////////// ///////////////////////////}

end;

{///////////////////////////////////////////////// ///////////////////////////}

{///////// Все, що нижче, відноситься до переходів між кроками ////////////////}

{///////////////////////////////////////////////// ///////////////////////////}

procedure TForm1.ExitClick (Sender: TObject);

begin

Close ();

end;

procedure TForm1.Button_NextClick (Sender: TObject);

begin

step: = step +1;

Form1.Button_Prev.Enabled: = true;

case step of

1: Step1;

2: begin

Step2;

Form1.Button_Next.Enabled: = false;

end;

else step: = step-1;

end;

form1.Caption: = 'Симплекс метод - крок' + inttostr (step);

end;

procedure TForm1.Button_PrevClick (Sender: TObject);

begin

step: = step-1;

Form1.Button_Next.Enabled: = true;

case step of

0: begin

Init;

Form1.Button_Prev.Enabled: = false;

end;

1: Step1;

else step: = step +1;

end;

form1.Caption: = 'Симплекс метод - крок' + inttostr (step);

end;

procedure TForm1.FormCreate (Sender: TObject);

begin

Init;

end;

Висновок

У цій роботі було розглянуто рішення задач лінійного програмування симплекс методом. Задача була вирішена симплекс методом, так само завдання було вирішено графічно (побудований графік). Для представленої задачі була складена програма на мові Delphi, програма знаходить значення цільової функції за умови максимізації значення.

Таким чином, обчислювальна техніка в даний час знаходить широке застосування, як у загальній математики, так і в одному з її розділів - математичних методах.

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

1. Зайченко Ю.П., Шумилова С.А. Дослідження операцій.

2. Ліщенко «Лінійне і нелінійне програмування», М. 2003

3. О.М. Карасьов, Н.Ш. Кремер, Т.М. Савельєва «Математичні методи в економіці», М.2000

4. Орлов О.І. Теорія прийняття рішень. Навчальний посібник. - М.: Видавництво "Март", 2004

5. Інтернет

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
165.4кб. | скачати


Схожі роботи:
Рішення задачі лінійного програмування симплекс методом
Рішення задач симплекс методом
Симплекс метод рішення задачі лінійного програмування
Рішення задач лінійного програмування 2
Рішення задач лінійного програмування
Рішення задач лінійного програмування різними методами
Рішення задач лінійного програмування в середовищі Maple
Рішення задачі лінійного програмування графічним методом
Рішення задачі лінійного програмування симплексним методом
© Усі права захищені
написати до нас
Рейтинг@Mail.ru