Решение задач линейного программирования

Во втором уравнении системы  уравнений ставится знак равно, потому что условии задачи сказано, что корм должен содержать ровно 414 единиц микроэлементов.

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

3. Находим целевую функцию задачи, так как цель задачи составление рациона наибольшей калорийности, то

Z(Х)=1+1.6+1.2→max

 

Таким образом, математическая модель имеет вид: составить такой рацион кормления Х=(, удовлетворяющий системе ограничений

 

и условию не отрицательности , при котором целевая функция Z(Х)=+1.6+1.2→max

 

Приводим задачу к каноническому виду.

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

Z(x)=1+1.6+1.2→max

 

 

Строим начальное опорное решение методом Гаусса:

2    4    8    1    0    104

16  24  18   0    0    414   :4

4    8   6    0  -1    120

1  1.6 1.2  0   0     0

2    4    8    1    0    104         

16  24  18   0    0    414              +

1    2  1.5  0  -4    30    *(-2)

1  1.6 1.2  0   0     0

0    0    5    1    8    44

          16  24  18   0    0    414                 +

1    2  1.5  0  -4    30    *(-16)

1  1.6 1.2  0   0     0

0    0    5    1    8    44

          0   -8  -6    0  64   -66                

1    2  1.5  0  -4    30    *(-1)     +

1  1.6 1.2  0   0     0

 

0    0     5    1    8    44

          0   -8   -6    0  64   -66    :8               

1    2   1.5  0  -4    30   

0 -0.4 -0.3 0   4   -30

 

0    0     5    1    8    44

          0    1  0.75  0   -8   8.25 *(-2)   +

1    2   1.5  0  -4    30   

0 -0.4 -0.3 0   4   -30

 

0    0     5    1    8    44

          0    1  0.75  0   -8   8.25  *0.4

1    0    0    0  12  13.5              +

0 -0.4 -0.3 0   4   -30

0    0     5    1     8   44

          0    1  0.75  0    -8   8.25 

1    0    0    0   12    13.5          

0    0    0    0  0.8  -26.7

 

 

Теперь решаем задачу симплексным методом. Составляем первую симплексную таблицу. Б=(x₄;x₂;x₁)

Б				0	0	0
	0		0	0	5	1	8
	0		0	1		0
	0		1	0	0	0
			0	0		0

 

 

 

Проверяем решение на оптимальность

 

₀=     ₃=

 

₁==0                             ₄

 

₂=₅=

 

Так как ₅<0, то решение не оптимальное, следовательно, его можно улучшить. Для этого находим новое опорное решение с помощью «правила прямоугольника».

Так как наименьшее отрицательное  значение₅=-0.8, то ключевым столбцом является столбец А₅; наименьшее значение 5, то ключевой строкой является строка х₁. Рассчитываем новые элементы таблицы:

Новый элемент =44-(13.5*8)/12=35

Новый элемент =0-(1*8)/21=2/3

Новый элемент =5-(0*8)/12=5

Новый элемент =8.25-(-8*13.5)/12=17.25

Новый элемент =0-(-8*1)/12=-(2/3)

Новый элемент =0.75-(-8*0)/12=0.75

 

Получаем новую симплексную  таблицу: Б=(x₄;x₂;x₅)

 

Б				0	0	0
	0			0	5	1	0
	0			1		0
				0	0	0
			0	0		0

 

          Аналогично проверяем решение на оптимальность.

Так как все , то решение оптимальное, следовательно, наибольшее значение Z(Х)=27.6, если x₁=0, x₂=17.25, x₃=0, x₄=35, x₅=1.125.

 

Ответ: максимальное  значение Z(Х)=27.6 при Х=(0; 17.25; 0)

 

5. Вывод

 

Можно составить рацион кормления  наибольшей калорийности в размере 27.6 тыс. ккал., если купить только 17.25 кг комбикорма второго вида. При этом суточный рацион содержит ровно 414 единиц микроэлементов, 104 единицы биостимуляторов и 120 кормовых единиц.

 

ГЛАВА 2 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

2.1. Транспортная задача

 
  Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из А₁,А₂…А_m пунктов отправления в В₁,В₂…В_n пунктов назначения. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Известно C_ij( i=) – стоимость перевозки единиц груза от i-поставщика, j- потребителю, или время, необходимое на перевозку единицы груза. Требуется составить такой план перевозок, при котором:

1. Все запасы поставщика  будут вывезены полностью.

2. Все запросы потребителя  удовлетворены полностью.

3. Суммарные затраты на  перевозку груза минимальны.

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

Условие транспортной задачи задается в виде таблицы:

 

1.Выбираем переменные задачи.

Пусть х_ij () – количество единиц груза, перевозимое от i-го поставщика j-му потребителю, причем х_{ij .}

2.Составляем систему ограничений.

Система будет состоять из уравнений, так как:

а) все запасы поставщиков  должны быть вывезены полностью

 

б) все запросы потребителей должны быть удовлетворены полностью

 

3.Задаем целевую функцию.

Цель задачи осуществить  перевозки с минимальными затратами, поэтому

Z(x) = с₁*x₁ + с₁*x₁ + … + с_m*x_{n .}

 

Таким образом, математическая модель имеет вид:

 составить план перевозки Х = , удовлетворяющий системе ограничений  ,х_ij ( ), обеспечивающий минимум целевой функции Z(x) =.

 

Транспортные задачи делятся  на два класса:

1. Задачи закрытого типа или с правильным балансом  .

2. Задачи открытого типа или с неправильным балансом  делятся на две группы:

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

б) если же запас товара меньше запросов, вводят фиктивного поставщика стоимость перевозок от  фиктивного поставщика потребителю = 0.

 

2.2  Особенности  транспортной задачи с ограничением  на пропускную

       способность

 

Пусть требуется при решении  транспортной задачи ограничить перевозки  от поставщика с номером l и потребителю с номером k. Возможны ограничения двух типов: 1)x_lk≥a; 2)x_lk≤b, где a и b- постоянные величины.

1. Если x_lk≥ a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы k-го потребителя на величину a (зарезервировать перевозку x_lk=а). В полученном оптимальном решении следует увеличить объем перевозки x_lk на величину а.
2. Если x_lk≤b, то необходимо вместо k-го потребителя с запросами b_k ввести двух других потребителей. Один из них с номером k должен иметь запросы b^,_k=b, а другой с номером n+1- запросы b_n+1=b_k-b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c_l(n+1), которая принимается равной сколь угодно большому числу M (M<< 1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как c_l(n+1)=M- самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n+1) останется пустой (x_l(n+1)=0) и объем перевозки x_lk не превзойдет b.

 
      

2.3  Алгоритм  решения транспортной задачи

 

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

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

3. Проверяют решение на оптимальность методом потенциалов.

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

4.Если решение неоптимальное, переходят к новому опорному решению, с помощью построения цикла и возвращаются к пункту 3.

2.4 Методы построения  начального опорного решения

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

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод  северо-западного угла.

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

Распределение груза начинается с верхней левой клетки таблицы. В неё ставится груз величиной  х₁₁=min{a₁;b₁} при этом из дальнейшего рассмотрения исключается или поставщик или потребитель. Затем, из оставшихся клеток таблицы, выбираем верхнею левую клетку, в которую записывают груз величиной:

х_ij = min

 и так далее до тех пор, пока весь груз не будет распределён.

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

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(c_ij).

Как и метод северо-западного  угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется  только одна клетка таблицы, соответствующая  минимальной стоимости:

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