Историческая справка.

В 1930 году А.Н. Толстым в сборнике «Планирование перево­зок» была изложена методика составления плана перевозок, обеспечивающего наименьший суммарный пробег. По существу, была сформулирована впервые транспортная задача, но при этом не приводилось точных математических формулировок и формальных доказательств. Первая строгая математическая постановка была предложена в 1941 году Ф. Хичкоком, в честь которого эта задача в западной литературе именуется проблемой Хичкока.

В 1931 году венгр Эгервари рассмотрел и решил задачу выбора «Венгерским алгоритмом».

В 1939 году Л.В. Канторович в книге «Математические методы организации и планирования производства» предложил решение задачи по распределению обработки пяти видов материалов между восьмью станками.

Во время второй мировой войны ряд американских ученых и английских математиков был привлечен военным ведомством для решения оперативных стратегических задач. Исследования такого рода известны под названием исследования операций (operations research).

Один из видов операционных исследований – линейное программирование – специальная методика решения класса задач, встречающихся в хозяйственной и вообще оперативной деятельности.

Возникновение методов линейного программирования относят к 1947 году и связано с работами ряда ученых, работающих в ведомстве ВВС США, Дж. Данцинг, М. Вуд, А. Чарнс и др.

В 1949 году Т. Кумпанс в простейшей форме сформулировал транспортную задачу.

В 1948 – 1949 годах математические методы успешно применялись на ленинградских предприятиях.

Дж. Данциг в работе «Максимизация линейной функции переменных ограниченных линейными неравенствами» изложил основы симплексного метода решения линейных оптимизационных задач, экономическое содержание которых изложено в более ранних работах Вуда, Кумпанса. Подробно симплексный метод решения линейных задач изложен в работе А. Чарнса, А. Хендерсона, В. Купера. Кун, Таккер ввели раздел «Линейное программирование», а общие принципы линейного программирования сформулировал англичанин Дж. Мортон.

В начале 50-х годов новая область научных исследований получила наименование «Линейное программирование».

Р. Гомори 1958 год – целочисленное программирование.

1960 год – Лэнд, Дойг, Литтл – метод ветвей и границ (комбинаторный метод решения задач).

Английский экономист Дж. Мортон в 1951 году изложил основные принципы линейного программирования и дал экономическую трактовку проблемам линейного программирования.

Задача планирования производства.

Предприятие планирует выпустить n-видов продукции и при этом предполагает использовать m-видов ресурсов (оборудование, сырье, энергия). Установлено путем изучения рынка, что цена реализации (прибыль c_j) от реализации единицы j-вида продукции j= .Заданы объемы каждого вида ресурсов в количестве b_j: . Известны расходы каждого вида ресурсов на производство единицы каждого вида продукции a_ij. Задача заключается в разработке программы производства продукции (указать сколько и какой вид продукции надо произвести), позволяющей получить максимальную прибыль от ее реализации и удовлетворяющей ограничению по ресурсам.