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

Задачи линейного программирования

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

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

1. нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);
2. оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);
3. определение оптимального рациона (оптимизация состава химической смеси);
4. транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);
5. задача о размещении производства (планирование с учётом затрат на производство и транспортировку продукции);
6. задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

Пример построения математической модели задачи

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется три исходных продуктаS1,S2 иS3. Расходы продуктов и запасы этих продуктов на складе приведены в таблице:

Исходный продукт	Расход продуктов (в тоннах на 1 т. краски)		Запас продукта на складе (тонн)
	краска для внутренних работ	краска для внешних работ
S1	10	5	250
S2	20	20	500
S3	5	5	200

Выпуск 1 тонны краски для внутренних работ приносит предприятию прибыль в размере 200 денежных единиц (ден. ед.), для внешних работ — 200 ден. ед. Требуется определить, сколько краски каждого вида следует производить предприятию, чтобы получить максимальный доход (при соблюдении ограничений на ресурсы). 1) Введем переменные задачи: Обозначим x₁— количество производимой краски для внутренних работ;x₂— соответствующее количество краски для наружных работ. 2) Ограничения, которым должны удовлетворять переменные задачи: Учитывая количество каждого вида сырья для производства краски, а также запасы сырья и прибыль, получаемую от выпуска изделий, составим соответствующие ограничения. 3) Целевая функция задачи: Обозначим Zдоход от продажи краски, тогда целевая функция задачи записывается так: Z= 200х₁ + 200х₂ Таким образом, задача состоит в том, чтобы найти максимум целевой функции Z= 200х₁ + 200х₂при ограничениях Это и есть математическая модель задачи.

Практическое занятие №2

Наименование занятия:Решение задач линейного программирования графическим методомЦель занятия: Научиться составлять математическую модель задачи линейного программирования, решать ее графическим методом. Подготовка к занятию: Повторить теоретический материал по теме «Линейное программирование» Литература:

1. Лобачева М.Е. Конспект лекций «Математические методы», 2013г.
2. Агальцов В.П. Математические методы в программировании, 2010г.

Перечень необходимых приборов, инструментов, материалов:ПЭВМ Задание на занятие:Задание 1.Решить задачу линейного программирования графическим методом

Вариант	Вариант
1		6
2		7
3		8
4		9
5		10

Задание 2. Составить математическую модель задачи и решить ее графическим методом Один из цехов предприятия выпускает изделия двух видов: А и В. Для производства этих изделий требуются три вида сырья: S1,S2 иS3. На выпуск изделия А расходуется D1 кгS1, D2 кгS2 и D3 кгS3. На выпуск изделия В расходуется F1 кгS1, F2 кгS2 и F3 кгS3. Запасы ресурсов ограничены: за рабочую смену цех может израсходовать не более G1 кгS1, G2 кгS2 и G3 кгS3. Выпуск изделия А приносит предприятию прибыль в размере Р1 денежных единиц (ден. ед.), изделия В — Р2 ден. ед. Требуется составить оптимальный план работы цеха, т.е. найти, сколько изделий А и изделий В требуется выпускать, чтобы получить максимальную прибыль (при соблюдении ограничений на ресурсы).

Вариант	D1	D2	D3	F1	F2	F3	G1	G2	G3	P1	P2
1	5	10	20	20	5	5	500	250	200	300	100
2	15	10	10	10	10	10	400	200	350	150	250
3	10	15	10	10	15	5	200	400	350	250	150
4	15	15	5	15	5	15	450	250	250	200	200
5	10	20	5	5	20	5	250	500	200	200	200
6	5	15	15	15	5	15	250	250	450	200	200
7	5	15	15	15	15	5	250	400	250	200	200
8	10	15	10	15	10	10	300	300	250	250	150
9	15	10	10	10	10	15	300	250	300	250	150
10	10	10	15	10	15	10	250	300	300	150	250

Порядок проведения занятия:

1. Получить допуск к работе;
2. Выполнить задания в соответствии со своим вариантом;
3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;
2. Выполненное задание;
3. Выводы по результатам выполненного задания;
4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. Какие задачи относятся к задачам линейного программирования?
2. Запишите общий вид задачи линейного программирования.
3. Геометрический метод решения задач линейного программирования, его достоинства и недостатки
4. Как определяется область допустимых решений?
5. Перечислите основные этапы решения задачи ЛПР графическим способом.

ПРИЛОЖЕНИЕ

Источник

Общая, стандартная и основная задачи линейного программирования

Определение 1. Общей задачей ЛП называется задача нахождения максимального (минимального) значения линейной целевой функции (1) при условиях , (2) , (3) , ,(4), где ,,— заданные постоянные величины и. Определение.2. Функция Z называется целевой функцией задачи (1 — 4), —проектными параметрами задачи, а условия (2 — 4) ограничениями данной задачи. Определение 3. Стандартной задачей ЛП называется задача нахождения целевой функции (1) при выполнении условий (2), (4), где k=m,l=n, т.е. когда ограничения заданы только в виде неравенств (2), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют: , , . Определение 4. Канонической (или основной) задачей ЛП называется задача нахождения максимального (минимального) значения функции (1) при выполнении условий (3), (4), где k=0,l=n,mn, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств (2) отсутствуют: , , ,. Определение 5. Совокупность значений проектных параметров , удовлетворяющих ограничениям задачи (2-4), называетсядопустимым решением, или планом. Определение 6. План , при котором целевая функция (1) принимает свое максимальное (минимальное) значение, называетсяоптимальным, т.е. . Все три формы задачи ЛП эквивалентны, ибо каждая из них с помощью некоторых преобразований может быть переписана в форме другой задачи. При этом необходимо пользоваться следующими правилами:

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

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

1. Каждое ограничение-равенство вида (3) можно записать в виде двух неравенств .
2. Переменная , неограниченная условием неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных:,,.

1. Геометрическая интерпретация задачи линейного программирования

Рассмотрим задачу, состоящую в определении максимального значения функции: (5) при условиях , (6) , (7). Эта задача ЛП в стандартной форме с двумя переменными. Каждое неравенство вида (6), (7) геометрически определяет полуплоскость соответственно с граничными прямыми (8). При этом вектор , как градиента функции, указывает ту полуплоскость, которая определяется неравенством, а вектор— полуплоскость, определяемую неравенством. Если система неравенств (6), (7) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Пересечение этих полуплоскостей образует выпуклый многоугольник решений, или область допустимых решений (ОДР). Таким образом, исходная задача ЛП состоит в нахождении таких точек многоугольника решений, в которых целевая функция Z принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст, и на нем целевая функция ограничена. Линейная целевая функция достигает точек экстремума только на границе выпуклого многоугольника. Рассмотрим градиент функции цели . Это будет вектор(см. рис.2.), указывающий направление возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую— const, то её движение параллельно самой себе в направлении вектора приведет к возрастанию функции цели. При этом для допустимости решения эта прямая должна иметь хотя бы одну общую точку с многоугольником решений. Два крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямойна рис.3), и решение исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5).

Источник