Алгоритм симплекс – метода

1. Находим первое опорное решение (угловую точку).

2. Составляем симплексную таблицу (см. рис.3.1).

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

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

5. Направляющая строка (номер выводимой из базиса переменной)  соответствует минимальному из всех соотношений  для положительных значений а_ik. Пусть это l – ая строка.

6. По методу Жордана – Гаусса исключаем переменную Хк из всех ограничений, кроме l –ого, где эта переменная должна быть с коэффициентом 1. Строим, новею симплекс – таблицу.

7. Переходим к этапу 3.

Для поиска первого опорного решения можно использовать следующие методы:

- метод естественного базиса,

- метод искусственного базиса.

Метод естественного базиса применяется для задач линейного программирования, записанных в виде (3.2), где все ограничения неравенства имеют тип "≤" и элементы вектора правых частей ограничений неотрицательны.

                                           (3.2)

В этом случае задачу (3.2) приводим к каноническому виду (3.3), вводя в левую часть каждого ограничения неравенства самостоятельную переменную, которые и будут образовывать естественный базис.

                               (3.3)

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

             (3.4)

 

базис	Сбазис	b	С1	С2	…	Сn
			Х1	Х2	…	Xn
X1базис	С1базис	b1	a11	a12	…	a1n
Х2базис	С2базис	b2	a21	a22	…	a2n
…	…	…	…	…	…	…
Хмбазис	Сmбазис	bm	am1	am2	…	amn
		(Cбазис,b)			…

Рис. 3.1. Симплексная таблица

 

Правила заполнения первой симплексной таблицы

1. Вместо С₁, С₂, …, С_n записываем соответствующие коэффициенты целевой функции.

2. Вместо а_ij записываем коэффициенты при неизвестных из основных ограничений задачи.

3. Вместо Х_i^базис записываем имена переменных, вошедших в базис, в той последовательности, в которой они образуют единичную матрицу.

4. Вместо С_i^базис записываем коэффициенты целевой функции при соответствующих базисных переменных.

5. Вместо b_i записываем элементы вектора правых частей задачи.

6.   

7.

Оптимальное значение переменных соответствует элементам из столбца «b» последней симплексной таблицы, а максимальное значение целевой функции содержимому ячейки (с^базис ,b).

 

 

2.3 Двойственные задачи

 

 

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

Правила построения двойственной задачи.

1. Целевая функция в двойственной задаче меняет своё направление на противоположное.

2. Количество двойственных переменных равно количеству основных ограничений исходной задачи.

3. Двойственная переменная, соответствующая ограничению равенству, является неограниченной по знаку, а соответствующая ограничению неравенству – неотрицательной.

4. Вектор правых частей ограничений исходной задачи является вектором коэффициентов целевой функции в двойственной задаче.

5. Вектор коэффициентов целевой функции исходной задачи является вектором правых частей ограничений в двойственной задаче.

6. Матрица коэффициентов ограничений двойственной задачи – это транспонированная матрица коэффициентов исходной задачи, т.е. строка коэффициентов исходной задачи, является столбцом коэффициентов двойственной задачи.

7. Неотрицательным переменным исходной задачи соответствуют ограничения неравенства в двойственной задаче, причем тип неравенства меняется на противоположный, по сравнению с исходной задачей. А неограниченной переменной исходной задачи соответствует ограничение равенство в двойственной задаче.

Соотношение двойственности является симметричным, т.е. двойственная задача по отношению к двойственной совпадает с исходной.

Если исходная задача линейного программирования записана в стандартном виде:         (с, х)→ max

                                                                            (4.1)

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

         

 

(b, y)→min

                                                                         (4.2)

 

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

      

            3x₁ + 3x₂ – 4x₃ → max

 

 

-2х₁ - х₂ + 3х₃   ≤ -18   у₁

4х₁     -     5 х₃  ≤ 12    у₂   

3х₁ - 2 х₂ + х₃ = 14    у₃

х₁ ≥ 0; х₂≥ 0; х₃ ≥ 0       

 

Вводом двойственные переменные

-18у₁+12у₂+14у₃         min

-2у₁ + 4у₂ + 3у ₃≥ 3

-у₁    - 2у₃  ≥3

3у₁ - 5у₂ + у₃ ≥ -4

у₁ ≥0; у₂≥0    

 

 

 

 

 

3 Раздел

Применение экономико-математического моделирования для обоснования      

плановых прогнозных решений.

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

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

 

Модель 1

 Построить модель на оптимальное сочетание фуражных зерновых, овощей, многолетних трав и молочного скотоводства. Площадь посева многолетних трав должна быть не менее 50 % от площади пашни. Молока произвести не менее 300 ц. Критерий оптимальности – максимум валовой продукции в денежном выражении.

 

Показатели	Приходится на 1 ц				Объем ресурсов
	Зерновых фуражных культур	Овощей	Сена многолет. трав	Молока
1. Пашня, га	0,0323	0,009	0,0165	-	1500
2.Трудовые ресурсы (всего), чел.-ч	0,5	2,3	0,8	5,2	850000
2.Трудовые ресурсы в напр. период, чел.-ч	0,03	0,4	0,02	1,2	28670
4.Корма, ц к.ед.	0,9	0,03	0,2	1,5	-
5.Стоимость продукции, руб.	-	250	-	760

х₁ – валовой сбор зерна

х₂ – валовой сбор овощей

х₃ – валовой сбор многолетних трав

х₄ – валовой сбор молока

 

Целевая функция

250х₂ + 760х₄     мах

 

Ограничения

1) По площади пашни

0,0323х₁ + 0,009х₂ + 0,0165х₃ ≤ 1500

2) По трудовым ресурсам

0,5х₁ + 2,3х₂ + 0,8х₃ + 5,2х₄ ≤ 850000

3) По трудовым ресурсам в напряженный период

0,03х₁ +0,4х₂ + 0,02х₃ + 1,2х₄ ≤ 28670

4) По кормам, ц к. ед.

   0,9х₁ + 0,03х₂ + 0,2х₃ ≥ 1,5х₄

5) По площади посева многолетних трав

0,0165х₃ ≥ 750

6) По производству молока

Х₄ ≥ 300

7) По не отрицательности

х₁ ≥ 0 ; х₂ ≥ 0 ; х₃ ≥ 0 ; х₄ ≥ 0

 

Модель 2

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

 

Вид работы	Себестоимость 1 га работ, руб.				Объем работ, усл. га
	С-80  (2 шт.)	ДТ 54  (10 шт.)	«Беларусь» (5 шт.)	КПД-35  (2 шт.)
Культивация	0,80	1,00	0,90	0,85	1500
Пахота	2,40	3,00	3,40	3,20	2000
Сев	-	-	1,00	0,95	800
Боронование	0,20	0,27	0,25	0,27	700
Сезонная норма работ, усл. га.	1000	1600	1800	600	5000 4750

 

X_ij - V_i производимый j-й машиной

   х₁₁х₁₂х₁₃х₁₄

   х₂₁х₂₂х₂₃х₂₄

 X= х₃₁х₃₂х₃₃х₃₄

   х₄₁х₄₂х₄₃х₄₄

       

 

Целевая функция

0,8х₁₁ + 1х₁₂ + 0,9х₁₃ + 0,85х₁₄ + 2,4х₂₁ + 3х₂₂ + 3,4х₂₃ + 3,2х₂₄ + 1х₃₃ + 0,95х₃₄ + +0,2х₄₁ + 0,27х₄₂ + 0,25х₄₃ + 0,27х₄₄              min

 

Ограничения

1) По виду работ

х₁₁ + х₁₂ + х₁₃ + х₁₄ = 1500

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 2000

х₃₃ + х₃₄ = 800

х₄₁ + х₄₂ + х₄₃ + х₄₄ = 700

2) По марки машин

х₁₁ + х₂₁ + х₄₁ = 1000

х₁₂ + х₂₂ + х₄₂  1600

х₁₃ + х₂₃ + х₃₃ + х₄₃=1800

х₁₄ + х₂₄ + х₃₄ + х₄₄ =600

3) По не отрицательности

 X_ij ≥ 0 i=1, 2, 3 j=1, 2, 3

 

Модель 3

1. Пашня, отведенная под кормовые цели - 490 га, пастбища - 800 га, сенокосы – 300 га.

2. На все поголовье скота необходимо произвести не менее 25000 ц к.ед.

3. Всего в хозяйстве будет 500 голов-коров. В году на 1 голову коровы затрачивается в натуре: концентрированных - от 7 до 12 ц, грубых - от 20 до 30 ц, сочных - от зеленых - от 60 до 100 ц,.

4. Покупные комбикорма составят не более 3000 ц.

5. Сведения о кормовых культурах (в расчете па I га посева)

 

 

Показатели	Зерновые фуражные	Многолетние травы		Однолетние травы на зеленый корм	Силосные	Корнеплоды	Пастбища	Сенокосы
		На сено	На зеленый корм
1. Урожайность, ц с 1 га	27	36	120	26	140	350	100	16
2. Содержание ц. к. ед. в 1 ц корма	1,1	0,5	0,2	0,4	0,2	0,1	0,18	0,45
3. Стоимость материальных затрат, руб.	190	95	100	110	140	450	50	60

 

6. Цепа 1 центнера покупных комбикормов - 19 руб.

7. Критерий оптимальности - минимум суммарных материально-денежных затрат  на создание кормовой базы.

Вводим переменные

х₁ – Площадь зерновых

х₂ – Площадь многолетних трав на сено

х₃ – Площадь многолетних трав на зеленый корм

х₄ – Площадь однолетних трав

х₅ – Площадь под силос

х₆ – Площадь под корнеплоды

х₇ – Площадь под пастбища

х₈ – Площадь под сенокосы

х₉ – Покупной комбикорм

 

Целевая функция

190х₁+95х₂+100х₃+110х₄+140х₅+450х₆+50х₇+6 х₈+ 19х₉                        min

Ограничения

1) По питательности