Экономические науки/8. Математические методы в экономике

Валідуда С.В., науковий керівник к.п.н., доц. Клочко О.В.

Вінницький національний аграрний університет, Україна

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

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

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

У 1931 р. угорський математик Б. Егерварі розглянув математичну постановку й вирішив задачу лінійного програмування, що має назва «проблема вибору», метод розв'язання одержав назву «угорського методу».

Засновником теорії математичного програмування в сучасному розумінні вважають праці радянського вченого Л. В. Канторовича. Наприкінці 30-х років у Ленінградському університеті ним уперше були сформульовані та досліджувались основні задачі, критерії оптимальності, економічна інтерпретація, методи розв’язання та геометрична інтерпретація результатів розв’язання задач лінійного програмування (1939 року Л. В. Канторович оприлюднив монографію «Математичні методи організації і планування виробництва»). Термін «програмування» потрібно розуміти в значенні «планування». Він був запропонований в середині 1940-х років Джорджем Данціґом, одним із засновників лінійного програмування, ще до того, як комп'ютери були використані для вирішення лінійних задач оптимізації. Для розв'язання задач лінійного програмування з великою кількістю змінних та обмежень використовують методи декомпозиції, які дають змогу замість вихідної задачі розв'язувати послідовність задач меншого обсягу. Сам термін «лінійне програмування» був введений дещо пізніше, 1951 року, у працях американських вчених Дж. Данцига та Г. Кумпанса. Однак у своїй монографії Дж. Данциг зазначає, що Л. В. Канторовича слід визнати першим, хто виявив, що широке коло важливих виробничих задач може бути подане у чіткому математичному формулюванні, яке уможливлює підхід до таких задач з кількісного боку та розв’язання їх чисельними методами. Лінíйне програмувáння (LP, англ. Linear Programming) — один з важливих розділів дослідження операцій, що зводиться до оптимізації лінійної цільової функції на множині, яка описується лінійними рівняннями і нерівностями.

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

Л. В. Канторовичем разом із М. К. Гавуриним в 1949 р. розроблено метод потенціалів, що застосовується при розв'язанні транспортних задач. У наступних роботах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лур'є, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдіна, Е. Г. Гольштейна й інших математиків і економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування, так і застосування її методів до дослідження різних економічних проблем. Методам лінійного програмування присвячено багато робіт зарубіжних учених. В 1941 р. Ф. Л. Хітчкок сформулював транспортну задачу.

Періодом інтенсивного розвитку математичного програмування є п’ятдесяті роки. У цей час з’являються розробки нових алгоритмів, теоретичні дослідження з різних напрямків математичного програмування: 1951 року — праця Г. Куна і А. Таккера, в якій наведено необхідні та достатні умови оптимальності нелінійних задач; 1954 року — Чарнес і Лемке розглянули наближений метод розв’язання задач з сепарабельним опуклим функціоналом та лінійними обмеженнями; 1955 року — ряд робіт, присвячених квадратичному програмуванню. У п’ятдесятих роках сформувався новий напрямок математичного програмування — динамічне програмування, значний вклад у розвиток якого вніс американський математик Р. Белман.

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

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

Література:

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

2. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

3. Плотников А.Д. Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4.