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

  • ID: 04767 
  • 9 страниц

Фрагмент работы:

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

Задача 6.

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

а) по правилу Крамера

б) матричным способом

Решение:

Вычислим определитель системы

так как..., то система имеет единственное решение.

а) Найдем решение системы по правилу Крамера

б) решим систему матричным способом.

Вычислим алгебраические дополнения:

Тогда обратная матрица равна

Решение системы в матричной форме запишется так:

Решения, найденные двумя способами совпадают.

Ответ:.........

Задача 18.

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

Решение: Выпишем расширенную матрицу системы:

С помощью элементарных преобразований приведем расширенную матрицу В к треугольному виду.

~

Последней матрице соответствует следующая система уравнений

В данном примере выберем за базисные переменные -...и..., за свободную переменную.... Выразим базисные неизвестные через свободную, получим общее решение системы уравнений:

Найдем частное решение СЛАУ:...

Базисное решение имеет вид:...

Ответ: общее решение СЛАУ...

частное решение СЛАУ:..., базисное решение СЛАУ:...

Задача 27.

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

Решение:

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

=...

=...

=...

Построим вектор С = (1, 1) и целевую функцию по уравнению:

=...

На рис. 1 видно, что оптимальное решение соответствует точке Е, лежащей на пересечении прямых (1) и (2). Найдем координаты точки Е:

При этом значение целевой функции

Рис. 1. Графическое решение задачи.

Ответ:...

Задача 39.

Проверим, является ли данная транспортная задача закрытой:

и.........

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

Склады потребители запасы

100 12 15 20 14 100 18 200

14 90 8 15 60 11 20 150

20 15 80 25 60 12 10 19 150

потребление 100 90 80 120 110 500

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

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

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

1 2 3 4 5...

100 90 80 120 110

1 200 100 12 15 20 14 100 18 0

2 150 14 90 8 15 60 11 20 0

+ ?

3 150 20 15 80 25 60 12 10 19 1

? +

12 8 24 11 18

Вычислим оценки свободных клеток:

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

Выполним перераспределение груза (перераспределение показано стрелочками). Получим новый опорный план.

1 2 3 4 5...

100 90 80 120 110

1 200 100 12 15 20 14 100 18 0

+ ?

2 150 14 90 8 60 15 11 20 ?9

3 150 20 15 20 25 120 12 10 19 1

? +

12 17 24 11 18

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

Проверим найденное решение на оптимальность.

Проверим условия оптимальности для незаполненных клеток:

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

Выполним перераспределение груза. Получим новый опорный план.

1 2 3 4 5...

100 90 80 120 110

1 200 100 12 15 20 20 14 80 18 0

2 150 14 90 8 60 15 11 20 ?5

3 150 20 15 25 120 12 30 19 1

12 13 20 11 18

Проверим условия оптимальности для незаполненных клеток:

Условия оптимальности выполнены для всех клеток. Следовательно, построенный план оптимален.

Ответ:......

Задача 46.

Составить экономико-математическую модель. Найти решение задачи линейного программирования при помощи средств Excel на ПК.

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

Материал Фонд материалов Нормы расходов

П1 П2 П3 П4

М1 50000 0,7 0,9 1,5 2,3

М2 28000 1,4 0,3 0,7 2,5

М3 40000 0,5 2,1 1,8 0,7

Прибыль 5 7 6 9

Решение:

Введем следующие обозначения:

x1 - нормы расходов для изготовителя П1

x2 - нормы расходов для изготовителя П2

x3 - нормы расходов для изготовителя П3

x4 - нормы расходов для изготовителя П4

Используя данные таблицы, определим необходимое количество каждого вида расходов при работе предприятий с каждым материалом х = (х1, х2, х3, х4):

М1 = 0,7х1 + 0,9х2+1,5х3 + 2,3х4

М2 = 1,4х1 + 0,3х2+0,7х3 +2,5х4

М3 =0,5х1 + 2,1х2+1,8х3 +0,7х4

Так как работа предприятия не должна превышать фонда материалов, то имеем следующие ограничения

0,7х1 + 0,9х2+1,5х3 + 2,3х4 ? 50000

1,4х1 + 0,3х2+0,7х3 +2,5х4 ? 28000

0,5х1 + 2,1х2+1,8х3 +0,7х4 ? 40000

Кроме того также должны выполняться условия неотрицательности переменных х1, х2, x3, x4, т.е. х1 ? 0, х2 ? 0, x3? 0, x4? 0.

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

Если обозначить функцию прибыли через f, то:

f = 5х1 +7х2+6х3 + 9х4

а основная цель может быть выражена так: максимизировать целевую функцию

f = 5х1 +7х2+6х3 + 9х4

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

Найти неизвестные значения переменных х1, х2, x3, x4, удовлетворяющие ограничениям

0,7х1 + 0,9х2+1,5х3 + 2,3х4 ? 50000

1,4х1 + 0,3х2+0,7х3 +2,5х4 ? 28000

0,5х1 + 2,1х2+1,8х3 +0,7х4 ? 40000

х1 ? 0, х2 ? 0, x3? 0, x4? 0.

и доставляющие максимальное значение целевой функции

f = 5х1 +7х2+6х3 + 9х4 ? max.

Решим эту задачу с помощью Excel.

В итоге получаем следующее:

П1 -...

П2 -...

П3-...

П4-....

При этом прибыль составит:...ден.ед.