Контрольная работа по "ТВиМС и линейное программирование"

 

 

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

 

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

Берем в таблице 1 клетку с наименьшим показателем стоимости  перевозок. В исходной таблице наименьшая стоимость равна 9 и отвечает клетке (3; 2). В эту клетку дадим максимально возможную поставку. Соответствующая ферма 3 располагает 1000 тоннами овощей, а спрос завода 2 составляет 3250 тонн.  Значит, размер максимально возможной поставки равен 1000 тонн. Неудовлетворенный спрос завода 2: 3250 – 1000 = 2250 единиц. Ферма 3 более овощами не располагает (из таблицы вычеркивается соответствующая строка):

 

 

 

 

 

 

	1		2		ai
1	10		15		2000
2	12		12		3000
3	18		9		1000
				1000
bj	2750		3250   2250

 

Из оставшихся для  рассмотрения клеток выбираем клетку с наименьшим показателем стоимости перевозок. Наименьшая стоимость равна 10 и отвечает клетке (1; 1). В эту клетку дадим максимально возможную поставку овощей 2000 тонн. Неудовлетворенный спрос завода 1: 2750 – 2000 = 750 единиц. Ферма 1 более овощами не располагает (из таблицы вычеркивается соответствующая строка):

	1		2		ai
1	10		15		2000
		2000
2	12		12		3000
3	18		9		1000
				1000
bj	2750 750		3250   2250

 

Ферма 2 располагает 3000 тонн овощей, потребность завода 1 составляет 750 тонн. Значит, размер поставки равен 750. Потребность завода 2 составляет 2250 тонн.  Значит, размер поставки равен 2250.

В итоге получаем:

	1		2		ai
1	10		15		2000
		2000
2	12		12		3000
		750		2250
3	18		9		1000
				1000
bj	2750		3250

Число занятых клеток в табл. 6 должно быть равно m + n – 1  = 3+2 – 1 = 4, равенство выполняется, т.е. условие невырожденности выполнено.

Получили исходное опорное  решение.

Стоимость перевозок  при исходном опорном решении  составляет:

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

Проверим оптимальность  опорного плана.

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

Будем считать, что  . Тогда

    

    

   

    

 

	1		2
1	10		15
		2000
2	12		12
		750		2250
3	18		9
				1000

 

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

  

        

Поскольку все оценки положительные, то план оптимален.

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

 

 

Задача7

 

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

Исходные данные записаны в таблице.

 

№ вар.

а11

а12

а21

а22

а31

а32

b1

b2

b3

c1

c2

f

 

11

7

2

5

6

3

8

14

30

24

-2

5

Min

        

 

Решение:

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

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

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

	0	2
	7	0

Взяв произвольную точку  на одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например, точка О (0; 0): , т.е. полуплоскость, содержащая точку О(0; 0) не является множеством решений неравенства .

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

	0	6
	5	0

Взяв произвольную точку  на одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например, точка О (0; 0): , т.е. полуплоскость, содержащая точку О(0; 0) является множеством решений неравенства .

Для третьего неравенства: строим прямую по двум точкам.

	0	8
	3	0

Взяв произвольную точку  на одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например, точка О (0; 0): , т.е. полуплоскость, содержащая точку О(0; 0) не является множеством решений неравенства .

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

Получили область допустимых решений – треугольник АВС.

Строим вектор-градиент функции  , указывающий направление возрастания функции F: .

Строим прямую - линию уровня функции , перпендикулярную вектору-градиенту.

Так как требуется  найти минимум функции, будем перемещать линию уровня  в направлении, противоположном направлению градиента, до тех пор, пока она не покинет область допустимых значений (треугольник  АBС). Крайняя точка области, в которой линия уровня покидает допустимую область (точка С), является решением задачи.

Крайняя точка С – точка минимума ,  лежит на пересечении прямых и .

Найдем координаты точки С:

      

Координаты точки  .

Подставляя  координаты точки С в функцию , находим

.

Ответ: .

 

 

                    Задача8

 

Найдите решения следующих  матричных игр

Решение:

8	13	8
10	12	10
13	9	9
13	13

Находим минимальный элемент в каждой строке.

   - нижняя цена игры

Находим максимальный элемент в каждом столбце.

     - верхняя цена игры.

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

Задача первого игрока:

Задача второго игрока:

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

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

 

Переменные y₃, y₄, y₅ - базисные.

Первое опорное решение: , . 

Запишем первое опорное решение в симплексную таблицу и проверим его на оптимальность:

	Базисные переменные	1	1	0	0	0
		y1	y2	y3	y4	y5
0	y3	8	13	1	0	0	1
0	y4	10	12	0	1	0	1
0	y5	13	9	0	0	1	1
		-1	-1	0	0	0	0

 

Первое опорное решение не оптимально, так как среди оценок есть отрицательные (-1 и -1). Оценки одинаковые. За разрешающий столбец выберем столбец, соответствующий переменной y₁.

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

 

Вместо переменной y₃ во второе опорное решение войдет переменная y₁.

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

	Базисные переменные	1	1	0	0	0
		y1	y2	y3	y4	y5
0	y3	0		1	0
0	y4	0		0	1
1	y1	1		0	0
		0		0	0		0

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

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

 

Вместо переменной y₄ во второе опорное решение войдет переменная y₂.

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

	Базисные переменные	1	1	0	0	0
		y1	y2	y3	y4	y5
0	y3	0		1
1	y2	0	1	0
1	y1	1		0
		0	0	0			0