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

  • ID: 05246 
  • 10 страниц

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

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

Задача 10.

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

Задача 12.

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

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

Найдем решение методом Гаусса:

Возьмем за базисные неизвестные... и..., за свободную.... Выразим базисные неизвестные через свободную.

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

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

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

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

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

Задача 21.

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

Решение:

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

=...

=...

=...

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

=...

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

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

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

Ответ:...

Задача 34.

На трех базах......... имеется груз в количестве 200, 240, 160 единиц. Этот груз нужно перевезти в пять...............пунктов в количестве 130, 170, 100, 90, 110 единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов.... Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Решение:

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

и.........

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

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

9 6 100 17 20 11 80 8 200

+ -

13 170 4 9 70 5 7 240

- +

130 6 7 14 10 30 6 160

потребление 130 170 100 90 110 600

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

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

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

Пусть..., тогда находим остальные потенциалы, получаем:

-6...-2

8...10...17...11...8

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

=...

=...

=...

Условия оптимальности не выполнены для клеток (1,2), (2,3), (3,2), (3,3). Следовательно, построенный план не оптимален.

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

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

9 20 6 100 17 11 80 8 200

+ -

13 150 4 9 90 5 7 240

- +

130 6 7 14 10 30 6 160

потребление 130 170 100 90 110 600

Полученное решение имеет вид:...

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

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

Пусть..., тогда находим остальные потенциалы, получаем:

-2...-2

8...6...17...7...8

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

=...

=...

=...

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

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

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

9 120 6 17 11 80 8 200

13 50 4 100 9 90 5 7 240

130 6 7 14 10 30 6 160

потребление 130 170 100 90 110 600

Полученное решение имеет вид:...

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

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

Пусть..., тогда находим остальные потенциалы, получаем:

-2...-2

8...6...11...7...8

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

=...

=...

=...

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

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

Задача 50.

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

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

Вид работ Оборот работ Производительность техники для каждой модели

80 4 3 2 5

60 8 1 5 1

40 1 3 4 2

Стоимость техники 7 2 5 3

Решение:

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

x1 - производительность модели...

x2 - производительность модели...

x3 - производительность модели...

x4 - производительность модели...

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

Вид работ:

= 4х1 + 3х2 + 2х3 + 5х4

= 8х1 + х2 + 5х3 + х4

=...

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

4х1 + 3х2 + 2х3 + 5х4 ? 80

8х1 + х2 + 5х3 + х4 ? 60

х1 + 3х2 + 4х3 + 24 ? 40

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

Целевая функция модели должна выражать основную цель деятельности предприятия: получение наименьшей стоимости тракторов.

Если обозначить функцию себестоимости тракторов через Z, то:

Z = 7х1 + 2х2 + 5х3 + 3х4

а основная цель может быть выражена так:

минимизировать целевую функцию Z =7х1 + 2х2 + 5х3 + 3х4

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

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

4х1 + 3х2 + 2х3 + 5х4 ? 80

8х1 + х2 + 5х3 + х4 ? 60

х1 + 3х2 + 4х3 + 24 ? 40

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

х1, х2, x3, x4 - целые

Z = 7х1 + 2х2 + 5х3 + 3х4? min.

Решим эту задачу с помощью Excel. Введем следующую таблицу, составленную из коэффициентов задачи (таблица 1).

В итоге получаем количество техники каждой модели:

-...... -...... -...... -...

При этом стоимость тракторов составляет:....

Таблица 1. решение задачи с помощью Microsoft Excel.

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