Численное решение задачи линейного программирования

Задание для графического решения

Найти точку максимума функции цели Z,

Z(x ₁ , x ₂)= sx ₁ + gx ₂

при заданных ограничениях

где g – номер группы; s - номер студента по журналу.

ТРАНСПОРТНАЯ ЗАДАЧА

Постановка классической транспортной задачи

Классическая транспортная задача состоит в поиске оптимальных грузопотоков, т.е. в оптимальном закреплении поставщиков однородного груза за потребителями. В математической форме условия транспортной задачи выглядят следующим образом:

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i, …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что

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

Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:

Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.

Определение 1.

Всякое неотрицательное решение системы линейных уравнений

определяемое матрицей X=(x_ij)(i =1,…,m; j =1,…,n), называется планом транспортной задачи.

Определение 2.

План , при котором функция

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Дата добавления: 2019-01-14; просмотров: 327; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 5 6 Следующая ⇒

Мы поможем в написании ваших работ!