Кваліфікаційна робота бакалавра на тему: «НЕСТАНДАРТНІ ПІДХОДИ ДО РОЗВ’ЯЗАННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ»

Зміст

Вступ    3

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

1. Приклади задач лінійного програмування.    4

2. Дві форми математичної моделі задач лінійного програмування     8

3. Спрощені записи задач лінійного програмування    10

4. Деякі властивості розв’язків задачі лінійного програмування    13

5. Поняття про двоїсті задачі лінійного програмування    14

Розділ II. Традиційні методи розв’язання задачі лінійного програмування.

1. Графічний метод розв’язування задач лінійного програмування    19

2. Симплексний метод розв’язування задач лінійного програмування    26

2.1. Початковий опорний план    27

2.2. Перехід від одного опорного плану до іншого    28

2.3. Оптимальний розв’язок. Критерій оптимальності плану    31

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

Розділ III. Нетрадиційні методи розв’язання задачі лінійного програмування.

1. Зациклення в задачах лінійного програмування    39

2. Опукле програмування    41

3. Градієнтний метод    43

4. Розв’язання задачі лінійного програмування градієнтним методом    49

Висновок    52

Список літератури    53

Вступ

Однією з найважливіших задач оптимізації є задача математичного програмування, що полягає в пошуку екстремуму (мінімуму або максимуму) функції f(x) при умовах gi(x) ≤ 0, i = 1, …, m, Якщо функції f(x), gi(x) i = 1, …, m, – лінійні, а область X задається обмеженнями вигляду xj ≥ 0, j = 1, …, n, то вказана задача називається задачею лінійного програмування (ЗЛП).
Уперше постановка ЗЛП та один із методів її розв’язання були запропоновані Л.В. Канторовичем у роботі “Математические методы организации и планирования производства” у 1939 році. У 1947 році Дж. Данціг розробив симплексний метод (симплекс-метод) – один із основних методів розв’язування ЗЛП. З тих пір теорія лінійного програмування бурхливо розвивалася і нині носить цілісний, в основному, закінчений характер.

Зауважимо, що на розвиток теорії лінійного програмування суттєво впливало її застосування до розв’язування (з широким використанням ЕОМ)
прикладних задач, пов’язаних з оптимальним плануванням, організацією та управлінням у різноманітних сферах людської діяльності.

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

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

Об’єкт дослідження: задача лінійного програмування.

Робоча гіпотеза: градієнтний метод може виявитися неефективним, але результативним методом при розв’язуванні задачі лінійного програмування. Очевидно, він не допустить зациклення як це можливо в симплекс методі.

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

1. Приклади задач лінійного програмування

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

Задача 1.1. Завод додатково освоїв випуск продукції чотирьох асортиментів B1, B2, B3, B4. Для випуску цієї продукції потрібна сировина чотирьох видів A1, A2, A3, A4, яку завод може щомісяця виділяти в обмеженій кількості. Кількість сировини кожного виду, потрібної для виготовлення кожного виду продукції, ціна кожного виду продукції, а також лімітоване щомісячне надходження потрібної сировини подано в такій таблиці:

Види сировини

Щомісячне надходження сировини ( в умовних одиницях )

Витрати сировини на одиницю кожного виробу

В1

В2

В3

В4

А1

А2

А3

А4

1260

900

530

210

2

2

0

1

4

2

1

0

6

0

1

1

8

6

2

0

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

8

10

12

18

Кількість продукції

x1

x2

x3

x4

Визначити, в якій кількості завод має випускати кожний з видів продукції B1, B2, B3, B4, щоб прибуток від її реалізації був максимальний.

Розв’язання. Характерні особливості цієї задачі:

а) додаткову продукцію B1, B2, B3, B4 завод може виготовляти при обмежених засобах: через певні обставини завод не може виділити більше сировини, ніж показано в таблиці;

б) серед багатьох можливих варіантів плану випуску продукції B1, B2, B3 і B4 треба вибрати найкращий, тобто в нашому випадку той, який дає максимум прибутку.

Особливості а) і б) властиві кожній задачі лінійного програмування.

Складемо математичну модель цієї задачі. Позначимо через х1, х2, х3, х4 відповідно ті кількості продукції асортиментів B1, B2, B3, B4, які треба випустити, щоб мати максимальний прибуток від їх реалізації. Тоді на випуск продукції B1 буде витрачено 2х1 умовних одиниць сировини А1, на випуск B2 – 4х2, на випуск B3 – 6х3, на випуск B4 – 8х4
умовних одиниць сировини А1 не повинні перевищувати 1260 умовних одиниць. Дістаємо таку лінійну нерівність:

2х1 + 4х2 + 6х3 + 8х4 ≤ 1260.

За змістом задачі невідомі х1, х2, х3, х4 є невід’ємні величини, тобто х1
≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0. Аналогічні міркування проводять до такої системи лінійних нерівностей, які накладають обмеження на значення невідомих х1, х2, х3, х4:

2х1 + 4х2 + 6х3 + 8х4 ≤ 1260,

    2х1 + 2х2 + 6х4 ≤ 900,    (1.1)

х1 + х3 ≤ 210,

х2 + х3 + 2х4 ≤ 530.

    х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0.    (1.2)

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

    Z = 8х1 + 10х2 + 12х3 + 18х4.    (1.3)

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Nestand Pidh Do Rozv-zadach Lin Prog (2.8 MiB, Завантажень: 4)

Сторінка: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
завантаження...
WordPress: 23.75MB | MySQL:26 | 0,373sec