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

  • ID: 00538 
  • 6 страниц

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

Вариант 8. Решите графическим методом задачу линейного программиро…

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

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

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.1).

=...

=...

=...

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

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

Целевую прямую можно построить по уравнению:

Строим вектор... из точки (0;0) в точку (2,3). Точка B- это последняя вершина области допустимых решений, через которую проходит целевая прямая, двигаясь в противоположном направлении вектора.... Поэтому В - это точка минимума ЦФ. Определим координаты точки В из системы уравнений прямой ограничений (1) и осью ОХ

В (0,6; 0)

Минимальное значение ЦФ равно...

Ответ:...

Задача 2.

Некоторая фирма решила приобрести станки- автоматы двух видов А и В. Для их установки фирмой выделена дополнительная производственная площадь - 18 м2, а для закупки - объем инвестиций - 20 млн. руб. Производительная площадь, занимаемая станком каждого вида и производительность в расчете на один станок приведены в таблице 1.

Необходимо:

1) записать ЭММ задачи расчета оптимальной стратегии закупки станков-автоматов. В качестве целевой функции взять общую производительность всех закупленных станков.

2) к данной задаче построить ей двойственную задачу.

3) решить пару симметричных двойственных задач симплексным методом.

Решение:

1) Обозначим через:

- количество приобретаемых станков вида А; а за... - количество приобретаемых станков вида В.

Запишем ограничения задачи:

по дополнительной площади...

по объему инвестиций...

переменные...и...должны удовлетворять условию неотрицательности:............

Целевая функция имеет вид...

Тогда математическая модель задачи имеет вид:

2) Запишем двойственную задачу:

3) решим задачу симплексным методом, для этого задачу 1 приведем к каноническому виду:...

Построим симплекс-таблицу

Базис B 7 10 0 0 Пояснения

=...

разрешающая переменная х2

х2 - в базис

Первая строка разрешающая

х3 - из базиса

разрешающий элемент "3"

0... 20 2 1 0 1

0 -7 -10 0 0

10... 6 1/3 1/3 1/3 0

разрешающая переменная х1

х1 - в базис

вторая строка разрешающая

х4 - из базиса

разрешающий элемент "5/3"

0... 14 5/3 -1/3 -1/3 1

60 -11/3 10/3 10/3 0

10... 16/5 1/5 -2/5 2/5 1/5

7... 42/5 3/5 -1/5 -1/5 3/5

454/5 83/15 12/5 13/5 11/5

В последней строке нет отрицательных элементов, следовательно, полученный план оптимален.

Целевая функция при этом решении принимает значение...

Выпишем итоговые результаты решения задачи.

1. Оптимальная программа выпуска продукции:......, L* =454/5.

2. Оптимальное решение двойственной задачи:..........

Задача 3.

Некоторая фирма для удовлетворения еженедельного спроса на продукции фирмы в пунктах...и...в объемах 55 единиц и 185 единиц создала 4 филиала в пунктах............. Транспортные расходы на доставку единицы продукции от созданного филиала названным потребителям приведены в нижеследующей таблице.

филиалы Мощность

(ед.) Транспортный тариф

До пункта... До пункта...

Филиал... 90 7 9

Филиал... 60 6 7

Филиал... 50 3 1

Филиал... 40 5 2

Необходимо:

1. записать ЭММ задачи доставки продукции фирмы от ее филиалов к потребителям. в качестве целевой функции взять общие транспортные расходы продукции от филиалов фирмы до ее потребителей.

2. построить опорный план методом наименьшего элемента.

3. решить ТЗ методом потенциалов.

Решение: Обозначим количество продукции, перевозимой из i-го филиала в j-й пункт потребления через.... Составим транспортную матрицу задачи

Филиалы...... Мощность филиалов

7 9 90

6 7 60

3 1 50

5 2 40

потребление 55 185 240

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

Задание ограничений

2) построим опорный план методом наименьшего элемента

Филиалы...... Мощность филиалов

7 90 9 90

55 6 5 7 60

3 50 1 50

5 40 2 40

потребление 55 185 240

Опорный план..., найденный методом наименьшего элемента

[ед.товара].

Соответствующая ЦФ (общие затраты на перевозку)

[руб.].

3) Найдем решение ТЗ методом потенциалов

В нашей задаче..., где...- число поставщиков...- количество потребителей. Заполненных клеток в таблице оказалось 5, следовательно план не вырожденный.

Филиалы...

8 9 Мощность филиалов

0 7 90 9 90

+ -

-2 55 6 5 7 60

- +

-8 3 50 1 50

-7 5 40 2 40

потребление 55 185 240

Вычислим потенциалы по формуле:...(для заполненных клеток) и запишем их в таблицу

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

Получаем:...

Условие оптимальности не выполнено для клетки (1; 1). Следовательно, план не оптимален. Выполним перераспределение груза. Получим новую транспортную матрицу

Филиалы...

7 9 Мощность филиалов

0 55 7 35 9 90

-2 6 60 7 60

-8 3 50 1 50

-2 5 40 2 40

потребление 55 185 240

Опорный план соответствующий этой матрице равен:... [ед.товара].

Общие затраты на перевозку:... [руб.].

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

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

Ответ: опорный план...

Затраты на перевозку...[руб.].