Основні задачі лінійного програмування by Vita - Illustrated by В.А. Лихогоденко - Ourboox.com
This free e-book was created with
Ourboox.com

Create your own amazing e-book!
It's simple and free.

Start now

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

by

Artwork: В.А. Лихогоденко

  • Joined Jan 2018
  • Published Books 1

ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

1.1. Предмет та сфери математичного програмування

 В різних областях людської діяльності економісти зустрічаються із задачами, які характеризуються такими властивостями:

1) на змінні величини накладається велика кількість обмежень;

2) задача має велику кількість розв’язків, із яких потрібно вибрати найкращий (оптимальний).

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

Початок розвитку математичного програмування покладено в 1939 році радянським математиком Л.В.Канторовичем в роботі «Математичні методи організації і планування підприємства».

Для розв’язання конкретної економічної задачі потрібно побудувати математичну модель.


1.1. Предмет та сфери математичного програмування

В різних областях людської діяльності економісти зустрічаються із задачами, які характеризуються такими властивостями:

1) на змінні величини накладається велика кількість обмежень;

2) задача має велику кількість розв’язків, із яких потрібно вибрати найкращий (оптимальний).

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

Початок розвитку математичного програмування покладено в 1939 році радянським математиком Л.В.Канторовичем в роботі «Математичні методи організації і планування підприємства».

Для розв’язання конкретної економічної задачі потрібно побудувати математичну модель.

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

Побудова математичних моделей включає наступні два етапи:

  1. Представляється у вигляді деякої залежності від невідомих величин переслідувана мета (прибуток від реалізації виробленої продукції, сумарні витрати на перевезення вантажів та тощо). Отриманий вираз називається цільовою функцією, функцією цілі, функціоналом або критерієм ефективності даної задачі.
  2. Формулюються умови, які повинні бути накладені на невідомі величини (змінні). вони витікають із наявності ресурсів, із необхідності задоволення потреб, із умов технології та інших економічних та технічних факторів. Ці умови представляють собою нерівності або рівняння.

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

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

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

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

Функція (1.1) називається функцією цілі (цільовою функцією) або лінійною формою. Співвідношення. (1.2) – (1.4) є обмеженнями задачі. Умови (1.4) називаються умовами незаперечності (невід’ємності), що накладають на змінні.

Для розв’язання практичних задач частіше використовуються інші форми постановок ЗЛП, а саме – симетрична й канонічна форми.

2
Основні задачі лінійного програмування by Vita - Illustrated by В.А. Лихогоденко - Ourboox.com

Лихогоденко В.А.,Самусенко П.Ф.

1 Студентка 2 курсу магістратури НПУ ім. М.П. Драгоманова, спеціальність Середня освіта (інформатика)

2 доцент, кандидат фізико-математичних наук,   кафедра теоретичних основ інформатики Факультету інформатики НПУ імені М.П.Драгоманова.

АНАЛІЗ ПРИКЛАДНИХ ЗАСОБІВ ДЛЯ РОЗВ’ЯЗАННЯ ОСНОВНИХ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Анотація. У статті проведений аналіз спеціалізованого програмного забезпечення, за допомогою якого задачі лінійного програмування можуть бути розв’язані за досить короткий час, зокрема Mathcad.. Ураховуючи переваги web-орієнтованого програмного забезпечення, у статті схарактеризовано web-сервіс WolframAlpha.

Ключові слова: лінійне програмування, програмне забезпечення, MathCad, WolframAlpha.

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

Окремий комплекс проблем стосується застосування пакетів прикладних програм для здійснення різноманітних математичних операцій, дій і обрахунків, так званих систем комп’ютерної математики (СКМ), зокрема Mathcad  та WolframAlpha.

Аналіз попередніх досліджень.

На сьогодні недостатньо проробленими залишаються методики розв’язання задач оптимізації та лінійного програмування з використанням сучасних комп’ютерних технологій, а саме з використанням математичного процесора MathCad та онлайн додатку WolframAlpha. В Україні над цією проблемою працюють науковці М.А. Мартиненко, Т.О. Кривець, Ю.В. Горошко, Д.А. Покришень, Т.П. Кобильник, В.О. Овчарук , І.В. Овчарук  та ін.

Мета статті. Аналіз спеціалізованих програмних забезпечень для розв’язання основних задач лінійного програмування.  

Виклад основного матеріалу.

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

Mathcad був задуманий і спочатку написаний Алленом Раздовим з Массачусетського технологічного інституту, співзасновником компанії Mathsoft Inc., яка з 2006 року є частиною корпорації PTC (Parametric Technology Corporation).

Простота інтерфейсу зробила МП MathCAD одним із самих популярних і розповсюджених в студентському середовищі математичних пакетів. Для введення формул і даних можна використовувати як клавіатуру, так і спеціальні панелі інструментів.

Деякі з математичних можливостей Mathcad засновані на підмножині системи комп’ютерної алгебри Maple (MKM, Maple Kernel Mathsoft).

Робота здійснюється в межах робочого аркуша, на якому рівняння і вирази відображаються графічно, на противагу текстовому запису в мовах програмування. При створенні документів-програм використовується принцип WYSIWYG (What You See Is What You Get — «що бачиш, те й отримуєш»).

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

Одним з прикладів кросплатформеного програмного забезпечення може бути система знань WolframAlpha, автором якої є Стівен Вольфрам – фізик, математик та програміст з Великої Британії. Безкоштовний технічний ресурс WolframAlpha (http://wolframalpha.com) від компанії Wolfram Research є новим способом отримання даних та відповідей за допомогою швидких розрахунків, основою яких є величезна колекція вбудованих даних, алгоритмів та методів.

Даний ресурс є кросплатформеним, оснащений веб-інтерфейсом, не вимогливий до апаратних ресурсів, оскільки розрахунки виконуються на серверах WolframAlpha. Для користувачів, які використовують його через комп’ютери та ноутбуки, ресурс безкоштовний, а для планшетів необхідно придбати додаток за символічну ціну 2,99$. До недоліків можна віднести наступне: англомовний інтерфейс; всі запити необхідно робити також англійською мовою; база знань, яка використовується у програмі, більше орієнтована на запити американських та західноєвропейських користувачів. В основі математичного ядра WolframAlpha лежить набір алгоритмів потужної математичної програми Mathematica від того ж виробника.

Висновки. В роботі приведено аналіз двох спеціалізованих програмних середовищ для роз’язування задач лінійного програмування, системи автоматизованих інженерних та економічних розрахунків Mathсad та бази знань і набору обчислювальних алгоритмів WolframAlpha. Ефективне розв’язання оптимізаційних задач вимагає використання сучасного потужного апарату, методів аналізу  та дослідження первинних даних. На сьогодні існує велика кількість спеціалізованих програмних забезпечень, за допомогою яких такі задачі можуть бути вирішені за досить короткий час.

ЛІТЕРАТУРА

  1. Математичне програмування: Навч. посібник/ MA. Мартиненко, O.M. Нещадим, В.М. Сафонов. – К.: «Четверта хвиля», 2002. – 220 с. Mathcad в інженерних розрахунках. Частина 1. Методичні вказівки для студентів інженерних спеціальностей / Укл. В.В. Гавриленко, КС. Величко, KM. Алексеенко. – К.: НТУ, 2002. – 127 с.
  2. Методичні особливості вивчення та застосування математичного пакету MathCad студентами технологічних спеціальностей Н.І. Вовкодав, Т.О. Кривець, О.О. Кубайчук
  3. Горошко Ю.В. Система знань WolframAlpha / Ю.В. Гоорошко, Д.А. Покришень // Науковий чвсопис НПУ імені Драгоманова. Серія №
  4. Кобильник Т.П. ВИКРИСТАННЯ  WEB-СЕРВІСУ WOLFRAMALPHA ДЛЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ З ТЕОРІЇ ЙМОВІРНОСТЕЙ / Т.П. Кобильник // Інформаційні технології в освіті. – 2015. – №24. – С. 68-80. Горошко Ю.В. Система знань WolframAlpha / Ю.В. Горошко,д.А. Покришень // Науковий часопис НПУ імені М.П. Драгоманова. Серія №
  5. Математика с компьютером. – К.: НПУ имени М.П. Драгоманова. 2012 р. – 300 с. (співавт. Горошко Ю.В., Винниченко Е.Ф.).
  6. В.О. Овчарук , І.В. Овчарук  Розв’язок задач оптимізації – як складова підготовки кадрів у галузі інформаційних технологій Автоматика/Automatics 2012, 26-28 вересня 2012 року, Київ, Україна
  7. Wolfram gridMathematica: Multiplying the Power of Mathematica over the Grid [Електронний ресурс]. Режим доступу https://www/wolfram.com/gridmathematica/.

Самусенко П.Ф., Лихогоденко В.А.

АНАЛИЗ ПРИКЛАДНЫХ СРЕДСТВ ДЛЯ РЕШЕНИЯ ОСНОВНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Аннотация. В статье проведен анализ специализированного программного обеспечения, с помощью которого задачи линейного программирования могут быть решены за достаточно короткое время, в частности Mathcad . Учитывая преимущества web-ориентированного программного обеспечения, в статье охарактеризован web-сервис WolframAlpha.

Ключевые слова: линейное программирование, программное обеспечение, MathCad, WolframAlpha.

Samusenko P.F.,Lyhohodenko V.A.

ANALYSIS OF APPLICATION SOFTWARE FOR SOLVING THE MAIN LINEAR PROGRAMMING CHALLENGES

Annotation. The article analyzes the specialized software, by means of which linear programming problems can be solved in a short time, in particular, Mathcad. Taking into account the advantages of web-oriented software, the article describes the WolframAlpha web service.

Keywords: linear programming, software, MathCad, WolframAlpha.

4

Розвязання задач лінійного програмування в Excel за допомогою “Пошуку рішення”

https://youtu.be/z_q1-h_kqw4

5
Основні задачі лінійного програмування by Vita - Illustrated by В.А. Лихогоденко - Ourboox.com
This free e-book was created with
Ourboox.com

Create your own amazing e-book!
It's simple and free.

Start now

Ad Remove Ads [X]
Skip to content