Лекция № 3.Линейное программирование

Содержание учебного плана: примеры моделей операций, приводящих к задаче линейного программирования (ЗЛП); различные виды ЗЛП и их эквивалентность; геометрическая интерпретация решения ЗЛП; основные понятия симплекс-метода решения ЗЛП; симплекс-алгоритм; методы отыскания опорного плана; двойственная ЗЛП; теоремы двойственности; экономическая интерпретация двойственных переменных.

3.1Основные классы теоретических моделей, приводящих к злп

Рассмотрим ряд задач, которые приводят к решению ЗЛП.

3.1.1Задача о диете (задача о смесях)

Исторически одной из первых задач, построенных на решении ЗЛП, являлась задача о диете [Error: Reference source not found]: задача составления наиболее экономного (т.е. наиболее дешевого) рациона питания, удовлетворяющего определенным требованиям. Подобная задача возникает в связи с необходимостью обеспечить питанием большое число людей, например, в армии, санатории и т.п. Аналогичная задача возникает в сельскохозяйственном производстве: животноводстве, птицеводстве и т.д.

Предполагается, что известен перечень доступных продуктов из наименований (хлеб, сахар, соль и т.д.), которые имеют полезных характеристик (потребительских свойств). Для каждого –го продукта известна его медицинская характеристика — удельное содержание –го полезного компонента. Матрицу ={ } ( , ) называют матрицей питательности.

Пусть  — планируемый рацион,  — вектор цен на продукты питания, а  — вектор необходимого содержания полезных компонент. Задачу

9. ,

где =< , >; ={  :  },

называют задачей о диете, или задачей о составлении рациона питания.

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

3.1.2Общая задача планирования выпуска продукции (распределительная задача)

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

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

10. < , > , .

В качестве показателя эффективности обычно выбирается один из экономических показателей хозяйственной деятельности системы, например, общая ценность продукции, которая может быть записана в матричном виде:

11. = = =< , >, = ,

где — прибыльность единицы продукции -го процесса.

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

3. Планирование производства продукции на предприятии.

В плановом году предприятие предполагает выпускать дозиметры типов высшей категории качества, и первой категории качества, которые реализуются по 40, 30 и 60 рублей за изделие. Трудоемкость производства дозиметров задается соотношением 3:2:5. В предплановом году выпуск продукции предприятия характеризовался следующими данными:

2. Отчетные данные в предплановый период.

Производство дозиметров	Среднее количество изделий в смену
Тип	200
Тип	500
Тип	100

Основными компонентами при сборке дозиметра являются датчик того же типа, что и прибор, а также экранированный провод (при сборке каждого дозиметра расходуется одинаковое количество этого материала). В плановом году предполагается поставлять в среднем не более 300, 500, 150 датчиков в сутки соответственно комплектации дозиметров , и . Поставки экранированного провода позволяют выпускать дозиметров не более 1200 единиц в смену. Задача — обосновать напряженные планы производства по объему реализации и ассортименту выпускаемой продукции, если доля высшей категории качества в общем объеме производства (в стоимостном выражении) должна быть не ниже 50 %.

1. Рассмотреть и выполнить этапы постановки проблемы.

Формализовать задачу при КИГ ЛПР:

1. увеличение численности рабочих на предприятии не предполагается;

2. работа производится в две смены.