• Кратко о линейном программировании. Линейные программы - реферат Линейные программы включают в себя

    Линейной называется программа, являющаяся записью линейного алгоритма. В такой программе все операторы выполняются строго последовательно, т.е. после выполнения каждого из них (кроме END) ЭВМ автоматически переходит к выполнению следующего за ним оператора.

    Составление простейших программ

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

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

    для блока Начало - оператор REM с названием программы;

    для блока Ввод - оператор ввода;

    для блока Процесс - оператор присваивания;

    для блока Вывод - оператор вывода;

    для блока Останов - оператор END.

    В этом все правило!

    Теперь приведем примеры конкретных программ рассматриваемого вида.

    Задача 12.2

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

    Задача 12.3

    Переставить значения величин А и В.

    Решение задач 12.2 и 12.3. Эти задачи рассматривались в главе 10, поэтому на рис. 12.2 приведены без пояснений схема алгоритма и программа задачи 10.2, а на рис. 12.3 - то же для задачи 10.3.

    На рис. 12.2 и 12.3 стрелками показано соответствие операторов программы блокам схемы алгоритма.

    Приведем программы решения еще двух задач. Программа задачи 12.1 иллюстрирует использование величин различного типа. Программа задачи 12.2 демонстрирует организацию вывода данных на печатающее устройство.

    Рис. 12.2

    Задача 12.1

    Вычислить значения У и Z по формулам:

    где В и В - целые величины.

    Решение

    Исходные данные: Э%, В%, С, X, А(а).

    Результат: Y,Z%.

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

    • 10 REM ЗАДАЧА 1
    • 20 PRINT "ВВЕСТИ D%, В%, С, X, А"
    • 30 INPUT D%,В%, С, X, А 40 R$="HBAH0B, 10А КЛ"
    • 50 Z%=2*D%-3*В%
    • 60 Y=(3*ABS(X)+С:(1/3)+SIN(A)/COS(А))*Z%
    • 70 PRINT "Z%=";Z%; "Y="; Y 80 PRINT R$
    • 90 END

    Задача 12.2

    Вычислить значение функции У = Л 2 + В 1 и отпечатать (вывести на принтер) значения исходных данных и результатов.

    Решение

    Программа вычисления функции Y:

    • 20 REM ВЫВОД НА ПЕЧАТЬ 30 PRINT "ВВЕСТИ А, В"
    • 40 INPUT А, В 50 У=А Л 2+В Л 2
    • 60 LPRINT "ДАННЫЕ:"," А=";А;" В=";В 70 LPRINT
    • 80 LPRINT "РЕЗУЛЬТАТ:"," Y=";Y 90 END

    Оператор в 30-й строке этой программы выводит текст на экран дисплея, а операторы 60-80 - на принтер. Оператор в 70-й строке печатает пустую строку на листе бумаги.

    Линейные программы с массивами

    Массивы в языке Бейсик. Напомним определение массива: массивом называется упорядоченная совокупность однородных величин, обозначенных каждая одним и тем же именем с различными целочисленными индексами, изменяющимися по порядку.

    В Бейсике используются одно- и двумерные массивы (в QBASIC допустимы даже восьмимерные). Они, как и простые переменные, могут быть различных типов: целые, вещественные, текстовые (строковые) и т.д.

    Внимание! В Бейсике отсутствуют операции обработки массивов в целом, т.е. операции вида «ввести массив Р(1:99)», которые мы привыкли использовать в главах 8 и 9. Для выполнения операции над массивом необходимо перечислить операции, выполняемые над каждым его элементом.

    Рассмотрим общий вид элемента массива в Бейсике:

    • - элемент одномерного массива: (к);
    • - элемент двумерного массива: (i,j),

    где - имя массива, должно отвечать тем же правилам, что и имя простой переменной;

    к - индекс (номер) элемента одномерного массива, к

    i ,j - индексы элемента двумерного массива (номера строки и столбца, на пересечении которых он находится), i > 0, j > 0. В QBASIC можно установить начальные значения k, i, j равными 1. Индексы k, i, j могут быть представлены любыми арифметическими выражениями. При вычислении выражения, представляющего индекс, в QBASIC результат округляется до ближайшего целого.

    Примеры записи элементов массива:

    Р$(0), С2(101) , X(4 б,5*К+1) , Т%(N/2, М) .

    В схеме алгоритма те же элементы имели бы такие обозначения: Р 0 ,

    С2ю1, X46,5?+i, T w /2>m-

    Внимание! Если в программе используется массив, то он должен быть предварительно объявлен, т.е. ЭВМ должна быть сообщена информация о типе и размерах этого массива с помощью оператора DIM.

    Пример: оператор DIM Р$(6), i_iB% (4,8) сообщает о наличии в программе

    текстового Р(0:6) и целого В(0:4, 0:8) массивов.

    Исходя из информации, содержащейся в операторе DIM, ЭВМ выделяет (резервирует) для каждого массива область памяти требуемого размера.

    Общий вид оператора DIM:

    В случае одномерного массива:

    DIM (d) ,

    В случае двумерного массива:

    DIM (п, ш)

    где DIM - имя оператора (от слова dimension - «размерность»); - имя массива; d, п, ш - размеры массива, т.е. d - номер последнего элемента одномерного массива; n(m) - номер последней строки (последнего столбца) двумерного массива.

    Размер массива выражается в большинстве версий Бейсика {в том числе в QBASIC) целым числом или целой переменной.

    Особенности записи оператора DIM:

    • 1) в одном операторе DIM можно объявлять любое число массивов (см. пример);
    • 2) оператор DIM рекомендуется помещать в начале программы;
    • 3) не следует использовать в программе простую переменную и массив с одним и тем же именем.

    Пример: оператор DIM D% (2), А (2,3), К$ (3) сообщает:

    • массив D% - одномерный целый, содержащий элементы D%(0), D%(1), D%(2);
    • массив К - одномерный текстовой, включает элементы К$(0), к$(1), К$(2), К$(3);
    • массив А - двумерный вещественный, включает такие элементы:

    Составление линейных программ с массивами. Прежде всего отметим особенности работы с массивами в программе.

    1. Элементы массивов получают значения с помощью операторов ввода или присваивания как простые переменные. При вводе (выводе) массивов в операторах ввода (вывода) перечисляются имена всех вводимых (выводимых) элементов массива.

    Пример: программа ввода и вывода массива Р (1:3) может иметь такой вид:

    • 20 DIM Р(3)
    • 30 INPUT Р(1), Р(2), Р (3)
    • 40 PRINT Р(1), Р(2), Р(3)
    • 50 END
    • 2. Все массивы можно разделить на два вида:
      • массивы постоянного размера (например, Р(1:7), В(1:4, 1:8)];
      • массивы переменного размера [например, А(1:&); С(1 :т, 1: d). В главах 8 и 9 мы использовали оба вида, не делая различий между ними.

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

    Следует только помнить: переменные - размеры массивов должны быть определены до обращения к оператору DIM.

    Пример:

    10 INPUT М 20 DIM Х(М)

    Линейные программы с массивами составляются в соответствии с рассмотренным ранее правилом составления простейших программ, которое можно дополнить одним пунктом - «после оператора REM следует записать в программе оператор DIM». Кроме того, необходимо учитывать только что изложенные сведения о работе с массивами.

    Теперь покажем построение рассматриваемых программ на конкретных примерах. Для начала вернемся к задаче 8.5. Схема алгоритма ее приведена на рис. 10.11. Заменив каждый блок этой схемы соответствующим оператором согласно правилу, приведенному в 12.2, и добавив оператор DIM, получим программу, приведенную ниже. После ознакомления с этой программой рекомендуем читателю самому составить программу решения задачи 10.7 и сравнить ее с приведенной ниже:

    • 10 REM СУММА
    • 20 DIM В(3, 3), S (2)
    • 30 PRINT "ВВЕСТИ МАТР. В(3, 3)"
    • 4 0 INPUT В(1, 1), В(1, 2), В(1, 3)
    • 50 INPUT В (2, 1), В (2, 2), В(2, 3)
    • 60 INPUT В(3, 1), В(3, 2), В(3, 3)
    • 70 S(l) =В (1, 1)+В(1, 2) +В (1, 3)
    • 80 S (2) =В (1, 3) +В (2, 3)+В(3, 3)
    • 90 PRINT "S(1)="; S (1); "S(2)=";
    • S (2)
    • 100 END
    • 10 REM СДВИГ 20 DIM В(4)
    • 30 PRINT "ВВЕСТИ МАССИВ В (4) "
    • 40 INPUT В(1), В(2),
    • 50 D=B(1)
    • 60 В(1)=В(2)
    • 70 В(2)=В(3)
    • 80 В(3)=В (4)
    • 90 В(4)=D
    • 100 PRINT "МАССИВ В=(";
    • 110 PRINT В(1); В(2);

    В (3) ; В (4) ; ") "

    Контрольные вопросы

    • 1. Какой оператор в Бейсике указывает тип и размеры массива?
    • 2. Каково обозначение элементов массива в Бейсике? Каково наименьшее значение индекса элемента массива?

    Задачи для самостоятельного решения

    • 2. Вычислить среднее арифметическое переменных В, Си И.
    • 3. Рабочие Иванов и Петров изготовили за смену А и В деталей соответственно, перевыполнив норму. Определить процент перевыполнения нормы (норма - С деталей в смену).
    • 4. Определить разницу в возрасте невест для двух братьев Пети и Димы. Их возраст а и Ь соответственно. Возраст невесты определяется по формуле

    где (7 - возраст жениха.

    5. Вычислить значение у:

    где

    Примем кф 0; г,Ф 0.

    • 6. Вычислить объем и площадь поверхности цилиндра диаметром О и высотой Н.
    • 7. Вычислить стоимость мебельного гарнитура, содержащего четыре стула, два кресла и один стол. Стоимость изделий соответственно А, В и С руб.
    • 8. Определить среднее арифметическое элементов массива С(1:5).
    • 9. Определить произведение сумм элементов каждой строки матрицы Р(1:2, 1:3).
    • 10. Переставить соответствующие элементы первой и второй строк матрицы А(1:2, 1:2).
    • 11. Переставить элементы массива Я(1: 6): 1-й элемент и 6-й, 2-й и 5-й, 3-й и 4-й.

    Если в программе все операторы выполняются последовательно, один за другим, такая программа называется линейной. Рассмотрим в качестве примера программу, вычисляющую результат по заданной формуле.

    Задача 1.1. Расчет по формуле

    Написать программу, которая переводит температуру в градусах по Фаренгейту в градусы Цельсия по формуле:

    где С - температура по Цельсию, a F - температура по Фаренгейту.

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

    В данном случае:

    В качестве исходных данных выступает одно вещественное число, представляющее собой температуру по Цельсию,

    В качестве результата - другое вещественное число.

    Перед написанием программы откроем интегрированную среду Visual C++:

    Пуск/Программы/Microsoft Visual Studio/ Microsoft Visual C++ 6.00

    1) File > New...

    2) В открывшемся окне:

    Выберите тип Win32 Console Application;

    Введите имя проекта в текстовом поле Project Name;

    Введите (выберете с помощью кнопки …) имя каталога размещения файлов проекта в текстовом поле Location, например G:/ASOIZ/

    Щелкните левой кнопкой мыши на кнопке ОК.

    3) открывается диалоговое окно Win32 Console Application - Stepl of 1 и в нем:

    Выберите тип An empty project;

    Щелкните на кнопке Finish.

    4) После щелчка появится окно New Project, в котором щелкните на кнопке ОК.

    1) File > New.... В результате откроется диалоговое окно New.

    2) На вкладке Files:

    Выберите тип файла (в данном случае: C++ Source File);

    В текстовом поле File Name введите нужное имя файла;

    Флажок Add to project должен быть включен;

    Щелкните на кнопке ОК.

    Набираем следующий текст программы:

    Рассмотрим каждую строку программы отдельно.

    В начале программы записана директива препроцессора, по которой к исходному тексту программы подключается заголовочный файл . Это файл, который содержит описания операторов ввода-вывода cin и cout.

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

    Любая заготовка при написании программы имеет вид:

    #include <…>

    #include <…>

    объявление переменных;

    ввод исходных данных;

    расчет результата;

    вывод результата;

    Для хранения исходных данных и результатов надо выделить достаточно места в оперативной памяти. Для этого служит оператор 2. В нашей программе требуется хранить два значения: температуру по Цельсию и температуру по Фаренгейту, поэтому в операторе определяются две переменные. Одна, для хранения температуры по Фаренгейту, названа fahr, другая (по Цельсию) - cels. Имена переменным дает программист, исходя из их назначения. Имя может состоять только из латинских букв, цифр и знака подчеркивания и должно начинаться не с цифры.

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

    Основные типы:

    int (short, unsigned) – целочисленные,

    float (double, long double) – вещественные

    char – символьный

    bool – логический

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

    В операторе 4 выполняется ввод с клавиатуры одного числа в переменную fahr . Для этого используется стандартный объект cin и операция извлечения (чтения) >>. Если требуется ввести несколько величин, используется цепочка операций >>.

    В операторе 5 вычисляется выражение, записанное справа от операции присваивания (обозначаемой знаком =), и результат присваивается переменной cels, то есть заносится в отведенную этой переменной память. Cначала целая константа 5 будет поделена на целую константу 9, затем результат этой операции умножен на результат вычитания числа 32 из переменной fahr.

    Для вывода результата в операторе 6 применяется объект cout. Выводится цепочка, состоящая из пяти элементов. Это строка " По Фаренгейту:" , значение переменной fahr , строка ", в градусах Цельсия:" , значение переменной cels и оператор перехода на новую строку endl.

    Последний оператор (оператор 7) этой программы предназначен для возврата из нее и передачи значения во внешнюю среду.

    Далее компилируем программу. Для этого нажимаем кнопку на панели инструментов либо комбинацию клавиш Ctrl+F7. В окне вывода (внизу экрана) должно вывестись сообщение 0 error(s), 0 warning(s) (0 ошибок, 0 предупреждений). Если есть ошибки - сверьте с оригиналом.

    Для запуска программы нажимаем кнопку на панели инструментов либо комбинацию клавиш Ctrl+F5.

    При запуске программы вместо русских символов видим???, что вызвыно различными стандартами кодировки символов кириллицы в операционных системах MS DOS-и Windows. Для исправления добавим в программу функцию CharToOem (дополнения для наглядности выделены красным цветом)

    #include

    #include

    char* RUS(const char* text)

    CharToOem(text, buf);

    float fahr, cels;

    cout<

    cels=5/9 * (fahr - 32);

    cout<

    cout<

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

    Как вы можете видеть, результат выполнения программы со стабильностью оказывается равным нулю! Это происходит из-за способа вычисления выражения. Давайте вновь обратимся к оператору 4. Константы 5 и 9 имеют целый тип, поэтому результат их деления также целочисленный. Естественно, что результат дальнейших вычислений не может быть ничем, кроме нуля. Исправить эту ошибку просто - достаточно записать хотя бы одну из констант в виде вещественного числа, например:

    cels = 5. / 9 * (fahr - 32);

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

    Оператор присваивания. Он задает или изменяет текущее значение некоторой переменной. При этом изменяется содержание конкретного элемента памяти, отведенного для этой переменной. Поскольку цель любого алгоритма - это получение в определенном месте памяти нужного значения, практически любая программа содержит этот оператор. Операторы ввода-вывода. Стандартные процедуры ввода данных используются для определения начальных значений определенных переменных и состоят из имени процедуры и списка ввода, содержащий имена переменных, значения которых будут вводиться с клавиатуры или из файла, т.е. переменным будут присваиваться какие-то определенные значения.
    Чаще для определения начальных значений удобнее пользоваться командой ввода, а не командой присваивания, потому что при необходимости использования программы с другими исходными данными не приходится менять текст программы.
    Если в записи алгоритма стоит команда ввода, то его выполнение прерывается и управление передается программе, которая может осуществить ввод данных. После ввода данных управление передается следующей команде алгоритма.
    На языке Паскаль процедура ввода данных имеет вид:
    READ (список ввода);
    READLN (список ввода).
    При выполнении процедур READ и READLN программа переходит в состояние ожидания ввода данных. Если в списке ввода указано несколько переменных, то их можно вводить в одной строке, отделяя друг от друга символом «пробел», или в отдельных строках (в столбик), завершая ввод каждого значения клавишей Enter.
    Работа процедуры не завершится, пока не будут введены значения для всех переменных, указанных в списке. Тип вводимых значений, должно совпадать с тем, который имеет соответствующая переменная.
    Оператор READLN отличается от оператора READ тем, что после введения необходимого числа данных курсор перемещается на следующую строку.
    Если ввод данных осуществляется с клавиатуры, то список ввода - это список переменных, т.е. последовательность имен переменных, разделенных запятыми. Если ввод осуществляется из файла, то в списке ввода первая переменная - файловая, связана с именем реального файла.
    Стандартные процедуры вывода результатов вычислений используются для вывода их значений на экран, принтер или в файл. На языке Паскаль процедуры вывода имеют вид:
    WRITE (список вывода);
    WRITELN (список вывода).
    Список элементов вывода значительно шире, чем в процедурах ввода. В него могут входить:
    идентификаторы величин, значения которых будут выводиться на соответствующее устройство или в файл;
    выражения, значение которых сначала будут вычислены, а затем выведены на устройство;
    стали величины (числовые, символьные, строковые).
    Различие между WRITE и WRITELN заключается в том, что вывод оператором WRITE начинается с текущего местоположения курсора на экране монитора и курсор после окончания вывода остается в той же строке. Оператор WRITELN выводит значения с текущего места, а затем курсор перемещается на следующую строку. Можно использовать оператор WRITELN без списка вывода для перемещения курсора на новую строку.
    Если вывод осуществляется на экран монитора, то список вывода - это список переменных, или последовательность имен переменных, констант или выражений, разделенных запятыми. Если вывод осуществляется в файл, то в списке вывода первая переменная - файловая, связана с именем реального файла.
    В команде вывода после элемента списка вывода через двоеточие можно указать формат вывода, т.е. ширину экрана, на котором будут располагаться значения. При выводе действительных данных можно указать также количество десятичных цифр в дробной части, которую нужно вывести на экран.
    Пример: write (А: 10: 3, В: 8).
    Оператор вызова вспомогательного алгоритма. В Паскале реализовано подпрограммы-процедуры и подпрограммы-функции. Вызов подпрограммы осуществляется по ее имени с указанием фактических параметров. При этом на месте фактических аргументов могут быть конкретные значения, имена фактических переменных, выражения, а на месте результатов - только имена фактических переменных. При этом количество, типы и назначение формальных и фактических параметров в соответствующих списках параметров должны совпадать.

    1.2 Кратко о линейном программировании.

    Что же такое линейное программирование? Это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

    Итак, линейное программирование возникло после Второй мировой войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».
    Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

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

    Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

    · рационального использования сырья и материалов; задачи оптимизации раскроя;

    · оптимизации производственной программы предприятий;

    · оптимального размещения и концентрации производства;

    · составления оптимального плана перевозок, работы транспорта;

    · управления производственными запасами;

    · и многие другие, принадлежащие сфере оптимального планирования.

    Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.

    Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

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

    Итак, линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.


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

    Основная задача линейного программирования (ОЗЛП) ставится следующим образом: Имеется ряд переменных . Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений:

    {1.1}

    и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)

    Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

    Допустимым решением ОЗЛП называют любую совокупность переменных , удовлетворяющую уравнениям (1.1).

    Оптимальным решением называют то из допустимых решений, при котором ЦФ обращается в минимум.

    На практике ограничения в задаче линейного программирования часто заданы не уравнениями, а неравенствами. В этом случае можно перейти к основной задаче линейного программирования.

    Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

    {1.2}

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

    Введём уравнения:

    {1.3}

    Где - добавочные переменные, которые также как и являются неотрицательными.

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

    Коэффициенты в формуле (1.3) перед равны нулю.


    1.3. Построение ограничений и градиента целевой функции: 1.4. Область допустимых решений – отрезок AB. 1.5. Точка А – оптимальная. Координаты т. А: ; ; . 2. Решение задачи линейного программирования симплекс-методом. Прямая задача. Задачу линейного программирования для любой вершины в компактной форме можно представить в виде: Для получения используем алгоритм, приведённый в...



    Лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...

    Задачи f1(x)=max=g1(x) – для первого предприятия; - для остальных предприятий. Решение задачи оптимального распределения средств между предприятиями методом динамического программирования Таблица 12 Средства с, тыс. гр. Предприятие 1 2 3 4 G1(x) G2(x) G3(x) G4(x) 20 11 13 12 10 40 21 20 22 27 60 40 42 34 33 80 54 45 55 57 100 62 62 ...

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

    Читать еще: