- •Элементы линейного программирования и транспортная задача рабочая тетрадь студента (-ки) _____ курса ___________________________________ факультета
- •Группы № ________
- •Глава 1. Линейное программирование
- •1.1. Общая задача линейного программирования
- •Задания для решения в аудитории
- •1.2. Графический метод решения задач линейного программирования
- •Задания для решения в аудитории
- •1.3. Анализ моделей на чувствительность (графический метод)
- •Задание для решения в аудитории
- •1.4. Симплекс-метод решения задач линейного программирования
- •Задание для решения в аудитории
- •1.6. Метод искусственного базиса (м – метод)
- •Задание для решения в аудитории
- •1.7. Двойственные задачи линейного программирования
- •Задание для решения в аудитории
- •Раздел 2. Транспортные задачи линейного программирования
- •2.1. Постановка транспортной задачи
- •2.2. Построение исходного допустимого плана в транспортной задаче методом минимального элемента
- •Задания для решения в аудитории
- •Метод минимального элемента
- •2. 3. Метод потенциалов решения транспортных задач
- •Задание для решения в аудитории
- •Расчетно-графическая работа № 1 «линейное программирование»
- •Задача № 2
- •Решение расчетно-графической работы № 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.
