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

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

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

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

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

План

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

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

Раздел № 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	A11 A21 A31 A41	A12 A22 A32 A42	A13 A23 A33 A43

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

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

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

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

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

a ₁₂