Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
КР по МОР.doc
Скачиваний:
8
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

Задание для решения в аудитории

Решить задачи симплекс- методом.

1. Косметическая фирма выпускает два вида кремов для рук из шести ингредиентов. Для первого вида крема количество ингредиентов 2, 8, 0, 3, 1, 6; а для второго вида – 3, 7, 3, 0, 2, 3. Запасы фирмы выглядят следующим образом 18, 56, 15, 18, 6, 18. Составить такой производственный план, при котором будет получена максимальная прибыль, если первый крем стоит 10 у. д. е, а второй – 12 у. д. е., причем необходимо представить к продаже оба крема.

2. Оружейный завод выпускает два вида ружей, которые должны обрабатываться на пяти разных станках. При чем, первый вид ружья должен обрабатываться на 1-ом станке 2 часа, 2-ом – 1 час, 3-м – 2 часа, 4-м – 4 часа, 5-м – 2 часа, а второй вид – 4, 1, 1, 3, 3 часов соответственно. Станки в течение дня могут работать определенное количество часов: 1-й – 20 часов, 2-й – 6 часов,3-й – 10 часов, 4-й – 15 часов, 5-й – 9 часов. Составить план производства ружей, при котором количество выходящих единиц оружия максимально.

3. В итальянской пиццерии есть два вида фирменной пиццы. Нормы затрат продуктов на одну пиццу и запасы пиццерии выглядят следующим образом:

Название продуктов

Затраты на одну пиццу

Запасы

I

II

Колбаса (гр)

200

400

200000

Сыр (гр)

300

100

90000

Грибы (гр)

100

200

80000

Майонез (мл)

100

100

60000

Соус (мл)

200

100

100000

Составит план выпечки пицц для максимализации прибыли, если пицца 1 вида стоит 50 у. д. е, а 2 – 65 у. д. е., причем в ассортименте должны быть обе пиццы.

1.6. Метод искусственного базиса (м – метод)

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

Для того чтобы решить задачу методом искусственного базиса:

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

2. Эти искусственные переменные следует ввести и в целевую функцию Z. В задаче на максимум – с коэффициентом (–М), а в задаче на минимум – с коэффициентом (+М): М(у1; у2, …., ум), где М – очень большое число.

3. Вводят новую линейную целевую функцию и эту функцию обычно записывают в виде двух строк:

.

4. Эти искусственные переменные выводят из базиса, делая их свободными, и потом назад в базис не возвращают, поэтому эти столбцы в новой симплекс-таблице зачеркивают и не рассчитывают.

5. Чтобы определить разрешающий столбец, находят в строке функции М (m+2 строка) наибольший, положительный элемент. Ему соответствует разрешающий столбец. Разрешающую строку ищут как обычно с помощью минимума отношений и переходят к новой симплекс-таблице по обычному алгоритму.

6. После переноса всех искусственных переменных у1, у2, …., уm в свободные, получают допустимое базисное решение. Строка М должна получиться из нулей, и ее отбрасывают.

7. И так как теперь есть допустимое решение, далее задачу можно решать и на максимум, и на минимум.

8. Все остальные элементы симплекс-таблицы вычисляются по правилу прямоугольника.

Пример. Решить систему методом искусственного базиса .

Решение. В первом уравнении нет оснований вводить переменную искусственного базиса, поэтому в нем можно выделить в базис переменную х3. Во второе и третье уравнения введем две искусственные переменные у1 и у2 (для удобства, в правые части уравнений). Таким образом получаем: (х3; y1; y2) – базисные, (х1; х2; x4; x5) – свободные.

Z = 0 – ( – х1 – 2х2) → min.

.

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

Св.

Баз.

х1

х2

х4

х5

b1

х3

3

– 5

2

0

1

у1

– 2

2

– 1

1

4

у2

– 1

3

– 2

1

5

Z

– 1

– 2

0

0

0

М

– 3

5

– 3

2

9

(в строке (m + 2), т. е. в М выбираем наибольший положительный элемент, т. е. 5, так как он максимально «тянет» в положительную сторону функцию цели в задаче на минимум).

.

Переходим к симплекс-таблице № 2.

Св.

Баз.

х1

y2

х4

х5

b1

х3

4/3

– 4/3

5/3

28/3

у1

– 4/3

1/3

1/3

2/3

х2

– 1/3

– 2/3

1/3

5/3

Z

– 5/3

– 4/3

2/3

10/3

М

– 4/3

1/3

1/3

2/3

(В данной таблице значения 1/3 расположены в двух столбцах, поэтому выбираем наиболее для нас удобный).

Симплекс-таблица № 3.

Св.

Баз.

х1

y1

х5

bi

х3

– 4

3

12

x4

– 4

1

2

х2

– 3

1

3

Z

– 7

2

6

М

0

0

0

(После заполнения симплекс-таблицы № 3 мы пришли к строке М, которая является нулевой и ее отбрасывают вместе с у1 и получают первое допустимое базисное решение: столбец bi не отрицателен, поэтому теперь задачу можно решать как на максимум, так и на минимум).

Анализируя строку Z видим, что х5 входит в целевую функцию Z со знаком «+», поэтому продолжаем переход к симплекс-таблице № 4.

.

Симплекс-таблица № 4.

Св.

Баз.

х1

х4

bi

х3

8

– 3

6

x5

– 4

1

2

х2

1

– 1

1

Z

1

– 2

2

.

Симплекс-таблица № 5.

Св.

Баз.

х3

х4

bi

х1

1/8

– 3/8

¾

x5

½

– ½

5

х2

– 1/8

– 5/8

¼

Z

– 1/8

– 13/8

10/8

Так как в строке Z все коэффициенты отрицательные, следовательно, решение оптимальное: Х(3/4; 1/4; 0; 0; 5). Zmin = 10/8.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]