Главная Коллекция "Otherreferats" Программирование, компьютеры и кибернетика Методы решения задач линейного программирования

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 04.02.2013
Размер файла 1,1 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Содержание

  • 1. Задание 2
  • 2. Задание 3
  • 3. Задание 4
  • 4. Задание 5
  • Список литературы
  • Приложения

1. Задание 2

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

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

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

Х1 + 3Х2 ? 6

Х1 + 2Х2 ? 12

-3Х1 + 2Х2 ? 9

Х1 ? 0, Х2 ?0

Z (х) = -2Х1 + 4Х2

Решение

1. Необходимо найти минимальное значение целевой функции

F = -2x1+4x2 > min,

при системе ограничений:

x1+3x2?6 (1)

x1+2x2?12 (2)

-3x1+2x2?9 (3)

x1?0 (4)

x2?0 (5)

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

Границы области допустимых решений

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

Рассмотрим целевую функцию задачи

F = -2x1+4x2 > min.

Построим прямую, отвечающую значению функции F = 0:

F = -2x1+4x2 = 0.

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

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

Прямая F(x) = const пересекает область в точке E. Так как точка E получена в результате пересечения прямых (4) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

x2=0

x1+2x2?12

Решив систему уравнений, получим: x1 = 12, x2 = 0

Откуда найдем минимальное значение целевой функции:

F(X) = -2*12 + 4*0 = -24

2. Необходимо найти максимальное значение целевой функции

F = -2x1+4x2 > max,

при системе ограничений:

x1+3x2?6 (1)

x1+2x2?12 (2)

-3x1+2x2?9 (3)

x1?0 (4)

x2?0 (5)

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

Рассмотрим целевую функцию задачи

F = -2x1+4x2 > max.

Построим прямую, отвечающую значению функции F = 0:

F = -2x1+4x2 = 0.

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

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

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

x1+2x2?12

-3x1+2x2?9

Решив систему уравнений, получим: x1 = 0.75, x2 = 5.625

Откуда найдем максимальное значение целевой функции:

F(X) = -2*0.75 + 4*5.625 = 21

2. Задание 3

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

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

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

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

3. Провести проверку полученного решения путем подстановки результата в исходную задачу.

Z max = 2X1 + 3X2 + X3

X1 + 2X2 - X3 >= 8

4X1 - X2 + X3 <= 12

X1 + 3X2 - 2X3 <= 22

Xj = 0, j = 1ч3

Решение

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

Определим максимальное значение целевой функции

Z(X) = 2x1 + 3x2 + x3

при следующих условиях-ограничений.

x1 + 2x2 - x3?8

4x1 - 2x2 + x3?12

x1 + 3x2 - 2x3?22

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

В 1-м неравенстве смысла (?) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (?) вводим базисную переменную x5. В 3-м неравенстве смысла (?) вводим базисную переменную x6.

1x1 + 2x2-1x3-1x4 + 0x5 + 0x6 = 8

4x1-2x2 + 1x3 + 0x4 + 1x5 + 0x6 = 12

1x1 + 3x2-2x3 + 0x4 + 0x5 + 1x6 = 22

Введем искусственные переменные x: в 1-м равенстве вводим переменную x7;

1x1 + 2x2-1x3-1x4 + 0x5 + 0x6 + 1x7 = 8

4x1-2x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 = 12

1x1 + 3x2-2x3 + 0x4 + 0x5 + 1x6 + 0x7 = 22

Для постановки задачи на максимум целевую функцию запишем так:

Z(X) = 2x1+3x2+x3 - Mx7 > max

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

x7 = 8-x1-2x2+x3+x4

которые подставим в целевую функцию:

Z(X) = 2x1 + 3x2 + x3 - M(8-x1-2x2+x3+x4) > max

или

Z(X) = (2+1M)x1+(3+2M)x2+(1-1M)x3+(-1M)x4+(-8M) > max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1

2

-1

-1

0

0

1

4

-2

1

0

1

0

0

1

3

-2

0

0

1

0

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

Решим систему уравнений относительно базисных переменных: x7, x5, x6. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,12,22,8)

Базисное решение называется допустимым, если оно неотрицательно.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x7

8

1

2

-1

-1

0

0

1

x5

12

4

-2

1

0

1

0

0

x6

22

1

3

-2

0

0

1

0

Z(X0)

-8M

-2-1M

-3-2M

-1+1M

1M

0

0

0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (8 : 1 , 12 : 4 , 22 : 1 ) = 8

Следовательно, 1-ая строка является ведущей.

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

x7

8

1

2

-1

-1

0

0

1

8

x5

12

4

-2

1

0

1

0

0

3

x6

22

1

3

-2

0

0

1

0

22

Z(X1)

-8M

-2-1M

-3-2M

-1+1M

1M

0

0

0

0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x1 .

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

8 : 1

1 : 1

2 : 1

-1 : 1

-1 : 1

0 : 1

0 : 1

1 : 1

12-(8 * 4):1

4-(1 * 4):1

-2-(2 * 4):1

1-(-1 * 4):1

0-(-1 * 4):1

1-(0 * 4):1

0-(0 * 4):1

0-(1 * 4):1

22-(8 * 1):1

1-(1 * 1):1

3-(2 * 1):1

-2-(-1 * 1):1

0-(-1 * 1):1

0-(0 * 1):1

1-(0 * 1):1

0-(1 * 1):1

(0)-(8 * (-2-1M)):1

(-2-1M)-(1 * (-2-1M)):1

(-3-2M)-(2 * (-2-1M)):1

(-1+1M)-(-1 * (-2-1M)):1

(1M)-(-1 * (-2-1M)):1

(0)-(0 * (-2-1M)):1

(0)-(0 * (-2-1M)):1

(0)-(1 * (-2-1M)):1

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x6

x7

x1

8

1

2

-1

-1

0

0

1

x5

-20

0

-10

5

4

1

0

-4

x6

14

0

1

-1

1

0

1

-1

Z(X1)

16

0

1

-3

-2

0

0

2+1M

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai4

и из них выберем наименьшее:

min (- , - , 14 : 1 ) = 14

Следовательно, 3-ая строка является ведущей.

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

x1

8

1

2

-1

-1

0

0

1

-

x5

-20

0

-10

5

4

1

0

-4

-

x6

14

0

1

-1

1

0

1

-1

14

Z(X2)

16

0

1

-3

-2

0

0

2+1M

0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x4.

Строка, соответствующая переменной x4 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x4 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x4 и столбец x4.

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

Представим расчет каждого элемента в виде таблицы:

B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

8-(14 * -1):1

1-(0 * -1):1

2-(1 * -1):1

-1-(-1 * -1):1

-1-(1 * -1):1

0-(0 * -1):1

0-(1 * -1):1

1-(-1 * -1):1

-20-(14 * 4):1

0-(0 * 4):1

-10-(1 * 4):1

5-(-1 * 4):1

4-(1 * 4):1

1-(0 * 4):1

0-(1 * 4):1

-4-(-1 * 4):1

14 : 1

0 : 1

1 : 1

-1 : 1

1 : 1

0 : 1

1 : 1

-1 : 1

(2+1M)-(14 * (-2)):1

(0)-(0 * (-2)):1

(1)-(1 * (-2)):1

(-3)-(-1 * (-2)):1

(-2)-(1 * (-2)):1

(0)-(0 * (-2)):1

(0)-(1 * (-2)):1

(2+1M)-(-1 * (-2)):1

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x6

x7

x1

22

1

3

-2

0

0

1

0

x5

-76

0

-14

9

0

1

-4

0

x4

14

0

1

-1

1

0

1

-1

Z(X2)

44

0

3

-5

0

0

2

1M

Окончательный вариант симплекс-таблицы:

Базис

B

x1

x2

x3

x4

x5

x6

x7

x1

22

1

3

-2

0

0

1

0

x5

-76

0

-14

9

0

1

-4

0

x4

14

0

1

-1

1

0

1

-1

Z(X3)

44

0

3

-5

0

0

2

1M

x1 = 22

x5 = -76

x4 = 14

Z(X) = 2*22 = 44

Ответ:

3. Задание 4

Решить задачу линейного программирования распределительным методом, начальное опорное решение, заполнив методом северо-западного угла (диагональным методом).

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

1. Записать экономико-математическую модель задачи.

2. Из последней таблицы записать полученное оптимальное решение.

Задача 6: В специализированном хозяйстве имеется четыре земельных участка площадью 1-250 га, 2-300 га, 3-180 га, 4-370 га. Требуется разместить на этих участках посевы трех зернофуражных культур: ячмень-150 га, овес-200 га, кукуруза на зерно-600 га, чтобы получить максимум валового сбора Урожайность культур по участкам приведены в таблице:

Культуры

Участки

1

2

3

4

Ячмень

18

27

25

20

Овес

14

23

22

17

Кукуруза

25

32

28

27

Решение

1. Экономико - математическая модель задачи

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

,

где - матрица урожайности.

Ограничения по количеству посевных площадей:

Ограничение по необходимому объему культур

2. Решим задачу распределительным методом, опорный план составим методом северо - западного угла.

Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.

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

Урожайность задана таблицей

1

2

3

4

Необходимо

1

18

27

25

20

150

2

14

23

22

17

200

3

25

32

28

27

600

Посевные площади

250

300

180

270

Проверим необходимое и достаточное условие разрешимости задачи.

? a = 150 + 200 + 600 = 950

? b = 250 + 300 + 180 + 270 = 1000

Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 50 (1000-950). Урожайность по всем участкам полагаем равной нулю.

Занесем исходные данные в распределительную таблицу.

1

2

3

4

Необходимо

1

18

27

25

20

150

2

14

23

22

17

200

3

25

32

28

27

600

4

0

0

0

0

50

Посевные площади

250

300

180

270

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

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 18

Для этого элемента запасы равны 150, потребности 250. Поскольку минимальным является 150, то вычитаем его.

x11 = min(150,250) = 150.

18

x

x

x

150 - 150 = 0

14

23

22

17

200

25

32

28

27

600

0

0

0

0

50

250 - 150 = 100

300

180

270

0

Искомый элемент равен 14

Для этого элемента запасы равны 200, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x21 = min(200,100) = 100.

18

x

x

x

0

14

23

22

17

200 - 100 = 100

x

32

28

27

600

x

0

0

0

50

100 - 100 = 0

300

180

270

0

Искомый элемент равен 23

Для этого элемента запасы равны 100, потребности 300. Поскольку минимальным является 100, то вычитаем его.

x22 = min(100,300) = 100.

18

x

x

x

0

14

23

x

x

100 - 100 = 0

x

32

28

27

600

x

0

0

0

50

0

300 - 100 = 200

180

270

0

Искомый элемент равен 32

Для этого элемента запасы равны 600, потребности 200. Поскольку минимальным является 200, то вычитаем его.

x32 = min(600,200) = 200.

18

x

x

x

0

14

23

x

x

0

x

32

28

27

600 - 200 = 400

x

x

0

0

50

0

200 - 200 = 0

180

270

0

Искомый элемент равен 28

Для этого элемента запасы равны 400, потребности 180. Поскольку минимальным является 180, то вычитаем его.

x33 = min(400,180) = 180.

18

x

x

x

0

14

23

x

x

0

x

32

28

27

400 - 180 = 220

x

x

x

0

50

0

0

180 - 180 = 0

270

0

Искомый элемент равен 27

Для этого элемента запасы равны 220, потребности 270. Поскольку минимальным является 220, то вычитаем его.

x34 = min(220,270) = 220.

18

x

x

x

0

14

23

x

x

0

x

32

28

27

220 - 220 = 0

x

x

x

0

50

0

0

0

270 - 220 = 50

0

Искомый элемент равен 0

Для этого элемента запасы равны 50, потребности 50. Поскольку минимальным является 50, то вычитаем его.

x44 = min(50,50) = 50.

18

x

x

x

0

14

23

x

x

0

x

32

28

27

0

x

x

x

0

50 - 50 = 0

0

0

0

50 - 50 = 0

0

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100]

23[100]

22

17

200

3

25

32[200]

28[180]

27[220]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

18*150 + 14*100 + 23*100 + 32*200 + 28*180 + 27*220 + 0*50 = 23780

Этап II. Улучшение опорного плана.

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

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

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Дij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки хij=1 от поставщика Аi к потребителю Вj.

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

Величина Дij называется оценкой свободной клетки (или характеристика).

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

Необходимо вычислить значение оценок Дij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).

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

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

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

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

Следующий этап решения транспортной задачи заключается в улучшении опорного плана.

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

Шаг 1. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27[+]

25

20

150

2

14[100][+]

23[100][-]

22

17

200

3

25

32[200]

28[180]

27[220]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,2; 1,1; 2,1; 2,2; ).

Оценка свободной клетки равна Д12 = (27) - (18) + (14) - (23) = 0.

(1;3): В свободную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Оценка свободной клетки равна Д12 = 0.

1

2

3

4

Необходимо

1

18[150][-]

27

25[+]

20

150

2

14[100][+]

23[100][-]

22

17

200

3

25

32[200][+]

28[180][-]

27[220]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,2; 3,2; 3,3; ).

Оценка свободной клетки равна

Д13 = (25) - (18) + (14) - (23) + (32) - (28) = 2

(1;4): В свободную клетку (1;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27

25

20[+]

150

2

14[100][+]

23[100][-]

22

17

200

3

25

32[200][+]

28[180]

27[220][-]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,4; 1,1; 2,1; 2,2; 3,2; 3,4; ).

Оценка свободной клетки равна

Д14 = (20) - (18) + (14) - (23) + (32) - (27) = -2.

(2;3): В свободную клетку (2;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100]

23[100][-]

22[+]

17

200

3

25

32[200][+]

28[180][-]

27[220]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,3; 2,2; 3,2; 3,3; ).

Оценка свободной клетки равна Д23 = 3.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100]

23[100][-]

22

17[+]

200

3

25

32[200][+]

28[180]

27[220][-]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,4; 2,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д24 = -1.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100][-]

23[100][+]

22

17

200

3

25[+]

32[200][-]

28[180]

27[220]

600

4

0

0

0

0[50]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (3,1; 3,2; 2,2; 2,1; ).

Оценка свободной клетки равна Д31 = 2.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100][-]

23[100][+]

22

17

200

3

25

32[200][-]

28[180]

27[220][+]

600

4

0[+]

0

0

0[50][-]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,1; 4,4; 3,4; 3,2; 2,2; 2,1; ).

Оценка свободной клетки равна Д41 = 4.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100]

23[100]

22

17

200

3

25

32[200][-]

28[180]

27[220][+]

600

4

0

0[+]

0

0[50][-]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,2; 4,4; 3,4; 3,2; ).

Оценка свободной клетки равна Д42 = -5.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[100]

23[100]

22

17

200

3

25

32[200]

28[180][-]

27[220][+]

600

4

0

0

0[+]

0[50][-]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,3; 4,4; 3,4; 3,3; ).

Оценка свободной клетки равна Д43 = -1.

Опорный план является неоптимальным, поскольку имеются положительные оценки клеток (4,1;) равные: (4).

Переход от неоптимального опорного плана к лучшему.

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

Из посевов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 50. Прибавляем 50 к объемам посевов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50]

23[150]

22

17

200

3

25

32[150]

28[180]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

18*150 + 14*50 + 23*150 + 32*150 + 28*180 + 27*270 + 0*50 = 23980

Шаг 2. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27[+]

25

20

150

2

14[50][+]

23[150][-]

22

17

200

3

25

32[150]

28[180]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,2; 1,1; 2,1; 2,2; ).

Оценка свободной клетки равна Д12 = 0.

(1;3): В свободную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27

25[+]

20

150

2

14[50][+]

23[150][-]

22

17

200

3

25

32[150][+]

28[180][-]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,2; 3,2; 3,3; ).

Оценка свободной клетки равна Д13 = 2.

(1;4): В свободную клетку (1;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27

25

20[+]

150

2

14[50][+]

23[150][-]

22

17

200

3

25

32[150][+]

28[180]

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,4; 1,1; 2,1; 2,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д14 = -2.

(2;3): В свободную клетку (2;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50]

23[150][-]

22[+]

17

200

3

25

32[150][+]

28[180][-]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,3; 2,2; 3,2; 3,3; ).

Оценка свободной клетки равна Д23 = 3.

(2;4): В свободную клетку (2;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50]

23[150][-]

22

17[+]

200

3

25

32[150][+]

28[180]

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,4; 2,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д24 = -1.

(3;1): В свободную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][-]

23[150][+]

22

17

200

3

25[+]

32[150][-]

28[180]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (3,1; 3,2; 2,2; 2,1; ).

Оценка свободной клетки равна Д31 = 2.

(4;2): В свободную клетку (4;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][+]

23[150][-]

22

17

200

3

25

32[150]

28[180]

27[270]

600

4

0[50][-]

0[+]

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,2; 4,1; 2,1; 2,2; ).

Оценка свободной клетки равна Д42 = -9.

(4;3): В свободную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][+]

23[150][-]

22

17

200

3

25

32[150][+]

28[180][-]

27[270]

600

4

0[50][-]

0

0[+]

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,3; 4,1; 2,1; 2,2; 3,2; 3,3; ).

Оценка свободной клетки равна Д43 = -5.

(4;4): В свободную клетку (4;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][+]

23[150][-]

22

17

200

3

25

32[150][+]

28[180]

27[270][-]

600

4

0[50][-]

0

0

0[+]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,4; 4,1; 2,1; 2,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д44 = -4.

Опорный план является неоптимальным, поскольку имеются положительные оценки клеток (2,3;) равные: (3).

Переход от неоптимального опорного плана к лучшему.

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

Из посевов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 150. Прибавляем 150 к объемам посевов, стоящих в плюсовых клетках и вычитаем 150 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50]

23

22[150]

17

200

3

25

32[300]

28[30]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

18*150 + 14*50 + 22*150 + 32*300 + 28*30 + 27*270 + 0*50 = 24430

Шаг 3. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27[+]

25

20

150

2

14[50][+]

23

22[150][-]

17

200

3

25

32[300][-]

28[30][+]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,2; 1,1; 2,1; 2,3; 3,3; 3,2; ).

Оценка свободной клетки равна Д12 = -3.

(1;3): В свободную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150][-]

27

25[+]

20

150

2

14[50][+]

23

22[150][-]

17

200

3

25

32[300]

28[30]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д13 = -1.

1

2

3

4

Необходимо

1

18[150][-]

27

25

20[+]

150

2

14[50][+]

23

22[150][-]

17

200

3

25

32[300]

28[30][+]

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,4; 1,1; 2,1; 2,3; 3,3; 3,4; ).

Оценка свободной клетки равна Д14 = -5.

(2;2): В свободную клетку (2;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50]

23[+]

22[150][-]

17

200

3

25

32[300][-]

28[30][+]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,2; 2,3; 3,3; 3,2; ).

Оценка свободной клетки равна Д22 = -3.

(2;4): В свободную клетку (2;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50]

23

22[150][-]

17[+]

200

3

25

32[300]

28[30][+]

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,4; 2,3; 3,3; 3,4; ).

Оценка свободной клетки равна Д24 = -4.

(3;1): В свободную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][-]

23

22[150][+]

17

200

3

25[+]

32[300]

28[30][-]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (3,1; 3,3; 2,3; 2,1; ).

Оценка свободной клетки равна Д31 = 5.

(4;2): В свободную клетку (4;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][+]

23

22[150][-]

17

200

3

25

32[300][-]

28[30][+]

27[270]

600

4

0[50][-]

0[+]

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,2; 4,1; 2,1; 2,3; 3,3; 3,2; ).

Оценка свободной клетки равна Д42 = -12.

(4;3): В свободную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][+]

23

22[150][-]

17

200

3

25

32[300]

28[30]

27[270]

600

4

0[50][-]

0

0[+]

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,3; 4,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д43 = -8.

(4;4): В свободную клетку (4;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[50][+]

23

22[150][-]

17

200

3

25

32[300]

28[30][+]

27[270][-]

600

4

0[50][-]

0

0

0[+]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,4; 4,1; 2,1; 2,3; 3,3; 3,4; ).

Оценка свободной клетки равна Д44 = -7.

Опорный план является неоптимальным, поскольку имеются положительные оценки клеток (3,1;) равные: (5).

Переход от неоптимального опорного плана к лучшему.

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

Из посевов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 30. Прибавляем 30 к объемам посевов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20]

23

22[180]

17

200

3

25[30]

32[300]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

18*150 + 14*20 + 22*180 + 25*30 + 32*300 + 27*270 + 0*50 = 24580

Шаг 4. Определяем оценку для каждой свободной клетки.

1

2

3

4

Необходимо

1

18[150][-]

27[+]

25

20

150

2

14[20]

23

22[180]

17

200

3

25[30][+]

32[300][-]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,2; 1,1; 3,1; 3,2; ).

Оценка свободной клетки равна Д12 = 2.

1

2

3

4

Необходимо

1

18[150][-]

27

25[+]

20

150

2

14[20][+]

23

22[180][-]

17

200

3

25[30]

32[300]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д13 = -1.

1

2

3

4

Необходимо

1

18[150][-]

27

25

20[+]

150

2

14[20]

23

22[180]

17

200

3

25[30][+]

32[300]

28

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,4; 1,1; 3,1; 3,4; ).

Оценка свободной клетки равна Д14 = 0.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20][-]

23[+]

22[180]

17

200

3

25[30][+]

32[300][-]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,2; 2,1; 3,1; 3,2; ).

Оценка свободной клетки равна Д22 = 2.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20][-]

23

22[180]

17[+]

200

3

25[30][+]

32[300]

28

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,4; 2,1; 3,1; 3,4; ).

Оценка свободной клетки равна Д24 = 1.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20][+]

23

22[180][-]

17

200

3

25[30][-]

32[300]

28[+]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (3,3; 3,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д33 = -5.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20]

23

22[180]

17

200

3

25[30][+]

32[300][-]

28

27[270]

600

4

0[50][-]

0[+]

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,2; 4,1; 3,1; 3,2; ).

Оценка свободной клетки равна Д42 = -7.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20][+]

23

22[180][-]

17

200

3

25[30]

32[300]

28

27[270]

600

4

0[50][-]

0

0[+]

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,3; 4,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д43 = -8.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14[20]

23

22[180]

17

200

3

25[30][+]

32[300]

28

27[270][-]

600

4

0[50][-]

0

0

0[+]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,4; 4,1; 3,1; 3,4; ).

Оценка свободной клетки равна Д44 = -2.

Опорный план является неоптимальным, поскольку имеются положительные оценки клеток (1,2;2,2;) равные: (2).

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

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

Переход от неоптимального опорного плана к лучшему.

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

Из посевов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 150. Прибавляем 150 к объемам посевов, стоящих в плюсовых клетках и вычитаем 150 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20]

23

22[180]

17

200

3

25[180]

32[150]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

27*150 + 14*20 + 22*180 + 25*180 + 32*150 + 27*270 + 0*50 = 24880

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

Из посевов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 20. Прибавляем 20 к объемам посевов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

Необходимо

1

18[150]

27

25

20

150

2

14

23[20]

22[180]

17

200

3

25[50]

32[280]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

18*150 + 23*20 + 22*180 + 25*50 + 32*280 + 27*270 + 0*50 = 24620

Выбираем из альтернативных вариантов (1,2;2,2;) тот, чья функция прибыли будет максимальной: z = 24880.

Шаг 5. Определяем оценку для каждой свободной клетки.

1

2

3

4

Необходимо

1

18[+]

27[150][-]

25

20

150

2

14[20]

23

22[180]

17

200

3

25[180][-]

32[150][+]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,1; 1,2; 3,2; 3,1; ).

Оценка свободной клетки равна Д11 = -2.

1

2

3

4

Необходимо

1

18

27[150][-]

25[+]

20

150

2

14[20][+]

23

22[180][-]

17

200

3

25[180][-]

32[150][+]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,3; 1,2; 3,2; 3,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д13 = -3.

1

2

3

4

Необходимо

1

18

27[150][-]

25

20[+]

150

2

14[20]

23

22[180]

17

200

3

25[180]

32[150][+]

28

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,4; 1,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д14 = -2.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20][-]

23[+]

22[180]

17

200

3

25[180][+]

32[150][-]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,2; 2,1; 3,1; 3,2; ).

Оценка свободной клетки равна Д22 = 2.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20][-]

23

22[180]

17[+]

200

3

25[180][+]

32[150]

28

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,4; 2,1; 3,1; 3,4; ).

Оценка свободной клетки равна Д24 = 1.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20][+]

23

22[180][-]

17

200

3

25[180][-]

32[150]

28[+]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (3,3; 3,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д33 = -5.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20]

23

22[180]

17

200

3

25[180][+]

32[150][-]

28

27[270]

600

4

0[50][-]

0[+]

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,2; 4,1; 3,1; 3,2; ).

Оценка свободной клетки равна Д42 = -7.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20][+]

23

22[180][-]

17

200

3

25[180]

32[150]

28

27[270]

600

4

0[50][-]

0

0[+]

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,3; 4,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д43 = -8.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[20]

23

22[180]

17

200

3

25[180][+]

32[150]

28

27[270][-]

600

4

0[50][-]

0

0

0[+]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,4; 4,1; 3,1; 3,4; ).

Оценка свободной клетки равна Д44 = (0) - (0) + (25) - (27) = -2.

Опорный план является неоптимальным, поскольку имеются положительные оценки клеток (2,2;) равные: (2).

Переход от неоптимального опорного плана к лучшему.

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

Из посевов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 20. Прибавляем 20 к объемам посевов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14

23[20]

22[180]

17

200

3

25[200]

32[130]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

27*150 + 23*20 + 22*180 + 25*200 + 32*130 + 27*270 + 0*50 = 24920

Шаг 6. Определяем оценку для каждой свободной клетки.

1

2

3

4

Необходимо

1

18[+]

27[150][-]

25

20

150

2

14

23[20]

22[180]

17

200

3

25[200][-]

32[130][+]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,1; 1,2; 3,2; 3,1; ).

Оценка свободной клетки равна Д11 = -2.

1

2

3

4

Необходимо

1

18

27[150][-]

25[+]

20

150

2

14

23[20][+]

22[180][-]

17

200

3

25[200]

32[130]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,3; 1,2; 2,2; 2,3; ).

Оценка свободной клетки равна Д13 = -1.

1

2

3

4

Необходимо

1

18

27[150][-]

25

20[+]

150

2

14

23[20]

22[180]

17

200

3

25[200]

32[130][+]

28

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (1,4; 1,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д14 = -2.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14[+]

23[20][-]

22[180]

17

200

3

25[200][-]

32[130][+]

28

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,1; 2,2; 3,2; 3,1; ).

Оценка свободной клетки равна Д21 = -2.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14

23[20][-]

22[180]

17[+]

200

3

25[200]

32[130][+]

28

27[270][-]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (2,4; 2,2; 3,2; 3,4; ).

Оценка свободной клетки равна Д24 = -1.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14

23[20][+]

22[180][-]

17

200

3

25[200]

32[130][-]

28[+]

27[270]

600

4

0[50]

0

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (3,3; 3,2; 2,2; 2,3; ).

Оценка свободной клетки равна Д33 = -3.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14

23[20]

22[180]

17

200

3

25[200][+]

32[130][-]

28

27[270]

600

4

0[50][-]

0[+]

0

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,2; 4,1; 3,1; 3,2; ).

Оценка свободной клетки равна Д42 = -7.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14

23[20][+]

22[180][-]

17

200

3

25[200][+]

32[130][-]

28

27[270]

600

4

0[50][-]

0

0[+]

0

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,3; 4,1; 3,1; 3,2; 2,2; 2,3; ).

Оценка свободной клетки равна Д43 = -6.

1

2

3

4

Необходимо

1

18

27[150]

25

20

150

2

14

23[20]

22[180]

17

200

3

25[200][+]

32[130]

28

27[270][-]

600

4

0[50][-]

0

0

0[+]

50

Посевные площади

250

300

180

270

Цикл приведен в таблице (4,4; 4,1; 3,1; 3,4; ).

Оценка свободной клетки равна Д44 = (0) - (0) + (25) - (27) = -2.

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

Таким образом, последний опорный план является оптимальным.

Максимальная прибыль составит:

27*150 + 23*20 + 22*180 + 25*200 + 32*130 + 27*270 + 0*50 = 24920

Ответ: , z=24920 т.

4. Задание 5

Номер задачи выбирается по последней цифре номера зачетной книжки.

1. Разработать модель конкретной задачи (условие задачи переписывается) в числовой развернутой и матричной форме.

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

3. Решить задачу на ЭВМ в программе Excel "Поиск решения".

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

Задача 6: В опытном хозяйстве установлено, что откорм КРС выгоден только тогда, когда каждое животное получает в суточном рационе не менее 20 кг. к. ед., не менее 2000 г белка и не менее 100 г кальция. Для кормления животных используется сено, силос и концентраты. Содержание указанных питательных веществ в 1 кг корма каждого вида, а также себестоимость 1 кг корма приведены в таблице. Возможности хозяйства позволяют включать в суточный рацион не более 20 кг сена. Составить кормовой рацион минимальной стоимости, учитывающий минимальные суточные нормы потребления питательных веществ и возможности хозяйства по ресурсам.

Таблица.

Виды кормов

Содержание в 1 кг.

Себестоимость 1 кг, ден. ед.

Кормовых единиц

Белка, г

Кальция, г
Сено
Силос

Концентраты

0,5
0,2

1,0
40
10

200
5
4

3
2
1

4
Решение
1. Для начала нам необходимо привести задачу к такому виду, чтобы мы могли определиться с методом ее решения.
Пусть - количество в рационе -го вида корма Матрица содержания питательных веществ - , - стоимость -го вида корма, - необходимая суточная норма питательных веществ
Тогда экономико-математическая модель имеет вид.
Приведем задачу к каноническому виду, для этого представим неравенства в системе ограничений в виде равенств, прибавив либо отняв дополнительные переменные. В целевую функцию эти переменные войдут с нулевыми коэффициентами.
Решим полученную эквивалентную задачу на ЭВМ в программе Excel "Поиск решения".(см. приложение)
В результате получили следующие значения изменяемых переменных:
2. Проведем анализ полученного решения используя двойственные оценки.
Запишем двойственную задачу к исходной задаче.
Решим двойственную задачу на ЭВМ в программе Excel "Поиск решения".(см. приложение)
В результате получили следующие значения изменяемых переменных:
3. Свойства двойственных оценок
Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.
Исходя из полученного решения двойственной задачи можем говорить о дефиците первого вида ресурса, то есть кормовых единиц.
Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса. Теневая цена - это стоимость единицы ресурса в оптимальном решении.
Таким образом при увеличении количества кормовых единиц на 1 кг себестоимость корма возрастет на 4 ден. ед.
Свойство 3. Оценки как инструмент определения эффективности отдельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. Разница между этими величинами (Дj) вычисляется как:
В том случае, если Дj ? 0, вариант производства является выгодным, если Дj < 0 - вариант невыгоден.
В данном конкретном случае имеем:
Таким образом Наименее выгодным является использование в кормовой смеси второго вида корма, то есть силоса.
Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение / показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне; или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести при уменьшении на единицу объема i-го ресурса, если мы хотим, чтобы значение целевой функции не изменилось.
Так как значения всех двойственных переменных кроме одной равны нулю, можем говорить о том что ресурсы не заменяемы.
Таким образом получаем что наиболее выгодным является рацион состоящий из 20 кг сена и 10 кг концентратов. Стоимость корма при этом составит - 80 ден.ед.

Список литературы

1. АстафуровВ.Г., Колодникова Н. - Компьютерное учебное пособие, раздел "Анализ на чувствительность с помощью двойственной задачи", Томск-2002.

2. Алесинская Т.В. - Задачи по исследованию операций с решениями.

3. Ашманов С. А. Линейное программирование. -- М.: Наука. Главная редакция физико-математической литературы, 1981.-- 340 с.

4. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов.-- М.: Высш. шк., 1986.-- 319 с

5. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. -- М.: ИНФРА-М, 2003. -- 444 с. -- (Серия "Высшее образование").

6. Булдаев А.С. Прямые методы решения задачи линейного программирования. - Иркутск, 2000. - 25 с.

7. Булдаев А.С. Двойственные методы решения задачи линейного программирования. - Иркутск, 2000. - 28 с.

8. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. -- 2-е изд., перераб. и доп. -- М.: Финансы и статистика, 2006. - 432 с: ил.

9. Кононов В.А. - Исследование операций. Для продвинутых математиков.

10. Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2002. - 407 с.

11. Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2005. - 128 с.

12. Солодовников А. С., Бабайцев В. А., Браилов А. В. Математика в экономике. Учебник. том 1 - М.: Финансы и статистика, 2000, 224 c.

Размещено на http://www.allbest.ru/

Приложение 1

Рис. 1. Исходные данные

Приложение 2

Рис. 2. Результаты вычислений

Приложение 3

Рис. 3. Исходные данные для двойственной задачи

Приложение 4

Рис. 4. Результаты вычислений для двойственной задачи

Размещено на Allbest.ru


Подобные документы

  • Решение задачи линейного программирования симплекс-методом

    Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

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

    Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

    курсовая работа [132,0 K], добавлен 09.12.2008

  • Применение линейного программирования для решения оптимизационных задач

    Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".

    курсовая работа [2,2 M], добавлен 29.05.2015

  • Решение задач линейного программирования симплекс-методом

    Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.

    курсовая работа [88,9 K], добавлен 11.02.2011

  • Симплекс метод решения задачи линейного программирования

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

    задача [390,4 K], добавлен 10.11.2010

  • Решение задачи линейного программирования графическим методом

    Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.

    курсовая работа [581,5 K], добавлен 13.10.2008

  • Методы решения задач линейного программирования с n-переменными

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

    курсовая работа [678,7 K], добавлен 03.04.2011

  • Специальные задачи линейного программирования

    Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.

    курсовая работа [280,8 K], добавлен 17.11.2011

  • Практикум по решению линейных задач математического программирования

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

    методичка [366,8 K], добавлен 16.01.2010

  • Графический метод решения задачи линейного программирования

    Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.

    контрольная работа [2,0 M], добавлен 02.05.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены