1. Математическая постановка задачи

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

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

Критерий оптимальности должен удовлетворять следующим требованиям:

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

2. количественно измеряться;

3. линейная зависимость между различными неизвестными величинами (переменными).

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

1. Математическая модель в общем виде

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

найти максимальное (минимальное) значение целевой функции

F(х) =c₁х₁=_c2х2+…+c_nх_nmaх (min)

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

a₁₁х₁+a₁₂х₂+…+a_1nх_n=b₁;

a₂₁х₁+a₂₂х₂+…+a_2nх_n=b₂;

………………………….

a_m1х₁+a_m2х₂+…+a_mnх_n=b_m,

неравенств

a₁₁х₁+a₁₂х₂+…+a_1nх_nb₁;

………………………….

a_k1х₁+a_k2х₂+…+a_knх_nb_k

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

х₁0, х₂0, … , х_n0.

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

при условии

, j=1, 2, …, m х  0, i =1, n.

Здесь х₁, х₂, …, х, …, х_n являются переменными, а коэффициенты c₁, c₂, …, c_n; a₁₁, …, a_mn; b₁, …, b_m – числа, которые могут быть положительными, отрицательными или равными нулю. В матричной форме эта задача записывается следующим образом:

cх  maх;

Aх   b, х  0.

1. Математическая модель в цифровом выражении

В пекарне для выпечки четырех видов хлеба используется мука двух сортов, маргарин и яйца. Имеющееся оборудование, производственные площади и поставки продуктов таковы, что в сутки можно переработать не более 380 кг муки I сорта, 200 кг муки II сорта, 90 кг маргарина, 1880 штук яиц. В таблице1 приведены нормы расхода продуктов, а также прибыль от продажи 1 кг хлеба каждого вида.

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

Таблица 1

Наименование продукта	Нормы расхода на 1 кг хлеба (по видам)
	1	2	3	4
Мука I (кг)	0,5	0,5	0	0

Мука II (кг)	0	0	0,5	0,5
Маргарин (кг)	0,125	0	0	0,125
Яйцо (шт)	2	1	1	1
Прибыль	14	12	5	6

Обозначим через x₁, x₂, x₃, x₄ виды хлебной продукции соответственно видам 1, 2, 3, 4. Целевая функция будет выглядеть следующим образом: L=14*x₁+12*x₂+5*x₃+6*x₄maх, где коэффициенты будут соответствовать прибыли от данного вида хлебного изделия. Ограничительные условия по имеющемуся оборудованию, производственным площадям и поставки продуктов будут следующими:

т.к. на изготовление первого вида хлеба уходит 0,5 кг и второго вида 0,5 кг муки I сорта, а переработать в сутки можно не более 380 кг муки I сорта, то составим следующее неравенство:

0,5*x₁+0,5*x₂ 380

т.к. на изготовление третьего вида хлеба уходит 0,5 кг и четвертого вида 0,5 кг муки II сорта, а переработать в сутки можно не более 200 кг муки II сорта, то составим следующее неравенство:

0,5*x₃+0,5*x₄200

т.к. на изготовление первого вида хлеба уходит 0,125 кг и четвертого вида 0,125 кг маргарина, а переработать в сутки можно не более 90 кг маргарина, то составим следующее неравенство:

0,125*x₁ 0,125*x₄90

т.к. на изготовление первого вида хлеба уходит 2 шт., второго вида 1шт., третьего вида 1шт., четвертого вида 1 шт. яиц, а переработать в сутки можно не более 1880 шт. яиц, то составим следующее неравенство:

2*x₁ +x₂ +x₃ +x₄1880,

где x10, x20, x30, x40.