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

Свободные переменные: 

Начальное решение:

Х_о ={  =0; х₂=0; х₃=0;х₄=0; х₅ =50 000;  = 20 000; х₇= 25 000}.

Шаг 2. Функция   уже выражена через свободные переменные.

Шаг 3. Проверка решения на оптимальность. Составляем симплекс-таблицу (табл. 3.6).                 

Таблица 3.6

 

 

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

Шаг 4. Получение нового решения.

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

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

Разрешающий элемент а₂₁ = 1.

Составим новую симплекс-таблицу.

Для подсчета элементов новой  симплекс-таблицы по формулам (3.23, 3.24) удобно использовать правило треугольника, наглядно отображающее указанные формулы.

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

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

Новая симплекс-таблица имеет следующий вид (табл. 7): 

 

Таблица 7

Базисные переменные	Коэффициенты при переменных							Свободные члены
	x1	x2	x3	x4	x5	x6	x7
x5	0	1	1	1	1	-1	0	30000
х1	1	0	0	0	0	1	0	20000
x7	0	1	1	0	0	0	1	25000
P	0	-5	-7	-4	0	10	0	200000

 

 

Новое решение имеет вид

Таким образом, прибыль увеличилась  на 200 000 ус. ед. Это решение неоптимально, так как последняя строка содержит отрицательные числа. Продолжаем оптимизацию.

Разрешающий столбец—третий, так как ему соответствует  максимальное по абсолютной величине отрицательное число -7.

Следовательно, третья строка является разрешающей.

Разрешающий элемент: а₃₃ =1.

Перейдем к новой симплекс-таблице (табл. 8).

Таблица 8

Базисные переменные	Коэффициенты при переменных							Свободные члены
	x1	x2	x3	x4	x5	x6	x7
x5	0	0	0	1	1	-1	-1	5000
х1	1	0	0	0	0	1	0	20000
X3	0	1	1	0	0	0	1	25000
P	0	2	0	-4	0	10	7	375000

 

 

Прибыль выросла, но решение X₂ неоптимально, так как в последней строке еще осталось отрицательное число.

Получим новое решение.

Разрешающий столбец —  четвертый, следовательно, переменная х₄ вводится в список базисных переменных.

Разрешающая строка — первая, и переменная х₅ выводится из списка базисных переменных.

Новая симплекс-таблица имеет следующий вид (табл. 9):

Таблица 9

Базисные переменные	Коэффициенты при переменных							Свободные члены
	x1	x2	x3	x4	x5	x6	x7
X4	0	0	0	1	1	-1	-1	5000
х1	1	0	0	0	0	1	0	20000
X3	0	1	1	0	0	0	1	25000
P	0	2	0	0	4	6	3	395000

 

 

Последнее решение является оптимальным, поскольку все числа, стоящие в последней строке, неотрицательны. Это решение единственно, так  как все элементы последней строки, соответствующие свободным переменным х₂, х₅,х₆, х₇, строго положительны.

    

Таким образом, для получения  максимальной прибыли в размере  
395 000 усл. ед. надо распределить средства следующим обраэом:  
20 000 усл. ед. вложить в рекламу на телевидении; 20 000 усл. ед. вложить в рекламу в газетах и 5000 усл. ед. вложить в рекламу, организованную с помощью расклейки объявлений. Рекламу на радио организовывать не следует.

Изложенные выше вычисления проводились для случая, когда  начальное решение является допустимым. Если в начальном решении существуют b_i<0, то допустимое начальное решение можно найти по следующему алгоритму.

Шаг 1. Выражение функции f через свободные переменные.  

Шаг 3. Составление симплекс-таблицы.

Шаг 3. Выбор переменной, вводимой в список базисных переменных.

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

Шаг 4. Выбор переменной, выводимой из списка базисных переменных.

Находят отношения элементов  столбца свободных членов к элементам  разрешающего столбца. Рассматривают  отношения, в которых числитель  и знаменатель отрицательные, и среди них выбирают минимальное. Строка, соответствующая выбранному отношению, напримерq-я, является разрешающей, и переменная, Стоящая в этой строке, выводится из списка базисных переменных. Элемент a_qp, стоящий на пересечении разрешающей строки и разрешающего столбца, является разрешающим элементом.

Шаг 5. По формулам (23) и (24) проводят симплекс-преобразование и переходят к новой симплекс-таблице. Если в новой таблице все свободные члены неотрицательны, то найденное решение является допустимым и следует перейти к шагу 3 алгоритма симплекс-метода, в противном случае – к шагу 2 рассматриваемого алгоритма.

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

5. Двойственная  задача линейного программирования. Экономическая интерпретация

Рассмотрим задачу линейного  программирования следующего вида:

                                                                     (28)

 

 

 

                                                                        (29)

 

В задаче требуется максимизировать  целевую функцию; все ограничения  являются неравенствами со знаком  , все переменные х₁,х₂,...,х_п неотрицательны. Задача содержи n управляющих переменных и т ограничений. Коэффициенты при переменных в целевой функции: c₁,c₂,...,c_n ; свободные члены: b₁, b₂,…, b_m.

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

                                  

В двойственной задаче требуется  найти минимум целевой функции, ограничения – неравенства со знаком   управляющие переменныеy₁, y₂,… ,y_m неотрицательны. Задача содержит m управляющих переменных и n ограничений. Коэффициенты целевой функции задачи b₁,b₂,… ,b_m являются свободными членами исходной ЗЛП, а свободные члены двойственной задачи с₁,с₂,...,с_n – коэффициентами целевой функции исходной ЗЛП. Матрица коэффициентов двойственной задачи транспонирована, т. е.. строки заменены столбцами, а столбцы – строками.

Задачи (28), (29) и (30), (31) называются парой взаимно двойственных задач линейного программирования.

Для двойственных задач верна  следующая теорема.

Теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение х* , то другая также имеет оптимальное решение у* . При этом соответствующие им оптимальные значения целевых функций f* =f(x*) и g =g(y*) равны.

Поясним экономический  смысл двойственной модели. Пусть  в качестве управляющих переменных x_j,  исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами b_i,   – количество ресурсов i-го типа, используемых для изготовления изделий. Через a_ij   обозначено количество ресурсов i-го типа, идущее на изготовление одного изделия j-го вида, (j – прибыль от реализации одного изделия j-го вида). Тогда исходная модель (28), (29) соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.

Пусть предприятие решило прекратить производство изделий и  продать ресурсы, идущие на их изготовление. Обозначим через цены на единицу  ресурсов i-го вида,   Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они нe должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой (30), второе условие – ограничениями (31). В левой части каждого из неравенств (31) стоит прибыль от продажи ресурсов всех типов, идущих на изготовление j-го изделия, в правой части – прибыль от продажи j-го изделия,   Таким образом, двойственная задача (30) – (31) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов. Значения переменных y₁, y₂,… ,y_m часто называют теневыми ценами.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

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