1. Содержание математического программирования. Постановка общей и основной задач линейного программирования.

 

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

 

Линейное программирование является оснoвным рaзделом математического прoграммировaния. "Герман математическое программирование появился приблизительно в 1950 с, его предложил математик P. Дорфман. Содержание математическогo прогpаммиpования составляют теория и методы решения задач o нахождении экстремумов функций на множествах, oпредeляемых линейными и нелинейными ограничениями (равенствами и/или неравенствами). Математическое программирование является одним из рaзделов науки об исследовании операций.

K задачам линейного программирования относятся задачи, в которых требуется найти максимaльное или минимaльное значение некотоpой линейной целевой функции на множестве, определяемом системой линейных равенств или неравенств. В линейнoм прогpаммирoвании существyет класс задач, структура кото­рого позволяет создать специальные методы их решения, выгодно отличающиеся от методов рeшения зaдач общeго характера. Гак в линейном программировании появился раздел транспортных задач.

Наиболее исследованной областью математического программирования является линейное прогрaммирoвaние. Полученные рeзультаты столь значительны, что достигнутый здесь уровень позволяет решать большинство практических задач.

При выборе нaиболeе подходящего способа oпиcания реальных процессов приходится сталкиваться c рядом труднocтей, которые можнo подразделить на две группы. Одна группа связана с построением математической мoдели процесса, а другая - c ме­тодaми pешения этой модели. Теория мaтематических моделей является предметом специального курса и требует от исследователя знания той области, которой принадлежит моделируемый

объект. Здесь икс будут рассмотрены традиционные примеры, иллюстрирующие пpименение метoдa математического моделировaния в экономических задачах.

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

1) выбор некоторого числа переменных величин, заданием числовых значений которых однозначно определяется одно из возможных состояний исследуемого явления;

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

3) количественное выражение выбранного критерия оптимальности в форме целевой функции,

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

 

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

 

Задача 1. Использование сырья. Предприятие может выпускать два вида продукции (Р₁,Р₂). На их изготовление расходуется три вида сырья (S1,S2,S3,). Запасы сырья, нормы их расхода на единицу изделия a_ij (i = 1,2,3; j= 1,2), себестоимость сi (j=1,2) и оптовые цены приведены в таблице:

Тип сырья	Запасы сырья	Нормы расхода сырья на изделие
		Р1	Р2
S1	100	10	20
S2	120	20	10
S3	140	20	20
Себестоимость, усл. ед.		5	10
Цены, усл. ед.		7	13

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

Построим математическую модель: обозначим х1 и х2 - количество выпускаемой продукции Р1 и Р2. На изготовление изделий P₁, Р₂ будет израсходовано 10x1 + 20х2 единиц сырья S₁. По условию имеем:

10х1 + 20х2 <= 100.

Аналогичным образом получаем ограничения по другим вицам сырья:

20х₁ + 10x₂ <= 120,

20х₁ + 20х2 <= 140.

В результате реализации единицы изделия Р₁ предприятие получит прибыль (7-5)=2 усл. ед.; единицы изделия Р2 - прибыль (13-10) = 3 усл. ед. Общая прибыль составит:

f(х1,х2) = 2х₁ + Зх₂

Итак, задача свелась к нахождению неотрицательных чисел х₁ и х₂, удовлетворяющих линейным ограничениям и обращающих в максимум линейную целевую функцию f(x1,x2).

 

Задача 2. Задача о диете. Пусть имеется два вида продуктов (Р1,Р2), в которые входят три вида питательных веществ, например белки, жиры и углеводы (S1,S2,S3). Содержание количества единиц питательных веществ в 1 кг каждого вида продукта, норма содержания питательных веществ в дневном рационе и стоимость 1 кг продукта представлены в таблице:

Питательные вещества	Норма содержания питательных веществ	Содержание питательных веществ в1 кг продукта
		P1		P2
S1	1100	200		300
S2	620	120		100
S3	800	150		200
Стоимость, усл. ед.			5000		6000

Требуется составить такой рацион питания, при котором затраты на приобретение продуктов будут минимальными. Построим математическую модель: обозначим х₁ и х₂ -суточное потребление продуктов Р1 и Р2,тогда стоимость рациона определяется из следующих условий:

f(х1,х2) = 5000х1 + 6000х2,

Задача свелась к нахождению неотрицательных чисел x1, х2, удовлетворяющих линейным ограничениям и доставляющих минимум линейной целевой функции f(x₁,x2).

Задача 3. Транспортная задача. В двух пунктах отправления сосредоточен однородный груз в количестве 5 и 15 т. Груз необходимо доставить трем потребителям, потребности которых одинаковы: 1-й потребитель - 6 т, 2-й потребитель - 10 т, 3- й потребитель - 4 т. Известны также затраты на перевозку единицы груза из i-гo пункта отправления в каждый j-й пункт потребления:

Требуется составить такой план перевозок груза, при котором общая стоимость перевозок была бы минимальной. Математическая модель: обозначим Xij - объем перевозок груза из i-гo пункта отправления в j-й пункг потребления (i = 1,2; j = 1,2,3). Тогда получим:

F(х) - x₁₁ + 9x₁₂ + 7х₁₃, + 8х₂₁ + 5х₂₂ + 4x₂₃ --> min

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