Линейное программирование. Решение задач графическим способом

    SetColor(White);

    SetLineStyle(0,0,NormWidth);

    OutTextXY(300,230,Result);{Выводим строку ответа}

  end

  else

    OutTextXY(7,3,'Вычисления не закончены!!!');

  {Завешение программы}

  Bar(0,0,GetMaxX,MaxY-1);

  SetColor(White);

  OutTextXY(7,3,'Нажмите любую клавишу для выхода');

  ReadKey;

End;

BEGIN

  i:=0;{Начальное значение кол-ва неравенств}

  Gd:=Detect;

  InitGraph(Gd, Gm, 'C:BPBGI'); { Путь к BGI драйверам }

  if GraphResult grOk then Halt(1);

  ShowXOY;

  EnterNerav;

  EnterMainF;

  GetResult;

  CloseGraph;

END.

Заключение

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

Вообще, с помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если N и M связаны соотношением N – M = 2.

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

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

Z = С1х1+С2х2+... +СNxN при ограничениях

a11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

aМ1x1 + aМ2x2 + ... + aМNХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

где все уравнения линейно независимы и выполняется cоотношение N - M = 2.

Используя метод Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х1, х2, ..., хM, а свободными - два последних: хМ+1, и хN, т. е. система ограничений приняла вид:

x1 + a1,М+1xМ+1 + a1NХN = b1

x2 + a2,М+1xМ+1 + a2NХN = b2

. . . . . . . . . . . .

xМ + aМ, М+1x2 + aМNХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные - неотрицательные: хj ≥ 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.

Литература

  1. Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. - 184 с.

  2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие - 2-е изд., испр. и доп. - М.: Высш. шк. ,1993 - 336 с.

  3. Ашманов С.А.Линейное программирование. - М.: Наука, 1981.

  4. Баканов М.И., Шеремет А.Д. Теория экономического анализа: Учебник. -4-е изд., доп. и перераб. - М.: Финансы и статистика, 2000. - 416 с.

  5. Баканов М.И., Шеремет А.Д.Экономический анализ: ситуации, тесты, примеры, задачи, выбор оптимальных решений, финансовое прогнозирование: Учеб. пособие. - М.: Финансы и статистика, 1999. -656 с.

  6. Банди Б. Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. -176 с.

  7. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 176 с.

  8. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.2. Транспортные задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 240 с.

  9. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента - СПб.: Издательство “Лань”, 2000. -480 с.

  10. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование,теория, методы и приложения. - М.: Наука, 1969.

  11. Гасс С.Линейное программирование. - М.: Физматгиз, 1961.

  12. Заварыкин В. М. и др. Численные методы: Учеб. пособие для студентов физ.-мат. спец. пед. ин-тов / В.М. Заварыкин, В.Г. Житомирский, М.П. Лапчик. - М.: Просвещение, 1990. - 176 с

  13. .Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. /Под общ. ред. проф. Кузнецова А.В., М., “ВЫШЭЙШАЯ ШКОЛА”, 1994. - 288 с.

  14. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие. – 2-е изд., перераб и доп. - М.: Высш. школа, 1980. -300 с.

  15. Ляшенко И.Н, Карагодова Е.А, Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Издательское объединение “Вища школа”, 1975. - 372 с.

  16. Пер. с яп. /М. Кубонива, М. Табата, С. Табата, Ю. Хасэбэ, под ред. М. Кубонива.  Математическая экономика на персональном компьютере: - М.: Высш. школа, 1980.

  17. Под ред и с предисл. Е.З. Демиденко – М.: Финансы и статистика, 1991. – 304 с.

  18. Солодовников А.С. Введение в линейную алгебру и линейное программирование. М., Изд. “Просвещение”, 1966. - 184 с.

  19. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т.1: Пер с англ. - М.: Мир, 1991. -360 с.

  20. Тынкевич М.А. Экономико-математические методы (исследование операций). Изд. 2, испр. и доп. - Кемерово, 2000. - 177 с.

Рецензия

1	2	3	4

Copyright © Radioland. Все права защищены.
Дата публикации: 2004-09-01 (0 Прочтено)