Основные теоремы линейного программирования

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

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

На рис. 2.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 2.2 - невыпуклое.

рис. 2.1	рис. 2.2

Определение 2. Пересечение конечного числа выпуклых множеств также выпуклое множество.

Определение 3.Точка выпуклого множества называется угловой (или крайней), если через неё нельзя провести ни одного отрезка, состоящего только из точек данного множества и для которого она была бы внутренней.
Для выпуклого многоугольника угловыми точками являются все его вершины. В пространстве выпуклое множество с конечным числом угловых точек называется выпуклым многогранником.

Утверждение 1. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве (исключая случай, когда система несовместна).

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

Ранее говорилось, что ограничениями любой задачи линейного программирования являются либо система линейных уравнений, либо система линейных неравенств. Совокупность решений таких систем при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений - неравенств входят только две переменные x1 и x2 это множество можно изобразить на плоскости (см.3).

Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.

Справедливость этого утверждения иллюстрируется в примере 3.

Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений, и наоборот.

Задания на закрепление

1. Задача об оптимальном использовании ресурсов при производственном планировании.

Общий смысл задач этого класса сводится к следующему.

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b₁, b₂,..., b_m условных единиц.

Известны также технологические коэффициенты a_ij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна c_j.

В планируемом периоде значения величин a_ij, b_i и c_j остаются постоянными.

Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей.

Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов.

Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

Таблица 2.1 - Исходные данные задачи об использовании производственных ресурсов

По данному условию сформулируем задачу линейного программирования.

Обозначим: x₁ - количество выпускаемых ежедневно хоккейных клюшек, x₂ - количество выпускаемых ежедневно шахматных наборов.

Формулировка ЗЛП:

= 2x1 + 4x2 → max;
4x1 + 6x2 ≤ 120, 2x1 + 6x2 ≤ 72, x2 ≤ 10;
x1 ≥ 0, x2 ≥ 0.

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Повторимся, методы решения ЗЛП мы будем рассматривать чуть позднее, а сейчас - пример задачи другого типа.

2. Задача о смесях (планирование состава продукции).

К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов.

На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.

Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.

Представим условие задачи в таблице 2.2.

Таблица 2.2 - Исходные данные задачи о смесях

Сформулируем задачу линейного программирования.

Обозначим: x₁ - количество корма I в дневном рационе птицы, x₂ - количество корма II в дневном рационе птицы.

Формулировка ЗЛП:

= 3x1 + 2x2 → min;
x1 + 4x2 ≥ 1, x1 + 2x2 ≥ 4, x1 ≥ 1; x1 ≥ 0, x2 ≥ 0.

Вопросы для самоконтроля по теме «Линейное программирование»

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

2. Назовите несколько задач из области экономики и менеджмента, которые можно решить методами линейного программирования.

Не нашли, что искали? Воспользуйтесь поиском по сайту: