Линейное программирование

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

Целью данной работы является ознакомление с линейным программированием. Для достижения цели предстоит решить несколько задач, в соответствии с которыми построена структура работы: следует рассмотреть общую задача линейного программирования ее формулу и геометрическую интерпретацию, а также изучить один из способов решение графический способ.

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

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

Формула задачи

Основная (общая) задача линейного программирования состоит в следующем. Задана система

(1)

m линейных алгебраических уравнений с n неизвестными x1, xn и линейная форма

(2)

относительно этих же неизвестных.

Требуется среди всех неотрицательных решений заданной системы (1) выбрать такое, при котором форма F принимает наименьшее (или наибольшее) значение (минимизируется или максимизируется соответственно).

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

Введем в рассмотрение матрицу, А из коэффициентов при неизвестных в уравнениях (1)

и столбцы

неизвестных и свободных членов этой системы.

Запишем систему линейных алгебраических уравнений (1) в матричной форме:

AX=B (1)

Если теперь через С=(с1, с2,, сn) обозначить строку из коэффициентов при неизвестных, то форму (2) можно представить так:

F=c0+CX (2)

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

Замечание 1. В ряде задач неизвестные x1, xn должны удовлетворять не только равенствам, но и неравенствам. Эти неравенства также называются ограничениями задачи.

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

Определение 2. Всякое неотрицательное решение x1(0), xn (0) системы (1) назовем допустимым решением или планом.

Определение 3. Неотрицательное (допустимое) решение системы (1), минимизирующее (максимизирующее) форму F, назовем оптимальным решением или оптимальным планом.

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

Задача имеет смысл лишь в том случае, когда система (1) совместна.