шення завдань лінійного програмування, що має поліноміальний час виконання. Це - метод внутрішньої точки, що використовує еліпсоїди, вписані в область допустимих значень. Хачиян довів, що час обчислення буде гарантовано менше, ніж поліноміальна функція розмірності задачі та кількості вхідних даних. Однак ступінь полінома, яку він встановив, виявилася занадто високою для того, щоб цей алгоритм можна було використовувати при вирішенні практичних завдань.
Алгоритм індійського математика, Нарендра Кармаркара був важливим розвитком теоретичного висновку Хачіян. Кармаркар показав, як задача лінійного програмування може бути вирішена за поліноміальний час. Крім того, алгоритм Кармаркара був застосуємо для рішення задач лінійного програмування на практиці.
Сучасні пакети для розв'язання задач лінійного програмування суміщають симплекс-метод Данцига з більш сучасними методами внутрішньої точки. Це дозволяє самим останнім варіантам вирішувати завдання, які включають до одного мільярда змінних. Для таких величезних завдань використовуються великі паралельні суперкомп'ютери з більш ніж тисячею процесорів. Але навіть на набагато більш скромних 4-процесорних комп'ютерах задачі лінійного програмування з мільйоном змінних вирішувалися за півгодини, при використанні методів внутрішньої точки.
. Проблеми практичної реалізації. Кількість інформації
Серйозною проблемою при практичному застосуванні лінійного програмування у вирішенні економічних завдань називається великий обсяг інформації, необхідний для передачі даних від суб'єктів господарювання до плануючого органу і назад. Вважається, що наявність грошей дозволяє зменшити ці обсяги, спростити передачу та обробку інформації. На противагу цьому, вважається, що розрахунок у натуральних показниках потребують не тільки великих обчислювальних ресурсів, але і високих вимог до комунікаційних систем.
Зазначена досвідом тенденція - керуючі намагаються полегшити собі життя, перебільшуючи необхідні витрати і одночасно вигоди довгострокових витрат у своїй єпархії. Якщо підрозділи пов'язані між собою через внутрішній план корпорації, а не через ринок, застосуємо той же підхід, що і при соціалістичному плануванні. Але коли справа доходить до відносин між незалежними капіталістичними компаніями, ці тенденції стримуються силами конкуренції (у припущенні, що ринок дійсно конкурентний).
Час від часу капіталістичні фірми теж можуть бажати легкого життя; але якщо вони розслабляються, а ринок легкодоступний для конкурентів, тоді агресивніші фірми включаються в конкуренцію на цьому ринку і, краще використовуючи наявну технологію, можуть підірвати ринкову частку існуючої компанії. Тоді ця компанія буде змушена виробляти більш ефективно під загрозою втрати своєї частки ринку, зниження прибутковості і, в кінцевому рахунку, розорення. Що ж до занадто далекосяжних інвестиційних планів, очевидною додержанням для капіталістичних фірм служить необхідність платити відсоток на кошти, які вони займають для інвестицій, так що сверхінвестіціі були б «самогубством». Так що існують серйозні стимули для реалістичної оцінки передбачуваної прибутковості інвестиційних проектів (зрозуміло, це не означає, що в капіталістичній економіці не приймають постійно помилкових рішень).
У роботі Пола Кокшотта і Алліна Коттрелла «Науков...
