Понятие линейного программирования

 

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

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

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

Математическая модель ЗЛП:

при

 

Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов

 

Пусть некоторая производственная единица (цех, завод, объединение и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексами j . Предприятие при производстве этих видов продукции должно ограничиваться имеющими видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Пусть их число равно m, припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчислимая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д.

Примем в качестве такой меры, например, цену реализации (), т.е. - вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов || || называют технологической матрицей и обозначают А:

.

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

Так как - цена реализации единицы j-той продукции, цена реализации единиц будет равна , а общий объем реализации:

.

Это выражение – целевая функция, которую нужно максимизировать.

Так как - расход i-го ресурса на производство единиц j-той продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить () единиц:

Чтобы искомый план Х= был реален, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы выпуска продукции:

, ().

Таким образом, модель задачи о наилучшем использовании ресурсов имеет вид:

Найти:

,

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

(),

, ().

Т.к. переменные входят в функцию Z(X) и систему ограничений только в первой степени, а показатели , , являются постоянными в планируемый период, то задача является задачей линейного программирования.

 

Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий

 

В задаче о наилучшем использовании ресурсов определяется оптимальный план выпуска продукции. Пусть при производстве какого-то общественно необходимого продукта используется n технологий. При этом требуется m видов ресурсов, заданных объемами (). Эффективности, т.е. количество конечной продукции (в рублях), производимой в единицу времени по j-той () технологии, обозначим через . Пусть, далее, - расход i-го ресурса в единицу времени по j-той технологии. В качестве неизвестной величины примем интенсивность использования j-той технологии, т.е. время, в течении которого продукция производится по j-той технологии. Пренебрегая временем переналадок, необходимыми для перехода от одной технологии к другой, получим следующую математическую модель задачи: найти план интенсивностей использования технологий Х= , обеспечивающий максимум выпуска в стоимостном выражении:

,

при ограничениях на лимитируемые ресурсы

(),

и условия неотрицательности

, ().

 

Примеры экономических задач линейного программирования. Задача о смесях

 

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

Модель задачи о наилучшем составе смеси рассмотрим на примере задачи о диете. Имеются пищевые продукты, известные под номерами 1, 2, 3,..., j,..., n. Они содержат различные питательные вещества, обозначаемые номерами 1, 2, 3,..., i,..., m (углеводы, белки, жиры, витамины, микроэлементы и др.). Единица j-го продукта содержит единиц i-го питательного вещества. Для нормальной жизнедеятельности в заданный промежуток времени нужно потреблять не менее единиц i-го питательного вещества. Обозначим через стоимость единицы продукции j-го вида. Требуется выбрать рацион минимальной стоимости, содержащие необходимые количества питательных веществ. План задач – это количества продуктов каждого вида, обеспечивающие необходимое количество питательных веществ при минимальных затратах на исходные продукты.

Математическая модель задачи:

Найти:

,

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

(),

, ().

 

Примеры экономических задач линейного программирования. Транспортная задача

 

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

Задача формулируется так: имеется m пунктов производства, в каждом из которых сосредоточено () единиц однородного продукта. Этот продукт нужно доставить n потребителям, где потребность составляет () единиц. Причем

.

Известны величины - затраты на перевозку единицы продукта из i-го пункта производства в j-тый пункт потребления. Обозначим через количество продукта, перевозимое из i-го пункта производства в j-тый пункт потребления. Матрица С=|| || называется матрицей тарифов

Матрица Х=|| || - матрицей перевозок:

С целью удобства построения математической модели матрицы тарифов и перевозок совмещают в одну, именуемую макетом транспортной задачи:

			...
			... ...
			... ...
...	... ...	... ...	... ...	... ...
			... ...

Математическая модель транспортной задачи: целевая функция, описывающая транспортные затраты,

,

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

();

на спрос потребителей, который должен быть удовлетворен:

();

при условии неотрицательности переменных, исключающем обратные перевозки

(, ).

 

1.9. Основные виды записи задач линейного программирования

 

Определение: Общей задачей линейного программирования называют задачу:

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

();

();

();

();

- произвольные (),

где , , - заданные действительные числа.

Определение: Симметричной формой записи задачи линейного программирования называют задачу:

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

();

();

или задачу

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

();

().

Определение: Канонической формой записи задачи линейного программирования называют задачу:

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

();

().

Рассмотрим еще два вида записи- матричную и векторную.

Введем обозначения: ,

, , ,

где С – матрица-строка; А – матрица системы уравнений, Х – матрица-столбец переменных, - матрица-столбец свободных членов.

Каноническая форма записи примет вид:

или

max Z=CX

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

,

или

, .

Запишем задачу линейного программирования в векторной форме:

, ,..., ,..., .

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

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

, ,

где - скалярное произведение векторов и .

 

1.10. Способы преобразования

 

При необходимости задачу минимизации можно заменить задачей максимизации и наоборот. Для функции одной переменной это утверждение очевидно. В самом деле, если - точка максимума функции y=f(x), то для функции y=-f(x) она является точкой максимума, так как графики функций f(x) и –f(x) симметричны относительно оси абсцисс (рис. 1).

Итак, min f() = max (-f()).

Рис. 1. Графики функций y=f(x) и y=-f(x).

То же самое имеет место в случае функции n переменных:

.