Методы оптимизации систем

 

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

 

Таблица 7 – Метод минимальной стоимости

Пункт	b1	b2	b3	b4	b5	b6	Запас
а1	3	13	19	-	-	30	65
а2	24	-	-	15	11	-	50
а3	-	-	-	-	-	20	20
Потреб	27	13	19	15	11	50
	Транспортные расходы						209

 

Составим целевую функцию:

 

 

Проверим полученный опорный план на невырожденность по формуле 1.3:

 

                                                  (1.3)

Решение:

 

Определим потенциалы поставщиков и потребителя из формулы 1.4:

 

                                                              (1.4)

 

Решение:

 

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

 

                                                    (1.5)

 

Решение:

 

 

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

Ответ: Для того, удовлетворить потребности потребителя, поставщикам необходимо: товар поставщика A₁ распределить по потребителям B₁, B₂, B₃ в количестве 3, 13, 19 соответственно; товар поставщика A₂ распределить по потребителям B₁, B₄, B₅ в количестве 24, 15, 11 соответственно. Общие затраты на доставку все продукции составляют 209 ден. ед.

 

 

2 Решение задач  линейного программирования с  помощью MS Excel

2.1 Решение  задачи симплекс методом с  помощью надстройки MS Excel «Поиск решения»

Торговое предприятие  для продажи товаров вида А, В, С использует ресурсы: торговая площадь (общий объем b₁, м²), время младшего торгового персонала (общий объем b₂, человеко-часов), время старшего торгового персонала (общий объем b₃, человеко-часов). Затраты на продажу одной партии товаров вида А составляют а₁₁ м², а₂₁ человеко-часов младшего торгового персонала, а₃₁ человеко-часов старшего торгового персонала. Для В и С эти числа соответственно а₁₂, а₂₂,  а₃₂ и а₁₃,  а₂₃, а₃₃. Прибыль от реализации одной партии товаров А, В, С равна с₁, с₂, с₃ соответственно. При каком объеме реализации прибыль будет максимальна?

Исходные данные задачи представлены на рисунке 2.1:

 

 

Рисунок 2.1 – Исходные данные

 

В ячейку E3, значение целевой функции, введем формулу (2.1):

 

                                (2.1)

 

В ячейки Е9:Е11, количество материалов, введем формулы (2.2):

 

                              (2.2)

 

Результат ввода формул 2.1 и 2.2 показан на рисунке 2.2:

 

 

Рисунок 2.2 – Результат ввода формул 2.1 и 2.2

 

Выбираем команду «Поиск решения» и заполняем диалоговое окно «Поиск решения» как показано на рисунке 2.3:

 

 

Рисунок 2.3 – Диалоговое окно команды «Поиск решения» для задачи оптимизационного типа

 

 

Рисунок 2.4 – Результат расчета задачи оптимизационного типа

 

Прибыль будет максимальна  при объеме реализации .

Ответ:

2.2 Решение  двойственной задачи и анализ  полученных данных

К имеющимся данным задачи подраздела 2.1 добавим следующее: двойственные оценки (z) – H9:H11, в ячейку Н13 введем формулу (2.3) целевой функции:

 

                             (2.3)

 

 

Рисунок 2.5 – Ввод формулы 2.3 целевой ячейки

 

В ячейку диапазона B13:D13 введем формулы (2.4) определяющие левые части ограничений двойственной задачи:

 

                                    (2.4)

 

 

Рисунок 2.6 – Ввод формулы 2.4 ограничения двойственной задачи

Выбираем команду «Поиск решения» и заполним диалоговое окно как показано на рисунке 2.7:

 

Рисунок 2.7 – Диалоговое окно команды «Поиск решения» для двойственной задачи

 

Затраты будут минимальны при объеме реализации равной .

Ответ:

2.3 Решение задачи в предположении целочисленности переменных

На основе задачи подраздела 2.1, при помощи команды «Поиск решения», добавим следующее ограничение целочисленности рисунок 2.8:

 

 

Рисунок 2.8 – Диалоговое окно команды «Поиск решения»

 

Рисунок 2.9 – Результат  целочисленного решения задачи симплекс методом с помощью надстройки MS Excel «Поиск решения»

2.4 Решение  транспортной задачи с помощью  надстройки MS Excel «Поиск решения»

Есть три поставщика с запасами a₁, a₂, a₃ и 5 потребителей (их спрос b₁, b₂, b₃, b₄, b₅ соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей C размера 3х5. Найти оптимальный план поставок. Исходные данные представлены на рисунке 2.10.

 

 

Рисунок 2.10 – Исходные данные

 

Исходная задача является открытой моделью, так как сумма потребностей больше суммы поставщика. Добавим фиктивного потребителя с нулевыми тарифами и запасами, рассчитанными по формуле (2.5):

 

                                                       (2.5)

 

Введем в ячейку H13 формулу 2.6 целевой функции:

 

                             (2.6)

 

В ячейки B12:G12 введем формулы (2.7):

 

                                       (2.7)

 

В ячейки H9:H11 введем формулы (2.8):

 

                                      (2.8)

 

При помощи команды «Поиск решений» добавим следующие ограничения  и значение целевой функции рисунок 2.12:

 

 

Рисунок 2.12 – Диалоговое окно команды «Поиск решений»

 

 

Рисунок 2.13 – Результат расчета транспортной задачи

 

Минимальные затраты  на поставку всей продукции составляют 209 ден.ед.

Ответ:

 

 

 

 

 

 

 

 

 

Выводы

В данной расчетно-графической работе было рассмотрено решение задач линейного программирования различными методами. Были рассчитаны min(max) значения целевой функции графическим методом. Симплекс методом был рассчитан оптимальный план реализации продукции для получения max прибыли, а так же рассмотрена её двойственное представление, по которому рассматривается минимизация затрат ресурсов. Так же решение задачи транспортным методом, найден оптимальный план перевозки продукции при минимальных расходах. Для проверки решения данные задачи были рассчитаны при помощи программы MS Excel, полученные значения целевых функций совпали.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Лист