·  математические модели большого числа экономических задач линейны относительно искомых переменных;

   ·  данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;

   ·  многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

   Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

   В общем виде модель записывается следующим образом:

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

   ·  ограничения:

   ·  требование неотрицательности:

   При этом a_ij, b_i, c_j (   ) - заданные постоянные величины.

   Задача  состоит в нахождении оптимального значения функции (1.2) при соблюдении ограничений (1.3) и (1.4).

   Систему ограничений (1.3) называют функциональными ограничениями задачи, а ограничения (1.4) - прямыми.

   Вектор  , удовлетворяющий ограничениям (1.3) и (1.4), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (1.2) достигает своего максимального (минимального) значения, называется оптимальным [10].

1.3. Алгоритм симплекс-метода

 

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

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

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

    Второй  столбец - коэффициенты целевой функции, соответствующие векторам, входящим в базис.

    Третий  столбец - компоненты опорного плана. В дополнительной строке в этом столбце пишется величина . Её легко вычислить перемножая числа из второго столбца и третьего столбца и складывая их.

    Далее идут столбцы, соответствующие всем векторам , и в этих столбцах записываются координаты этих векторов в рассматриваемом базисе. Заметим, что для векторов, входящих в базис, эти координаты имеют вид (0,0, ... ,0,1,0, ..., 0), где единица стоит в той строке, где находится сам этот базисный вектор. В дополнительной строке сверху обычно выписывают коэффициенты , соответствующие этим векторам. В дополнительной строке снизу пишутся величины , вычисляемые по формулам:

     .

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

    Далее идут следующие этапы, связанные  с преобразованием этой таблицы. При ручном счете каждый раз эту  таблицу лучше переписывать заново, при счете на ЭВМ (который, естественно, всегда используется при решении практических, а не учебных задач), эта таблица просто преобразуется в памяти ЭВМ.

Этап 1

Просматривается дополнительная строка снизу, где записаны разности .

Этап 2

Если  есть столбцы, где  , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис.

Пусть , то есть в базис надо вводить вектор . Назовем столбец, соответствующий этому вектору, направляющим столбцом. В дальнейшем мы будем направляющий столбец помечать символом .

Этап 3

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

 

Пусть этот минимум достигается для вектора

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

 

 

Этап 4

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

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

.

Остальные элементы этой строки заполняются величинами

.

Обратите  внимание на особую роль элемента , стоящего на пересечении направляющей строки и направляющего столбца. Именно на него делятся все бывшие элементы направляющей строки. На месте бывшего элемента автоматически появляется единица.

Написанные  выше формулы для пересчета элементов  направляющей строки можно записать следующим правилом:

.

Этап 5

Далее начинается пересчет всех остальных  строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент  плана

;

для координат  разложения по базису

;

для дополнительной строки

.

Обратите  внимание на то, что все эти формулы по сути дела строятся по одному правилу

.

    Это правило применимо и к компонентам плана, и к величинам , и к разностям . Его даже можно использовать для пересчета элементов самого направляющего столбца, хотя проще заполнить его нулями, оставив

      

 

 

 Далее итерации продолжаются.[3]

1.4. Метод полного исключения Жордана

 

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

   Производят  такие преобразования, в результате которых в каждой строке и в каждом столбце матрицы системы линейных алгебраических уравнений остаются по одному неизвестному с коэффициентами, равными единице, т. е. фактически получают решение системы. Например, необходимо исключить переменную x_s из всех строк за исключением i-й. Коэффициент a_is, стоящий перед переменной x_s, называют генеральным элементом, i-ю строку и 5-й столбец—разрешающими. Прежде всего разрешающую строку делят на a_is и она остается без изменения. Чтобы исключить переменную x_s из первого уравнения, умножают разрешающую строку на — a_is и складывают с первой строкой. В результате получают первую строку с нулевым элементом на месте a_is. Аналогично исключают x_s в остальных строках. Получают эквивалентную запись системы алгебраических уравнений. В ней i-я строка имеет прежний вид, но все коэффициенты у нее поделены на a_is; 5-й столбец состоит из нулевых элементов (кроме единичного, стоящего в /-й строке). Остальные элементы матрицы системы и столбец свободных переменных пересчитывают по правилу прямоугольника. Например, новое значение элемента, а новое значение элемента столбца свободных членов 

     
 

      

    Из  правила прямоугольника следует, что  когда в разрешающей строке (столбце) есть нулевые элементы, то элементы столбцов (строк), пересекающих эти нулевые элементы, остаются без изменения.[1] 

 

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

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

   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 n-часов в день, участка В - 72 n-часа и участка С - 10 n-часов.

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

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

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