Цілочислові задачі лінійного програмування

Цілочислові задачі лінійного програмування

1. Огляд теми

Цілочислове програмування

1.1.  Математична постановка задачі цілочислового програмування.

1.2.  Алгоритм розв’язання задачі цілочислового програмування графічним методом.

1.3.  Алгоритм методу Гоморі.

1.1 Математична постановка задачі цілочислового програмування

Для більшості економічних задач їх розв’язок повинен бути виражений цілими числами. Наприклад, кількість одиниць продукції, що не можна ділити, кількість обладнання тощо.

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

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

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

(1.1)

При умовах

(1.2)

, (1.3)

— цілі (1.4)

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

1.2  Алгоритм розв’язання задачі цілочислового програмування графічним методом

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

Розглянемо Алгоритм даного Методу на прикладі:

В цеху підприємства вирішили встановити додаткове обладнання, для розміщення якого виділено 19/3 м2 площі. На придбання обладнання підприємство може витратити 10000 грн., при цьому воно може закупити обладнання двох видів. Комплект обладнання І виду коштує 1000 грн., а ІІ виду – 3000 грн. Придбання одного комплекту обладнання І виду позволить збільшити випуск продукції за зміну на 2 од., а одного комплекту обладнання ІІ виду – на 4 од. Для установки одного комплекту обладнання І виду потрібно 2 м2 площі, а для обладнання ІІ виду – 1 м2 площі. Визначити такий набір додаткового обладнання, який дасть можливість максимально збільшити випуск продукції.

Розв’язання. Нехай х1 – кількість комплектів обладнання І виду, що придбає підприємство, а х2 – кількість комплектів обладнання ІІ виду. Тоді математична модель задачі має вигляд:

1)  Розв’язати задачу графічним методом [див. Частина 1, с. 19-20]. Якщо отримано цілочисловий розв’язок, то задача розв’язана. В протилежному випадку перейти до п.2.

2)  Замінити контур багатокутника розв’язків ламаною лінією, вершини якої на виходять за межі багатокутника розв’язків і мають цілочислові координати (див. рис.. 1.1)

3)  Будують вектор з координатами, рівними коефіцієнтам цільової функції, тобто вектор з координатами (2;4).

4) Через точку (0;0) проводять перпендикулярну до вектора пряму А.

5) Переcуваючи пряму А в напрямку вектора , визначають першу та останню точки перетину прямої з багатокутником розв’язків. Перша точка – точка мінімуму, остання – точка максимуму.

6) Визначають координати точки максимуму (мінімуму).

7) Визначають значення цільової функції в точці максимуму (мінімуму), підставляючи в цільову функцію координати точки максимуму(мінімуму) Рис. 1.1

Розв’язком наведеного прикладу є т. E(1;3), в якій цільова функція приймає максимальне значення . Тобто підприємство повинно придбати 1 комплект обладнання першого виду і 3 комплекти обладнання другого виду. Це забезпечить підприємству максимальне збільшення випуску продукції, що дорівнює 14 одиниць за зміну.

1.3  Алгоритм методу Гоморі.

Іншим способом розв’язання задач цілочислового програмування є метод Гоморі, який складається з таких етапів:

1)  Знаходять розв’язок задачі цілочислового програмування симплексним методом, не зважаючи на умову цілочисловості змінних.

2)  Аналізують знайдений розв’язок. Якщо серед компонентів нема дробових чисел, то знайдений план являється оптимальним планом задачі цілочислового програмування. В противному випадку складають додаткове обмеження для змінної, яка в оптимальному плані задачі (1.1)-(1.3) має максимальне дробове значення, а в оптимальному плані задачі (1.1)-(1.4) повинна бути цілочисловою.

(1.5)

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

Дробовою частиною числа називається різниця між цим числом і його цілою частиною.

Цілою частиною числа називається найбільше ціле число, яке не перевищує дане.

3)  За допомогою двоїстого симплексного методу знаходять розв’язок задачі, яку отримали із задачі (1.1)-(1.4) шляхом введення додаткового обмеження.

4)  В разі необхідності складають ще одне додаткове обмеження і продовжують ітераційний процес до отримання оптимального плану задачі (1.1)-(1.4) або до встановлення неможливості її розв’язання.

Приклад. Підприємство випускає два види продукції – А і В. Для цього використовує два види сировини. Норми витрат сировини кожного виду на виготовлення одиниці продукції даного виду наведено в таблиці 1. В ній також указано прибуток від реалізації одиниці продукції кожного виду і загальна кількість сировини по видах.

Вид сировини

Норми витрат сировини (кг) на одиницю продукції виду

Загальна кількість сировини (кг)

А

В

І

2

1

ІІ

1

3

4

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

1

4

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

Нехай — кількість виробів виду А, — кількість виробів виду В. Тоді прибуток підприємства складає

При умовах

.

Запишемо задачу в формі основної задачі ЛП:

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

Застосуємо алгоритм розв’зання цілочислових задач ЛП методом Гоморі.

1)  Розв’яжемо задачу симплексним методом без врахування умови цілочисловості змінних та .

Базис

Сб

План

1

4

0

0

Оціночні відношення

Х1

Х2

Х3

Х4

1

Х3

0

2

1

1

0

2

Х4

0

4

1

3

0

1

®min

M+1

0

-1

-4

0

0

1

Х3

0

5

5/3

0

1

-1/3

2

Х2

4

4/3

1/3

1

0

1/3

M+1

16/3

1/3

0

0

4/3

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

.

Знаходимо значення функції як дробової частини вказаних аргументів:

Або

Для того, щоб змінна стала базисною, помножимо отримане рівняння на .

Базис

Сб

План

1

4

0

0

0

Х1

Х2

Х3

Х4

Х5

1

Х3

0

5

5/3

0

1

-1/3

0

2

Х2

4

4/3

1/3

1

0

1/3

0

3

Х5

0

-1

-1

0

0

-1

1

M+1

16/3

1/3

0

0

4/3

0

3)  За допомогою двоїстого симплексного методу знаходимо розв’язок отриманої задачі.

Базис

Сб

План

1

4

0

0

0

Х1

Х2

Х3

Х4

Х5

1

Х3

0

5

5/3

0

1

-1/3

0

2

Х2

4

4/3

1/3

1

0

1/3

0

3

Х5

0

-1

-1

0

0

-1

1

M+1

16/3

1/3

0

0

4/3

0

1

Х3

0

10/3

0

0

1

-2

5/3

2

Х2

4

1

0

1

0

0

1/3

3

Х1

1

1

1

0

0

1

-1

M+1

5

0

0

0

1

1/3

Отримали цілочисловий розв’язок: . Отже, підприємство повинно виробляти 1 шт. виробів виду А і 1 шт. виробів виду В. При цьому його прибуток складатиме 5 гр. од.

3. Рекомендована література

1. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.

2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

Tagged with: , , , , ,
Posted in Математичні моделі в розрахунках на еом

Перелік предметів:
  1. Інформаційні технологіі в галузі
  2. Інформаційні технологіі в системах якості стандартизаціісертифікаціі
  3. Історія української культури
  4. Бухоблік у ресторанному господарстві
  5. Діловодство
  6. Мікропроцесорні системи управління технологічними процесами
  7. Науково-практичні основи технологіі молока і молочних продуктів
  8. Науково-практичні основи технологіі м’яса і м’ясних продуктів
  9. Організація обслуговування у підприємствах ресторанного господарства
  10. Основи наукових досліджень та технічноі творчості
  11. Основи охорони праці
  12. Основи підприємницькоі діяльності та агробізнесу
  13. Політологія
  14. Технологічне обладнання для молочноі промисловості
  15. Технологічне обладнання для м’ясноі промисловості
  16. Технологічний семінар
  17. Технологія зберігання консервування та переробки молока
  18. Технологія зберігання консервування та переробки м’яса
  19. Технологія продукціі підприємств ресторанного господарства
  20. Технохімічний контроль
  21. Технохімічний контроль
  22. Управління якістю продукціі ресторанного господарства
  23. Вища математика 3к.1с
  24. Вступ до фаху 4к.2с.
  25. Загальні технології харчових виробництв
  26. Загальна технологія харчових виробництв 4к.2с.
  27. Мікробіологія молока і молочних продуктів 3к.1с
  28. Математичні моделі в розрахунках на еом
  29. Методи контролю харчових виробництв
  30. Основи фізіології та гігієни харчування 3к.1с
  31. Отримання доброякісного молока 3к.1с
  32. Прикладна механіка
  33. Прикладна механіка 4к.2с.
  34. Теоретичні основи технології харчових виробництв
  35. Технологія зберігання, консервування та переробки м’яса
  36. Фізика
  37. Харчові та дієтичні добавки
  38. Фізичне виховання 3к.1с

На русском

  1. Методы контроля пищевых производств
  2. Общая технология пищевых производств
  3. Теоретические основы технологий пищевых производств
  4. Технология хранения, консервирования и переработки мяса
LiveInternet

Интернет реклама УБС