Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 48


таблицу 7.4).

Таблица 7.4

Предприятие

База

Б1

Б2

Б3

Б4

Б5

П1

П2

П3

с11

с21

с31

с12

с22

с32

с13

с23

с33

с14

с24

с34

с15

с25

с35

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б1, Б2, Б3, Б4, могут дать не более b1, b2, b3, b4, b5 единиц сырья. Требуется составить такой план снабжения предприятий сырьем (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырье.

Опять поставим задачу линейного программирования. Обозначим хij количество сырья, получаемое i-м предприятием с j-и базы. Всего план будет состоять из 15 элементов решения:

        (7.14)

Введем ограничения по потребностям. Они состоят в том, что каждое предприятие получит нужное ему количество сырья (ровно столько, сколько ему требуется):

       (7.15)

Далее напишем ограничения-неравенства, вытекающие из производственных мощностей баз:

        (7.16)

Наконец, запишем суммарные расходы на сырье, которые мы хотим минимизировать. С учетом данных табл. 7.4 получим (пользуясь знаком двойной суммы):

L =

      (7.17)

 

Опять перед нами задача линейного программирования: найти такие неотрицательные значения переменных xij которые удовлетворяли бы ограничениям-равенствам (7.15), ограничениям-неравенствам (7.16) и обращали бы в минимум их линейную функцию (7.17).

Таким образом, мы рассмотрели несколько задач линейного программирования. Все они сходны между собой, разнятся только том, что в одних требуется обратить линейную функцию в максимум, в других — в минимум; в одних ограничения — только неравенства, в других — как равенства, так и неравенства. Бывают задачи линейного программирования, где все ограничения — равенства. Эти различия несущественны, так как от ограничений-неравенств легко переходить к ограничениям-равенствам и обратно, как будет показано в следующем параграфе.




Содержание  Назад  Вперед