Виды линейного программирования. Решение задач линейного программирования графическим методом

Аннотация: Данная лекция раскрывает ряд вопросов, посвященных линейному программированию как одному из разделов математического программирования; в частности, формулирует основные виды задач линейного программирования, раскрывает отличия данных задач от классических задач математического анализа; знакомит с различными формами записи данных задач, осуществляет их постановку и исследование структуры. Наиболее полно раскрыт вопрос о решении задач линейного программирования симплекс-методом.

1. Понятие математического программирования

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

Наличие ограничений делает задачи принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

Можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• задачи линейного программирования,
• задачи нелинейного программирования .

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

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин " линейное программирование " возник в результате неточного перевода английского " linear programming ". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского " linear programming " было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая форма задачи имеет вид: найти при условиях

Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме

Т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I 2 = 0 , а в другом - I 1 = 0 .

Задача ЛП в канонической форме.

Линейное программирование

Линейное программирование - математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства , задаваемых системами линейных уравнений и неравенств.

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

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

История

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году .

Задачи

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида :

при условиях

, .

Задача линейного программирования будет иметь канонический вид , если в основной задаче вместо первой системы неравенств имеет место система уравнений :

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств .

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.

Примеры задач

Максимальное паросочетание

Рассмотрим задачу о максимальном паросочетании в двудольном графе : есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией.

Введём переменные , которые соответствуют паре из -того юноши и -той девушки и удовлетворяют ограничениям:

с целевой функцией . Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Максимальный поток

Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока).

Возьмём в качестве переменных - количество жидкости, протекающих через -тое ребро. Тогда

,

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

Обобщение предыдущей задачи - максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение , где - величина максимального потока, и решить задачу с новой функцией - стоимостью потока.

Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счёт особой структуры уравнений и неравенств.

Транспортная задача

Имеется некий однородный груз, который нужно перевести с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются - количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:

Целевая функция имеет вид: , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица размера . Первый игрок выбирает число от 1 до , второй - от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков ( - число, выбранное первым игроком, - вторым). Нужно найти оптимальную стратегию первого игрока.

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

, , (),

в которой нужно максимизировать функцию . Значение в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

Алгоритмы решения

Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод . Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью . Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.

Первый полиномиальный алгоритм , метод эллипсоидов , был предложен в 1979 году советским математиком Л. Хачияном , разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП - методов внутренней точки , первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году . Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования , разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

См. также

• Графический метод решения задачи линейного программирования

Примечания

Литература

• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М .: «Вильямс», 2006. - С. 1296. - ISBN 5-8459-0857-4
• Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9
• Карманов В. Г. Математическое программирование. - 3-е издание. - М .: Наука, 1986. - 288 с.
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

• - Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
• Вершик А. М. «O Л. В. Канторовиче и линейном программировании »
• Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе ».
• Барсов А. С. «Что такое линейное программирование », Популярные лекции по математике , Гостехиздат, 1959.
• М. Н. Вялый Линейные неравенства и комбинаторика . - МЦНМО , 2003.

Wikimedia Foundation . 2010 .

• Зальтен, Феликс
• Глагов, Мартина

Смотреть что такое "Линейное программирование" в других словарях:

линейное программирование - — линейное программирование Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между… … Справочник технического переводчика

Линейное программирование

Линейное программирование - область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… … Экономико-математический словарь

Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей 8 .

Л.В. Канторович впервые сформулировал такие широко используемые экономико-математические понятия, как оптимальный план, оптимальное распределение ресурсов, объективно обусловленные оценки, указав многочисленные области экономики, где они могут быть применены.

Понятие линейного программирования было введено американским математиком Д. Данцигом, который в 1949 г. предложил алгоритм решения задачи линейного программирования, получивший название «симплексный метод».

Математическое программирование, в которое входит линейное программирование, в настоящее время является одним из направлений исследования операций. В зависимости от вида решаемых задач в нем выделяют такие области, как линейное, нелинейное, дискретное, динамическое программирование и др. Термин «программирование» введен в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу или план работы некоторого экономического объекта.

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

Главным инструментом для решения таких задач является математическое моделирование. При этом сначала строится простая модель, затем проводится ее исследование, позволяющее понять, какие из интегрирующих свойств объекта не улавливаются формальной схемой, после чего за счет усложнения модели обеспечивается большая ее адекватность реальности. Во многих случаях первым приближением к действительности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, являются линейными. Практика показывает, что достаточное количество экономических процессов достаточно полно описывается линейными моделями. Следовательно, линейное программирование как аппарат, позволяющий отыскивать условный экстремум на множестве, заданном линейными уравнениями и неравенствами, играет важную роль при анализе этих процессов.

Линейное программирование получило широкое развитие в связи с тем, что было установлено: ряд задач сферы планирования и управления может быть сформулирован в виде задач линейного программирования, для решения которых имеются эффективные методы. По оценкам специалистов примерно 80–85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

Созданный математический аппарат в сочетании с компьютерными программами, производящими трудоемкие расчеты, позволяет широко использовать модели линейного программирования в экономической науке и практике.

Определение 1 9 . Линейное программирование (ЛП) – это область математического программирования, являющегося разделом математики и изучающего методы поиска экстремальных (наибольших и наименьших) значений линейной функции конечного числа переменных, на неизвестные которой наложены линейные ограничения.

Эта линейная функция называется целевой, а ограничения, которые представляют количественные соотношения между переменными, выражающие условия и требования экономической задачи и математически записываются в виде уравнений или неравенств, называются системой ограничений.

К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой 10:

от n переменных x 1 , x 2 , …, х n при наложенных функциональных ограничениях:

(3.2)

и прямых ограничениях (требовании неотрицательности переменных)

, (3.3)

где a ij , b i , c j – заданные постоянные величины.

В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно.

ЗЛП в более краткой записи имеет вид:

,

при ограничениях:

;

.

Вектор `Х = (x 1 , x 2 , …, х n ) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением ) ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f (`X ), называется оптимальным планом задачи и обозначается f (`X * ), где ` Х * =(x 1 * , x 2 * , …, х n * ).

Еще одна форма записи ЗЛП:

,

где f (`X * ) есть максимальное (минимальное) значение f (С , х ), взятое по всем решениям, входящим в множество возможных решений Х .

Определение 2 11 . Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи.

Для составления математической модели необходимо:

1) обозначить переменные;

2) составить целевую функцию исходя из цели задачи;

3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.

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

Линейное программирование – математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.

Задача линейного программирования (ЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Линейное программирование применяется при решении следующих экономических задач:

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

2. Задач определения оптимального размещения оборудования на морских судах, в цехах.

3. Задача определения оптимального плана перевозок груза (транспортная задача).

4. Задача оптимального распределения кадров.

5. Задач о смесях, диете (планирование состава продукции) и т.д.

3. МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL.

Традиционно наукой управления называют построение детально разработанных моделей, в результате анализа которых принимаются управленческие решения. Сегодня миллионы менеджеров для анализа деловых задач применяют электронные таблицы. Современные электронные таблицы имеют много мощных средств, которые можно использовать для более точного анализа моделей, в результате чего могут приниматься более взвешенные и близкие к оптимальным решения. С учетом все более широкого применения электронных таблиц в процессе управления будущим специалистам необходимо владеть профессиональными навыкам разработки моделей – как «спланировать» чистый рабочий лист так, чтобы получить полезную и практическую модель деловой ситуации, не углубляясь в алгоритмические и математические тонкости расчетов.

Основные этапы создания модели линейного программирования в Excel:

1. Написание и проверка символической модели линейного программирования. Модель записывается на бумаге в математическом виде.

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel.

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ .

С помощью электронных таблиц можно моделировать реальные ситуации и оценивать полученные результаты. Другими словами с помощью электронных таблиц можно делать анализ результатов деятельности и прогнозирования будущих перспектив предприятия. Эти задачи в среде MS Excel дает возможность решать надстройка Поиск решения.

Поиск решения – это надстройка, которая предназначена для оптимизации моделей при наличии ограничений. Она состоит из двух программных компонентов: программы написанной на языке Visual Basic, который транслирует представленную на рабочем письме информацию для внутреннего представления, которая используется другой программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля. Она выполняет оптимизацию и возвращает найденное решение первой программе, которая возобновляет данные на рабочем листе. С помощью ее можно найти оптимальное значение формулы, которая сохраняется в целевой ячейке. Эта процедура работает с группой ячеек, которые непосредственно связанные с формулой в целевой ячейке. Чтобы получить результат по формуле в целевой ячейке, процедура изменяет значение в ячейках, которые влияют на поиск. Для того, чтобы уменьшить множественное число значений, которые используются в модели задачи, применяют ограничение. Эти ограничения могут содержать ссылку на другие ячейки, которые влияют на поиск.

Общий алгоритм работы с надстройкой Поиск решения.

1. В меню Сервис выбрать команду Поиск решения .
2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению . Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению . Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
6. Нажмите кнопку Выполнить .
7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение . Для возобновления входных данных установите переключатель в положение Восстановить исходные значения.
8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс . MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.

Алгоритм роботи з надбудовою Поиск решения.

5. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ ПРОГРАММЫ MS EXCEL.

Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки – 04кг; 0,4кг; 0,3кг; фруктового пюре – 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара – 80кг, патоки – 60кг, фруктового пюре – 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В – 11грн., вида С – 12грн.

Таблица 1

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

15. Аналитические методы. Методы линейного программирования.

15.1. Аналитические методы

На протяжении всей своей эволюции человек, совершая те или иные деяния, стремился вести себя таким образом, чтобы результат, достигаемый как следствие некоторого поступка, оказался в определенном смысле наилучшим. Двигаясь из одного пункта в другой, он стремился найти кратчайший среди возможных путь. Строя жилище, он искал такую его геометрию, которая при наименьшем расходе топлива, обеспечивала приемлемо комфортные условия существования. Занимаясь строительством кораблей, он пытался придать им такую форму, при которой вода оказывала бы наименьшее сопротивление. Можно легко продолжить перечень подобных примеров.

Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

Ответ на первый вопрос получается как результат глубокого изучения проблемы, которую предстоит решить. Выявляется тот параметр, который определяет степень совершенства решения возникшей проблемы. Этот параметр обычно называют целевой функцией иликритерием качества . Далее устанавливается совокупность величин, которые определяют целевую функцию. Наконец, формулируются все ограничения, которые должны учитываться при решении задачи. После этого строится математическая модель, заключающаяся в установлении аналитической зависимости целевой функции от всех аргументов и аналитической формулировки сопутствующих задаче ограничений. Далее приступают к поиску ответа на второй вопрос.

Итак, пусть в результате формализации прикладной задачи установлено, что целевая функция , где множество Х – обобщение ограничений, его называют множеством допустимых решений. Существо проблемы оптимизации заключается в поиске на множестве Х – множестве допустимых решений такого решения
, при котором целевая функцияf достигает наименьшего или наибольшего значения.

Составной частью методов оптимизации является линейное программирование.

15.2. Основные понятия линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

Линейное программирование - это раздел математики, ориентированный на нахождение экстремума (максимума или минимума) в задачах, которые описываются линейными уравнениями. Причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (переменные) условия ограничений на входные параметры. Необходимым условием задач линейного программирования является обязательное наличие ограничений на ресурсы (сырье, материалы, финансы, спрос произведенной продукции и т.д.). Другим важным условием решения задачи является выбор критерия останова алгоритма, т. е. целевая функция должна быть оптимальна в некотором смысле. Оптимальность целевой функции должна быть выражена количественно. Если целевая функция представлена одним или двумя уравнениями, то на практике такие задачи решаются достаточно легко. Критерий останова алгоритма (или критерий оптимальности) должен удовлетворять следующим требованиям:

быть единственным для данной задачи;

измеряться в единицах количества;

линейно зависеть от входных параметров.

Исходя из вышесказанного, можно сформулировать задачу линейного программирования в общем виде:

найти экстремум целевой функции

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

и условиях неотрицательности входных параметров:

В краткой форме задача линейного программирования может быть записана так:

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

Задачи линейного программирования можно решить аналитически и графически.

15.3. Каноническая задача линейного программирования

, i=1,…,m,

, j=1,…,n.

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

15.4. Общая задача линейного программирования

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

при ограничениях

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

целевая функция

при условиях-ограничениях: