Задача линейного программирования (стр. 1 из 2)

Юридический техникум Рассмотрено и одобрено ПЦК

г. Кропоткин программирования

Председатель ПЦК

Покалицына О.В.

План

чтения лекции по учебной дисциплине

«Математические методы»

Раздел № 2.Линейное программирование.

Тема № 2.1. Виды задач линейного программирования.

Занятие №

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

Время

Место проведения: аудитория.

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

Литература:

1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.

2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001

Учебные вопросы и расчет времени

№п/п	Учебные вопросы	Время, мин	Методические указания
1.2.3.	Задача линейного программирования (ЗЛП). Трудности решения ЗЛП. Классификация задач оптимизации.

1. Вводная часть. Организационный момент. План занятия. Основные требования.

2. Основная часть.

1. Задача линейного программирования (ЗЛП).

Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. В конце 30-х годов целый ряд существенных результатов по линейному программированию был установлен Л.В. Канторовичем.

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

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

2. Трудности решения ЗЛП.

Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения х1, х2,…, xn; вида и количества ограничений на элементы решений.

3. Классификация задач оптимизации.

Задача о рациональном питании (задача о пищевом рационе).

ПОСТАНОВКА ЗАДАЧИ. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃, П₄; стоимость единицы каждого продукта равна соответственно С₁, С₂, С₃, С₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее b_i единиц; углеводов – не менее b₂ единиц; жиров – не менее b₃ единиц. Для продуктов П₁, П₂, П₃, П₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где a_ij (i=1,2,3,4; j=1,2,3) – какие – то определённые числа; первый индекс указывает номер продукта, второй – номер элемента (белки, углеводы, жиры).

продукт	элементы
	белки	углеводы	жиры
П1П2П3П4	A11A21A31A41	A12A22A32A42	A13A23A33A43

Требуется составить такой пищевой рацион (т.е. назначить количества продуктов П₁, П₂, П₃, П₄, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

МАТЕМАТИЧЕСКУЮ МОДЕЛЬ. Обозначим x₁, x₂, x₃, x₄ количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона (обозначим её L): она линейно зависит от элементов решения x₁, x₂, x₃, x₄.

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

Система ограничений:

a₁₁x₁+a₂₁x₂+a₃₁x₃+a₄₁x₄≥b₁

a₁₂x₁+a₂₂x₂+a₃₂x₃+a₄₂x₄≥b₂

a₁₃x₁+a₂₃x₂+a₃₂x₃+a₄₃x₄≥b₃

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x₁, x₂, x₃, x₄.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных x₁, x₂, x₃, x₄, чтобы они удовлетворяли ограничениям – неравенствам и одновременно обращали в минимум линейную функцию этих переменных:

Задача о планировании производства.

ПОСТАНОВКА ЗАДАЧИ. Предприятие производит изделия трёх видов: U₁, U₂, U₃. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b₁ единиц изделия U₁, не мене b₂ единиц изделия U₂ и не мене b₃ единиц изделия U₃. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно b₁, b₂, b₃ единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s₁, s₂, s₃, s₄, причём запасы ограничены числами g₁, g₂, g₃, g₄ единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим a_ij количество единиц сырья вида s_i (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия U_j (j= 1, 2, 3). Первый индекс у числа a_ij – вид изделия, второй – вид сырья. Значения a_ijсведены в таблицу (матрицу).

Сырьё	Изделия
	U1	U2	U3
S1S2S3S4	a11a12a13a14	a21a22a23a24	a31a32a33a34

При реализации одно изделие U₁ приносит предприятию прибыль c₁, U₂ – прибыль c₂, U₃ – прибыль c₃. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Элементами решения будут x₁, x₂, x₃ – количества единиц изделий U₁, U₂, U₃, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений – неравенств: x₁³b₁, x₂³b₂, x₃³b₃.

Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения – неравенства: x₁£b₁, x₂£b₂, x₃£b₃.

Целевая функция: L=c₁x₁+c₂x₂+c₃x₃→ max.

Система ограничений:

a₁₁x₁+a₂₁x₂+a₃₁x₃£¡₁.

a₁₂x₁+a₂₂x₂+a₃₂x₃£¡₂.

a₁₃x₁+a₂₃x₂+a₃₃x₃£¡₃.

a₁₄x₁+a₂₄x₂+a₃₄x₃£¡₄.

Задача о загрузки оборудования.

ПОСТАНОВКА ЗАДАЧИ. Ткацкая фабрика располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: T1, T2, T3, но с разной производительностью. Данные a_ijпроизводительности станков в таблице (первый индекс – тип станка, второй – вид ткани).

Каждый метр ткани вида T1 приносит фабрике доход c₁, вида Т2 – доход с₂, Т3 – доход с₃.

Тип станка	Вид ткани
	Т1	Т2	Т3
12	а11а21	а12а22	а13а23

Фабрике предписан план согласно которому она должна производить в месяц не менее b₁ метров ткани Т1, b₂ метров ткани Т2, b₃ метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно b₁, b₂, b₃ метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3, чтобы суммарный месячный доход был максимален.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Введём букву x с двумя индексами (первый – тип станка, второй – вид ткани). Всего будет шесть элементов решения: x₁₁x₁₂x₁₃x₂₁x₂₂x₂₃ .

Здесь x₁₁ – количество станков типа 1, занятых изготовлением ткани Т1, x₁₂ – количество станков типа 1, занятых изготовлением ткани Т2 и т.д.