Xreferat.com » Рефераты по информатике и программированию » Економічні задачі лінійного програмування і методи їх вирішення

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

src="http://xreferat.ru/image/33/1305988749_69.png" alt="Економічні задачі лінійного програмування і методи їх вирішення" width="133" height="53" align="BOTTOM" border="0" />,

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


де X = (x1, …, xn) — вектор змінних,


C = (c1, …., cn), B = (b1, …, bm)T,

Aj = (a1j, …, amj)T, j = 1, …, n — задані вектори,


T — знак транспонування, та


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


відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану — Економічні задачі лінійного програмування і методи їх вирішення. Тоді


Економічні задачі лінійного програмування і методи їх вирішення, (1)

Економічні задачі лінійного програмування і методи їх вирішення, (2)


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


Економічні задачі лінійного програмування і методи їх вирішення, (3)

Економічні задачі лінійного програмування і методи їх вирішення, (4)


де xij коефіцієнт розкладання. Система умов


Економічні задачі лінійного програмування і методи їх вирішення, (5)

zk ≥ 0, xj = 0, j = m + 1, …, n, j ≠ k (6)


при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому променю дорівнює θ, тоді значення базисних змінних дорівнюють xi(θ). В цих позначеннях рівняння (5) можна представити в виді


Економічні задачі лінійного програмування і методи їх вирішення. (7)


помноживши рівняння (3) на θ при j = k та віднявши від рівняння (1), отримаємо


Економічні задачі лінійного програмування і методи їх вирішення. (8)


Із рівнянь (7-8) отримаємо


Економічні задачі лінійного програмування і методи їх вирішення. (9)


Оскільки xi(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження xi (θ) ≥ 0, визначається із умови

Економічні задачі лінійного програмування і методи їх вирішення. (10)

де I = {i | xik > 0}.


В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ0 визначається із рівнянь (9), (4), (2)


Економічні задачі лінійного програмування і методи їх вирішення,


де Δk = zk — ck. Очевидно, Δj = 0 для j = 1, …, m.

Нехай Економічні задачі лінійного програмування і методи їх вирішення — початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:

знайти Δk = minjΔj. Якщо Δk = 0, тоді план, який розглядається оптимізовано; якщо Δk < 0, вектор Ak вводиться в базис;

знайти θ0 та l, для якого Економічні задачі лінійного програмування і методи їх вирішення, із формули (10). Якщо I = Λ — порожня множина, лінійна форма необмежена зверху; якщо I ≠ Λ вектор Al виводиться із базису;

за знайденими l, k обчислити нові значення елементів таблиці за формулами


Економічні задачі лінійного програмування і методи їх вирішення (12)

Економічні задачі лінійного програмування і методи їх вирішення,


де Економічні задачі лінійного програмування і методи їх вирішеннята перейти до виконання операції (1) з новими значеннями всіх xij = x'ij.

Перетворення (12) замінює вектор коефіцієнтів Xk = (x1k, …, xmk) на одиничний вектор Xk з xlk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.

Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу


Економічні задачі лінійного програмування і методи їх вирішення,


при обмеженнях


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

Економічні задачі лінійного програмування і методи їх вирішення;

Економічні задачі лінійного програмування і методи їх вирішення,


яка містить одиничний базис, який складається із векторів An+1, …, An+m. Цим векторам відповідають штучні змінні із значеннями Економічні задачі лінійного програмування і методи їх вирішення, i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі Економічні задачі лінійного програмування і методи їх вирішення, вихідна задача не має розв'язку. Якщо ж Економічні задачі лінійного програмування і методи їх вирішеннята задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z0 може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних Економічні задачі лінійного програмування і методи їх вирішеннядорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин bi на bi + εi, де εi достатньо малі, при вдалому виборі εi не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.


3. Прикладний розділ


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


Для розробки математичної моделі задачі позначимо:

x1 – кількість продукту А;

x2 – кількість продукту В;

Цільова функція буде мати вид:


Z=x1+2x2¦mах


Система обмежень:


3 x1+3 x2 <= 15 2 x1+6 x2 <= 18 4 x1<= 16 x1+2x2 <= 8 Xj>=0, j=1..2


Зведення задачі до канонічного виду: Zmax = x1+2x2 при умовах:


3x1+3x2+x3 = 15 2x1+6x2+x4 = 18 4x1+x5 = 16 x1+2x2+x6 = 8 Xj>=0, j=1..6


Таблиця 5.

Базис С План 1 2 0 0 0 0
X3 0 15 3 3 1 0 0 0
X4 0 18 2 6 0 1 0 0
X5 0 16 4 0 0 0 1 0
X6 0 8 1 2 0 0 0 1
Zj-Cj
0 -1 -2 0 0 0 0

Таблиця 6.

Базис С План 1 2 0 0 0 0
X3 0 6 2 0 1 -0,5 0 0
X2 2 3 40238 1 0 40330 0 0
X5 0 16 4 0 0 0 1 0
X6 0 2 40238 0 0 -0,3333 0 1
Zj-Cj
6 -0,3333 0 0 40238 0 0

Таблиця 7.

Базис С План 1 2 0 0 0 0
X1 1 3 1 0 40210 -0,25 0 0
X2 2 2 0 1 -0,1667 40269 0 0
X5 0 4 0 0 -2 1 1 0
X6 0 1 0 0 -0,1667 -0,25 0 1
Zj-Cj
7 0 0 40330 40269 0 0

Відповідь: Zmax =7, Xопт =(3 ; 2 ; 0 ; 0 ; 4 ; 1).

Це свідчить про те, що максимальний прибуток підприємства буде дорівнювати 7 грн., а виробництво продукції А і В складає відповідно 3 і 2 одиниці.


3.2 Вирішення задачі лінійного програмування за допомогою «Пошуку рішень» у середовищі Microsoft Office Excel 2003


«Пошук рішень» – одна із сервісних можливостей пакету Microsoft Office Excel 2003. Він представляє собою спрощений варіант симплекс-методу.

«Пошук рішень» викликається за допомогою меню «Сервіс», далі вибираємо підменю «Надстройки» і натискаємо «Пошук рішень» [12].

Методика знаходження рішення задачі за допомогою «Пошуку рішень» в Excel полягає в тому, що користувач задає основні параметри завдання (цільову функцію, систему обмежень) і змінні клітинки, яким дають деякі довільні початкові значення (одиниці). Після цього «Пошук рішень» автоматично перебирає всі можливі значення змінюваних клітинок так, щоб вони задовольняли обмеженням, а цільова функція приймала задані значення. Таким чином, порядок виконання «Пошуку рішень» такий [3]:

1. На аркуші Excel формується масив, відповідний розширеній матриці системи обмежень задачі (блок клітинок В2:С5 та Е2:Е5).

2. Виділяються клітинки, відповідні змінним завдання, яким присвоюються початкові значення, які дорівнюють одиницям (В8:С8).

3. Виділяється клітинка, в якій обчислюється значення цільової функції, яка містить посилання на клітинки змінних (у клітинку В10 вводимо формулу =1*B8+2*C8).

4. Створюється масив, відповідний лівим і правим частинам системи обмежень. Для цього з посиланням на клітинки коефіцієнтів і змінних обчислюються складові лівих частин системи обмежень, і обчислюється сума (у клітинку В12 вводимо формулу =B2*B8, у клітинку В13 вводимо =B3*$B$8 і далі тягнемо мишкою вниз ще на дві клітинки; у клітинку С12 вводимо =C2*$C$8 і тягнемо вниз; відповідно у клітинках Е12-Е15 обчислимо суму построково). Це все проілюстровано на рисунку 1.


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

Рис. 1.

5. Після запуску «Пошуку рішень» задається адреса цільової клітинки, спрямованість цільової функції, адреса змінюваних клітинок, система обмежень, умова невід’ємності значень змінних. Вікно «Пошуку рішень» зображено на рисунку 2.


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

Рис. 2.


6. У параметрах виділяється лінійна і невід'ємна моделі. Дивись рисунок 3.


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

Рис. 3.


7. Проводиться запуск. У випадку, якщо необхідне рішення знайдено, воно зберігається. Це вікно зображене на рисунку 4.


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

Рис. 4.


Остаточні результати бачимо на рисунку 5. З нього видно, що x1=3, тобто продукції виду А необхідно виготовляти у кількості 3-х одиниць, x2=2, тобто продукції виду В необхідно виготовляти у кількості 2-х одиниць, при цьому максимальне значення цільової функції буде досягати 7, тобто прибуток підприємства буде складати 7 грн.

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

Рис. 5.


Висновки


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

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

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

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

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

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

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


СПИСОК ЛІТЕРАТУРИ


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

Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и свіязь, 1989. – 176с.

Белобродский А.В., Гриценко М.А. Поиск решений с Excel 2000. –Воронеж, 2001.

Вагнер Г. Основы исследования операций. Т.1. – М.: Издательство «Мир», 1972.

Вентцель Е. С. Исследование операций. Задачи, принципы, методология. – М.: Дрофа, 2004.

Енциклопедія кібернетики /За ред. В. Глушкова. – К.: «Українська радянська енциклопедія», 1973.

Зайченко Ю.П. Исследование операций. – К.: Вища шк., 1979.

Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. – М.: «Дело и Сервис» , 1999. – 368 с.

Конюховский П.В. Математические методы исследования операций в экономике. – СПб.: Питер, 2000. – 208с.

Косоруков О.А., Мищенко А.В. Исследование операций /Под общ. ред.. Н. П. Тихомирова. – М.: «Экзамен», 2003.

Лотов А.В. Введение в экономико-математическое моделирование. – М.: Наука, 1984. – 391с.

Мур Дж., Уэдерфорд Л.Р. и др. Экономическое моделирование в Microsoft Excel. – М.: Издательский дом «Вильямс», 2004. – 1024 с.

Таха, Хемди А. Введение в исследование операцій: Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 912с.

Химмельблау. Прикладное нелинейное программирование. – М.: «Мир», 1975.

Шелобаев С. И. Математические методы и модели в экономике, финансах, бизнесе. – Учеб. пособие для вузов. – М.: ЮНИТИ-ДАНА, 2001. – 367с.

Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. Теория, методы и приложения. – М.: Наука, 1969. – 424с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: