Курс предприним

Каждому из неравенств (6.7) на графике рис

6.1 соответствует полуплоскость, в пределах которой находятся все допустимые данным неравенством значения переменной величины Xj (j = 1, 2,..., 6).

(6.6)

Рис. 6.1.

х.

Так, неравенству х1 > 0 соответствует полуплоскость вправо от оси х2 (граница ее заштрихована).

Неравенству х3 = 8хх + 12х2 — 16 > 0 соответствует полуплоскость вправо и вверх от линии граничного значения данного неравенства (при х3 = 0). Уравнение этой линии

х, +3 / 2х2 -2=0.

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

Неравенствам (6.7) соответствует некоторая область — шести-угольник ABCDEF, образованный границами упомянутых выше полуплоскостей. Эта область может быть названа областью допустимых планов, поскольку любая точка в ее пределах отвечает требованиям наложенных ограничений (6.3).

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

Целевой функции соответствует семейство параллельных прямых. Рассмотрим одну из них, проходящую через начало координат, что будет иметь место при у = 22,8. При этом х2 = Зх,.

Интересующая нас прямая у = 22,8, как видно из рис. 6.1, имеет наклон вправо от оси х2. Задаваясь различными значениями у, получим семейство прямых линий, параллельных прямой у = 22,8, проходящей через точку 0. При этом чем меньше будет значение у, тем, очевидно, правее будет располагаться соответствующая прямая.

Поскольку мы добиваемся минимального значения у, то нас будет интересовать прямая, расположенная в наибольшем удалении вправо от прямой у = 22,8 и проходящая через многоугольник ABCDEF, — прямая ymil1.

Единственной точкой, соответствующей оптимальному плану, будет та вершина многоугольника ABCDEF (рис. 6.1), которая одновременно принадлежит области допустимых планов и отвечает требованию минимизации целевой функции у, — вершина С. Из уравнения прямой ВС, проходящей через точку С, следует, что Л", = 4. Из уравнения прямой DC, проходящей через ту же точку, следует, что х2 = 0.

Подставляя полученные значения х1 = 4 и х2 = 0 в уравнения (6.5), определим величины остальных переменных, составляющих оптимальный план:

х3 = 16; х4 = 0; х5 = 10;

х6 = 8.

Таким образом, оптимальный план будет следующим:

= 4;

х2 = 0;

*3 = 16;

X, = 0;

х5 = 10;

*6 = 8.

Линейная форма величины издержек при этом будет минимальной:

24 . 8 „ 228 132 ,, /сп\

у = ——х4+ — х0+ = = 13,2. (6.9)

10 10 10 10

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

При решении этих задач целевая функция рассчитывается по формуле, аналогичной (6.2):

/ = С1Х1 +С2Х2 +...+С]Х] +с*х„, (6.10)

где у — целевая функция, подлежащая максимизации. Отличие заключается в том, что знаки перед всеми постоянными коэффициентами меняются на обратные (с* = - с*).

Вычислительные методы линейного программирования

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

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

На основе этой идеи создан и разработан один из основных методов решения задач линейного программирования — так называемый симплекс-метод.

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

Первый шаг. Найти допустимый план, соответствующий одной из вершин области допустимых планов.

Второй шаг. Проверить, оптимален ли найденный план. Если оптимален, вычисления окончены. Если нет — следующий план.

Третий шаг. Переход к другой вершине (другому допустимому плану), в которой значение целевой функции меньше, проверка его на оптимальность и т. д.

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

Анализируя рис. 6.1, можно заметить, что в каждой из вершин две из переменных обращаются в нуль. Поэтому мы должны принять две переменные равными нулю, а затем найти остальные четыре из системы уравнений (6.3). В совокупности все переменные дадут один из допустимых планов, соответствующих некоторой вершине.

Чтобы преобразовать систему уравнений описанным образом, необходимо выразить каждую из неизвестных хь х2, ..., хт через остальные.

(6.11)

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

/

«11 «12 • • «1,„ 4

«21 «22 • «2,„

V «иг 1 «,„2 • ^тп у

Если это условие выполняется, то величины хь х2, ..., хт называют базисными. Каждый базис соответствует определенной вершине.

Преобразуем систему уравнений (6.3) так, чтобы, приравнивая две переменные нулю (например, х5 = 0, х6 = 0), можно было получить значение базисных величин хь х2, х3 и х4 — координаты одной из вершин многоугольника.

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

Действительно,

11

о 2 0,

Это дает нам право считать, что величины хь х2, х3 и х4 являются базисными и система (6.3) может быть разрешена относительно их.

Все необходимые преобразования будем производить с матрицей коэффициентов уравнений (6.3):

161 10 76 24

О 2 О 3

1

О 2 О

(6.12)

Курс предприним

В качестве примера возьмем…

Для него главная цель — получение прибыли за счет «удовлетворения потребностей народного хозяйства и граждан в высококачественной медицинской технике». Это конечная цель, которая должна быть достигнута предприятием в целом. Ее …

Элементами матрицы являются…

Так, элемент, записанный на пересечении /-то столбца и /-й строки матрицы, соответствует значению показателя эффективности, рассчитанному для значений параметров Z7,. и Z •. При составлении матрицы следует стремиться к ее …

Здесь раскрывается приведенная…

На первый взгляд, это звучит парадоксально. Но ведь говорим же мы об экономичной скорости на транспорте: далеко не самое быстрое движение автомобиля или судна приносит наибольшую выгоду. Как правило, не …

Как с нами связаться:

Украина:
г.Александрия
тел. +38 05235 7 41 13 Завод
тел./факс +38 05235  77193 Бухгалтерия
+38 067 561 22 71 — гл. менеджер (продажи всего оборудования)
+38 067 2650755 - продажа всего оборудования
+38 050 457 13 30 — Рашид - продажи всего оборудования
e-mail: msd@inbox.ru
msd@msd.com.ua
Скайп: msd-alexandriya

Схема проезда к производственному офису:
Схема проезда к МСД

Представительство МСД в Киеве: 044 228 67 86
Дистрибьютор в Турции
и странам Закавказья
линий по производству ПСВ,
термоблоков и легких бетонов
ооо "Компания Интер Кор" Тбилиси
+995 32 230 87 83
Теймураз Микадзе
+90 536 322 1424 Турция
info@intercor.co
+995(570) 10 87 83

Оперативная связь

Укажите свой телефон или адрес эл. почты — наш менеджер перезвонит Вам в удобное для Вас время.