Дискретная, математика, и. .математическая, кибернетика
Галканов А.Г., кандидат технических наук, доцент Московского государственного гуманитарно-экономи-че-ского университета, Какалыев Я., кандидат технических наук (Туркменистан)
О ЧЕТЫРЁХЭТАПНОМ АЛГОРИТМЕ СИМПЛЕКС МЕТОДА
Рассмотрим каноническую задачу линейного программирования
f (x) = c1x1 + c2x2 +... + cnxn ^ extr (max v min), (1)
an xi + ai2 x2 + ... + aimxm + aim+1 xm + ." + ö1nxn = b1, a2ixi + a22x2 + ... + a2mxm + a2m+1 xm+1 + ... + a2nxn = Ь2,
(2)
а ,х, + а 2х2 +... + а х + а +,х +, +... + а х = Ь ,
т1 1 т2 2 тт т тт+1 т+1 тп п т'
X! > 0, Х2 > 0,..., Хп > 0. (3)
В работе [1] предложен четырёхэтапный алгоритм симплекс метода решения канонической задачи линейного программирования (1) — (3). Цель первого этапа состоит в преобразовании системы (2) к базисному виду (если она задана в небазисном виде) и нахождении её базисного решения. Цель второго этапа состоит в нахождении допустимого решения. На третьем этапе допустимое решение проверяется на оптимальность. Если найденное допустимое решение не является оптимальным, то на четвёртом этапепродолжается поиск оптимального решения, где используется понятие строки целевой функции. Работа алгоритма каждого этапа показана на примерах. Даны решения экономических задач с составлением их математических моделей. Изложен минимум теоретического материала к симплекс методу. Ко многим сформулированным теоремам даны альтернативные доказательства. Однако во введении и на стр. 26 этого пособия допущены две ошибки, в связи с чем авторы приносят свои извинения читателям этой книги. Предлагаем их исправления. Во введении последний абзац под номером 7) считать неверным. Случай 1 (стр. 26) следует читать в следующей редакции. Пусть с1 = 1, с2 = 0,
а11 = 2, а12 = 3, Ь1 = 6, х1 > 0, х2 > 0: /(х1, х2) = х1 ^ тах, 2х1 + 3х2 = 6. Ясно, что О = {(х1, х2): 0 < х1 < 3, х2 = (6 — 2х1):3} есть прямоугольный треугольник с вершинами 0(0, 0), А(3, 0), В(0, 2), т.е. компакт, так что по теореме 5 из главы 1 задача имеет решение. При этом все точки гипотенузы ААОВ являются допустимыми решениями данной задачи. Однако, согласно следствию 6 из главы 1, лишь в точке А(3, 0) функция / = х1 принимает свой глобальный максимум, поскольку векторы с = (1, 0) и х = (3,0) сонаправлены: 1 • 3 = V1 + 0 • V9 + 0. Так что х = (3, 0) — единственное реше-
ние данной задачи и max f = 3. Рис. 1 на стр. 27 читать без точки C в виде, где x = x1, y = x2.
Рис.1.
Литература
1. Галканов А., Какалыев Я. Симплекс метод в понятиях, задачах и решениях. Учебно-методическое пособие для студентов высших учебных заведений. М.: Издательство «Новое время», 2014. - 117 с.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.